Двоичные деревья — это структура данных, которая позволяет нам эффективно хранить и обновлять данные, сохраненные в наборе данных. Эти типы деревьев имеют не более двух дочерних элементов и следуют правилу, которое определяет, на какой стороне набора данных будет сохранена информация. Временная сложность вставки или поиска фрагмента данных в дереве составляет 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;
             }
         }
      }
   }
}

Это делает так, чтобы значение последнего добавленного значения помещалось в правильное место без переопределения старых значений.