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

Двоичное дерево поиска используется для выполнения операций поиска данных, поскольку оно может находить данные за время O (log (n)), что довольно эффективно. В BST выполняются следующие операции:

  • Вставка
  • Удаление
  • Идет поиск
  • Обходы

Вставка в BST выполняется с использованием следующих правил и шагов:

  • Данные вставляются в корневой узел, если корневой узел имеет значение null.
  • BST проходится от корневого узла таким образом, что следующий посещаемый узел остается, если вставляемые данные меньше, чем данные текущего узла, в противном случае он правильный.
  • Наконец, новый узел вставляется слева от текущего узла, если его данные меньше, чем данные текущего узла, в противном случае он вставляется справа.

Удаление в BST выполняется по следующим правилам:

  • Если удаляемый узел является конечным узлом, он становится нулевым.
  • Если удаляемый узел имеет только одного дочернего элемента, он заменяется этим дочерним элементом.
  • В противном случае узел заменяется наименьшим узлом данных из его правого поддерева.

Поиск выполняется путем обхода BST таким образом, что:

  • Если текущее значение узла равно искомому значению, вернуть true.
  • Если искомое значение меньше значения текущего узла, следующий посещаемый узел находится слева от текущего узла, в противном случае — справа.

Обходы BST бывают трех видов:

  • По порядку: сначала проходится левый узел, затем корень, а затем правый.
  • Пост-порядок: сначала проходится левый узел, затем правый, а затем корень.
  • Предварительный порядок: сначала проходится корневой узел, затем левый, а затем правый.

Вот полная реализация кода JavaScript для двоичного дерева поиска.

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