Аффирмация дня: не забывайте быть добрым к себе 🌟
Двоичное дерево поиска — это структура данных, обладающая следующими свойствами:
A. У каждого узла дерева может быть не более двух дочерних элементов.
B. Все узлы в правом поддереве больше корня
C. Все узлы в левом поддереве меньше корня
NB: корень — это первый узел в дереве.
Наилучший возможный сценарий бинарного дерева поиска — 0(log n). Это связано с тем, что для lookup(), т. е. найти или удалить узел, нам пришлось бы перебирать узел, а затем делить дерево на каждой итерации. Это делает lookup() и remove() намного быстрее при использовании бинарного дерева поиска, чем при использовании связанного списка (ниже мы увидим, почему).
Наихудший возможный сценарий бинарного дерева поиска — 0(n). Следовательно, Большой 0 бинарного дерева поиска равен 0(n). Наихудший сценарий бинарного дерева поиска может иметь место, когда в правом поддереве дерева есть только узлы (левое поддерево пусто) или есть только узлы в левом поддереве дерева (правое поддерево пусто). Здесь мы не получаем преимущества деления наших задач пополам {0(log n), логарифмическое время}, поскольку мы работаем по прямой. Это похоже на связанные списки.
Бинарные деревья поиска против связанных списков
Как упоминалось выше, мы работаем по прямой в связанном списке. Таким образом, если мы ищем узел или пытаемся удалить узел, нам придется перебирать связанный список. Это 0(n) операций.
Однако вставка элемента в конец связанного списка, т. е. push — это 0(1). Таким образом, метод insert() лучше работает со связанным списком, чем с бинарным деревом поиска, потому что 0(1) более эффективен, чем 0(log n).
В итоге:
Давайте реализуем бинарное дерево поиска (BST)!
BST: Вставить()
Для этого метода мы:
- Создайте новый узел.
- Условный оператор, если дерево пусто.
- Имейте условный оператор, если вставляемый узел имеет то же значение, что и узел, который уже находится в дереве.
- Сравните узел, который мы пытаемся вставить, с 1-м узлом, если он меньше или меньше предыдущего узла, он идет влево, а если он больше или больше предыдущего узла, он идет вправо.
- Если это null (пустое пространство), мы вставляем новый узел в это пространство, в противном случае мы переходим к следующему узлу и сравниваем (как на шаге 4).
- Используйте цикл while, потому что мы не знаем, сколько раз мы будем проходить по дереву. То есть мы не знаем, сколько раз будем делать шаги 4 и 5.
insert(value){ const newNode = new Node(value); //we create a new Node if(this.root === null){ this.root = newNode; return this; //if we have an empty tree, root is set equal to the new Node and is returned } let temp = this.root //we create a temp variable to point to the parent element and we will use temp to iterate through the list while(true){ if(newNode.value === temp.value) return undefined { if(newNode.value < temp.value) { if (temp.left === null){ temp.left = newNode; return this; //returns the entire tree } temp = temp.left; //if the space isn't open on the left side of the tree } else { if (temp.right === null) { temp.right = newNode; return this; } temp = temp.right; } } } }
BST: Содержит()
Здесь мы ищем узел внутри дерева.
Мы начинаем с корня дерева, и либо а) у нас есть полное дерево, по которому мы можем выполнить итерацию, либо б) у нас есть пустое дерево, поэтому корень будет равен нулю.
contains(value) { if(this.root === null) return false; let temp = this.root //if we have items in the tree, we create a variable temp and use it to iterate through the tree while(temp){ if (value < temp.value){ temp = temp.left; //if the number we're looking for is less than the parent, temp moves to the left and down } else if (value > temp.value){ temp = temp.right; //if the number is greater than the parent, temp moves to the right } else{ return true; //if the values are the same return true } return false; //if temp is equal to null it'll return false and break out of the while loop. For instance if we're looking for a number that's not in the tree } }
BST: минимальное значение()
Мы хотим вернуть узел, содержащий минимальное значение (наименьшее число) в дереве. Если левое поддерево не пусто, мы запускаем цикл while, пока не получим минимальное значение. Если он пуст, мы выходим из цикла while и возвращаем текущий узел, который является минимальным значением.
minValueNode(currentNode) { while (currentNode.left != null){ currentNode = currentNode.left } return currentNode }