Что такое бинарное дерево поиска?

Бинарное дерево поиска (Binary Search Tree, BST) — это особый вид бинарного дерева данных, в котором каждый узел содержит ключ (значение), и для каждого узла выполняется следующее свойство:

• Ключи всех узлов в левом поддереве меньше ключа данного узла.
• Ключи всех узлов в правом поддереве больше ключа данного узла.
• Левое и правое поддеревья также являются бинарными деревьями поиска.

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

Пример узла:

class Node {
  constructor(value) {
    this.value = value; // Ключ узла
    this.left = null;   // Ссылка на левого потомка
    this.right = null;  // Ссылка на правого потомка
  }
}

Основные операции:

• Поиск: Начинается с корня. Если искомое значение меньше ключа текущего узла, переходим в левое поддерево; если больше — в правое; если равно — найден.
• Вставка: Аналогично поиску, но когда достигается подходящее место (null), создается новый узел.
• Удаление: Наиболее сложная операция. Зависит от количества потомков удаляемого узла (0, 1 или 2). При удалении узла с двумя потомками обычно заменяется наименьшим элементом из правого поддерева или наибольшим из левого.

Бинарные деревья поиска используются для создания словарей, множеств и для эффективной сортировки данных (сортировка деревом). Для поддержания сбалансированности и гарантии логарифмического времени операций используются самобалансирующиеся варианты, такие как AVL-деревья или красно-черные деревья.