Двоичные деревья — это структура данных, которая позволяет нам эффективно хранить и обновлять данные, сохраненные в наборе данных. Эти типы деревьев имеют не более двух дочерних элементов и следуют правилу, которое определяет, на какой стороне набора данных будет сохранена информация. Временная сложность вставки или поиска фрагмента данных в дереве составляет O (log n). Прежде чем мы перейдем к тому, как это сделать, давайте определим несколько ключевых терминов.
Бинарное дерево и бинарное дерево поиска — это два разных типа деревьев с примерно одинаковой структурой.
Двоичное дерево. Дерево с не более чем двумя дочерними узлами.
Двоичное дерево поиска:дерево с не более чем двумя дочерними узлами, узлы которого следуют правилу, определяющему путь, по которому любой новый узел будет помещен в дерево. Например, левые потомки ≤ родительский узел ‹ правые потомки.
Некоторыми другими ключевыми терминами могут быть Complete, Full и Perfect:
Полное двоичное дерево: каждый узел имеет ноль или двух дочерних элементов. Узлы не имеют только одного ребенка.
Полное бинарное дерево: каждый уровень в дереве полностью заполнен, за возможным исключением последнего уровня, который должен быть заполнен слева направо.
Идеальное бинарное дерево: полное и законченное.
Теперь, когда мы знаем, что такое бинарное дерево и как оно работает, давайте попробуем его создать. Базовый код для двоичного дерева довольно прост: у вас есть левая и правая переменные, которые ссылаются на новый узел, и переменная val, которая представляет собой данные, которые вы хотите сохранить.
class BinaryTree {
constructor(val) {
this.val = val;
this.left = null;
this.right = null;
}
}
Теперь давайте создадим функцию для ввода значения в двоичное дерево поиска. Предположим, что значения, которые мы хотим сохранить, являются целыми числами.
class BinaryTree { addValue(val) { if(val > this.val) { this.right = new BinaryTree(val) } else { this.left = new BinaryTree(val) } } }
Хотя это не единственное, что нам нужно, что, если уже есть набор значений, в котором мы хотим установить наше новое значение? Мы можем исправить это, немного изменив эту функцию так, чтобы она зацикливалась до тех пор, пока не будет найдено нулевое значение.
class BinaryTree {
curNode = this
while(curNode.left || curNode.right) {
if(val > this.val) {
curNode = curNode.right
} else {
curNode = curNode.left
}
if(!curNode) {
Class BinaryTree {
addValue(val) {
currentNode = this
while (true){
if(val <currentNode.val){
if (currentNode.left == null){
currentNode.left = new BinaryTree(n);
return this;
}else{
currentNode = currentNode.left;
}
} else {
if (currentNode.right == null) {
currentNode.right = new BinaryTree(n);
return this;
} else{
currentNode = currentNode.right;
}
}
}
}
}
Это делает так, чтобы значение последнего добавленного значения помещалось в правильное место без переопределения старых значений.