Прежде всего, мы спрашиваем себя, что такое дерево?

Дерево — это то, что вы на самом деле считаете деревом, с корнем в качестве ядра. По мере того, как корень растет, он вырастает из ствола, из которого вырастают ветви, а из этих ветвей вырастают другие ветви.

Если вы посмотрите на Рис. 0, вы увидите корень внизу, который растет в то, что мы называем стволом, и эти стволы вырастают из ветвей, которые вырастают из ветвей, и у нас есть листья (не обращайте внимания на листья) для сейчас, поскольку мы коснемся этого позже.

В реальном программировании это то, как выглядит дерево

Как видно на рис. 1, у нас есть корень под номером 2, который находится не внизу, как настоящее дерево, а вверху, и по мере роста дерева он растет вниз по сравнению с к реальным деревьям жизни, которые растут вверх. Когда дерево растет, оно вырастает из ветвей, которые, в свою очередь, вырастают из большего количества ветвей по мере того, как Дерево становится больше в размерах.

В бинарных деревьях поиска есть разница.

Двоичные деревья поиска отличаются тем, что корень в этом случае 41 начинается с всего двух ветвей 20, 65 и по мере роста Дерева ветви не могут иметь более двух ветвей.

На буквальном языке программирования мы имеем в виду, что

Корень — это верхний узел дерева, а две его ветви — дочерние узлы.

По мере того, как эти дочерние элементы растут, они буквально становятся родителем двух ветвей, из которых он вырастает (см. рис. 4). Помните, что у каждого родителя не может быть более двух детей.

Что делать, если родитель не хочет иметь детей, как называется это явление? Ну, я предполагаю, что это был бы лист, потому что, если вы помните, в нашем графическом изображении Дерева на Рис. 0, когда ветви заканчивали расти, из них вырастали листья, то есть чтобы показать там больше не является ветвью, но в BSTS мы не включаем лист, а удаляем коннектор, чтобы показать, что родитель не подключается ни к какой ветке, как на рис. 4, где дочерние элементы не имеют коннекторов, соединяющихся с следующая ветка.

Еще одна вещь, которую следует отметить в BSTS, это то, что здесь мы строим ветви от корня, глядя на рис. 4, на основе левой и правой стороны корня, так же, как родитель и потомки, как дерево растет.

Если вы внимательно посмотрите на рис. 4, вы заметите закономерность с этими числами, и вы увидите, что левая ветвь, родитель, является числом, меньшим, чем корень. > и правая ветвь на число больше, чем корень, и по мере роста дерева у родителей будет две ветви, которые будут дочерними. Дочерний элемент левой ветви будет на число меньше, чем родительский, так же как и дочерний элемент правой ветви и так далее.

Вот как BSTS используется для размещения элементов или, скажем, чисел в своей структуре.

Что, если мы хотим добавить ветки, в буквальном смысле программирования, что мы имеем в виду, что, если мы хотим вставить узлы в дерево?

Мы должны определить класс узла с конструктором, в который будет передаваться значение параметра. Класс узла также будет иметь еще два свойства слева и справа, чтобы обозначить позицию, в которой растет ветвь, и они будут установлены в нуль, потому что мы предполагают, что ветка еще не растет.

мы также должны определить класс BST, который будет иметь конструктор, внутри конструктора будет корневое свойство для отслеживания первого значения, вставляемого в дерево, и оно установлено равным нулю, потому что на данный момент мы просто конструируем дерево, и в данный момент оно пусто. Вне конструктора у нас будет свойство вставки, которое будет принимать значение параметра, которое будет использоваться для построения дерева.

Чтобы добавить новые значения, которые будут использоваться для построения дерева, мы должны определить класс BST, используя ключевое слово new, которое будет храниться в переменной bst, тогда мы имеем для вызова метода вставки в классе BST с помощью свойства точки переменной bst

Теперь начнем с функциональности вставки

Точно так же, как мы определили класс BST ранее, мы делаем то же самое с узлом, который представляет ветвь, которую мы создаем для свойства и его свойств, глядя на рис. 5.Затем мы передаем значение параметра в нашем методе вставки в узел, чтобы создать узел для нашего дерева.

Мы должны проверить, есть ли в дереве корень, потому что, если вы помните ранее, взглянув на рис. 6, для нашего корневого свойства установлено значение null. Если установлено значение null, мы должны установить в качестве корня узел, который мы создали, глядя на рис. 8, чтобы наше дерево могло иметь корень, потому что нет дерева без корня.

что, если корень был создан, и мы хотим добавить в дерево еще один узел, который будет ветвью? если вы помните, на рис. 4 была схема, где числа слева были числами меньше корня, а числа справа были числами больше корня, поэтому мы должны принять это учитывать при добавлении узлов в дерево.

