Двоичное дерево поиска — это особый тип двоичного дерева, в котором данные каждого правого дочернего узла больше, чем его родительский узел, а данные каждого левого дочернего узла меньше, чем его родительский узел.
Двоичное дерево поиска используется для выполнения операций поиска данных, поскольку оно может находить данные за время O (log (n)), что довольно эффективно. В BST выполняются следующие операции:
- Вставка
- Удаление
- Идет поиск
- Обходы
Вставка в BST выполняется с использованием следующих правил и шагов:
- Данные вставляются в корневой узел, если корневой узел имеет значение null.
- BST проходится от корневого узла таким образом, что следующий посещаемый узел остается, если вставляемые данные меньше, чем данные текущего узла, в противном случае он правильный.
- Наконец, новый узел вставляется слева от текущего узла, если его данные меньше, чем данные текущего узла, в противном случае он вставляется справа.
Удаление в BST выполняется по следующим правилам:
- Если удаляемый узел является конечным узлом, он становится нулевым.
- Если удаляемый узел имеет только одного дочернего элемента, он заменяется этим дочерним элементом.
- В противном случае узел заменяется наименьшим узлом данных из его правого поддерева.
Поиск выполняется путем обхода BST таким образом, что:
- Если текущее значение узла равно искомому значению, вернуть true.
- Если искомое значение меньше значения текущего узла, следующий посещаемый узел находится слева от текущего узла, в противном случае — справа.
Обходы BST бывают трех видов:
- По порядку: сначала проходится левый узел, затем корень, а затем правый.
- Пост-порядок: сначала проходится левый узел, затем правый, а затем корень.
- Предварительный порядок: сначала проходится корневой узел, затем левый, а затем правый.
Вот полная реализация кода JavaScript для двоичного дерева поиска.
Обход по порядку в BST всегда будет возвращать массив, содержащий данные узлов в отсортированном порядке.