Итак, что мы делаем, так это создаем переменную с именем current, которая содержит корень и будет использоватьсядля отслеживания наших узлов при добавлении чисел. в деревья.

Когда мы хотим вставить в деревья, мы должны использовать цикл, чтобы мы могли постоянно добавлять числа столько, сколько нам нужно, и этот цикл будет использоваться для обновления текущего узла, который вставляется в дерево. дерево, которое, как мы сказали ранее, имеет root по умолчанию, и по мере роста дерева нам нужно обновлять current.

нам нужен оператор if, который будет использоваться для сравнения значений, добавляемых в дерево, с текущим значением, которое обновляется циклом while после каждой проверки. Нам также нужно проверить, есть ли свойство left в нашем узле, потому что, когда мы определяли наш узел, свойства left и right были установлены в null, поскольку мы предполагали, что при определении класса узла не было дерева. также current = current.left используется в качестве базового случая для цикла while, поэтому, когда свойство left текущего узла равно null, это означает, что новое значение не вставляется, цикл завершается, так как на следующей итерации он вернет false.

Точно так же, как мы сделали для левого свойства, то же самое можно сказать и для правого свойства.

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

Теперь начнем с функции поиска

что, если мы хотим получить узел из дерева, мы можем использовать метод find для вызова метода find, мы должны вызвать метод find в классе BST, используя свойство точки в переменной, как на рис. 7 и мы передаем переменную, которую ищем в дереве, в метод find.

В методе find внутри нашего BST-класса мы сначала проверяем, есть ли корень в дереве, потому что мы должны знать, есть ли корень или нет, поскольку дерево без корня означало бы, что нет ветви.

Затем, как мы делали ранее, мы должны сохранить корень в созданной нами переменной с именем current, это будет содержать наш текущий узел в дереве, так как нам нужно будет использовать цикл для навигации по дереву.

при зацикливании текущего узла мы должны проверить, равно ли текущее значение значению, переданному в наш метод поиска. Если это так, мы должны вернуть текущий.

что, если это не так, как и при вставке узлов в дерево, мы должны проверить, меньше ли значение, переданное в наш метод поиска, чем текущее значение или больше, чем текущее значение. Если это так, мы должны обновить текущее значение, чтобы, когда оно проверяет, равно ли оно текущему значению, возвращалось текущее значение.

когда после выполнения поиска нет значения, цикл while завершается и возвращается значение undefined

Итак, вот полный код всего алгоритма BST.

class Node {
    constructor(value){
        this.value = value;
        this.left = null;
        this.right = null;
    }
}

class BST {
    constructor(){
        this.root = null;
    }

    insert(val){
        const newNode = new Node(val);
        if(!this.root){
            this.root = newNode;
        }else{
            let current = this.root;
            while(current){
                if(val === current.value) return undefined;
                if(val < current.value){
                    if(!current.left){
                        current.left = newNode;
                        return this;
                    }
                    current = current.left;
                }else{
                    if(!current.right){
                        current.right = newNode;
                        return this;
                    }
                    current = current.right;
                }
            }
        }
    }

    find(val){
        if(!this.root) return undefined;
        let current = this.root;
        while(current){
            if(current.value === val){
                return current;
            }else if (val < current.value){
                current = current.left;
            }else if(val > current.value) {
                current = current.right;
            }
        }
        return undefined;
    }
}


const bst = new BST();

bst.insert(10);
bst.insert(5);
bst.insert(2);
bst.insert(12);
bst.insert(6);
bst.insert(7);

bst.find(10);

БОЛЬШОЕ ОБОЗНАЧЕНИЕ O ДЛЯ BST

для вставки это O(logN)

для поиска это O(logN)

Это не гарантируется, потому что, скажем, у нас есть одна ветвь по всему дереву вместо двух ветвей, поскольку мы знаем, что действительный BST может иметь одну ветвь, потому что, если вы помните ранее, наш предел количества ветвей, которые может иметь родитель, равен двум, поэтому имея одну филиал не нарушает это правило.

Когда идет поиск, посмотрите на рис. 18, по мере того, как мы перемещаемся вниз, чтобы найти значение 20, выполняется пять циклов, чтобы добраться до числа 20, а затем представьте, что теперь произойдет, если у нас будет миллион ветвей для циклического прохождения? Вот почему было бы лучше разбить его на две ветви, так как это уменьшит количество циклов, если мы будем перебирать много ветвей в дереве.

Заключение

BST можно использовать в

  • ДОМ
  • сетевая маршрутизация
  • Абстрактные синтаксические деревья.
  • Искусственный интеллект, например игра MinMax, такая как TicTacToe.
  • папки в операционных системах
  • компьютерные файловые системы