Бинарное дерево поиска (BST)

Binary Search Tree (BST) — двоичное дерево, в котором для каждого узла все значения в левом поддереве меньше, а в правом — больше значения этого узла.

Зачем нужно

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

Где используется

  • Словари и множества в стандартных библиотеках (TreeMap, TreeSet в Java)
  • Базы данных: индексы на основе B-деревьев (обобщение BST)
  • Автодополнение: хранение отсортированных ключей
  • Алгоритмы, требующие in-order обхода за O(n)

Основной контент

Свойство BST

        8
       / \
      3   10
     / \    \
    1   6    14
       / \   /
      4   7 13

Для узла 8: все в левом < 8, все в правом > 8

Реализация

class BSTNode {
  constructor(val) {
    this.val = val;
    this.left = this.right = null;
  }
}

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

  // Вставка — O(log n) средн., O(n) худший
  insert(val) {
    const node = new BSTNode(val);
    if (!this.root) { this.root = node; return; }
    let cur = this.root;
    while (true) {
      if (val < cur.val) {
        if (!cur.left) { cur.left = node; return; }
        cur = cur.left;
      } else {
        if (!cur.right) { cur.right = node; return; }
        cur = cur.right;
      }
    }
  }

  // Поиск — O(log n) средн.
  search(val) {
    let cur = this.root;
    while (cur) {
      if (val === cur.val) return cur;
      cur = val < cur.val ? cur.left : cur.right;
    }
    return null;
  }

  // In-order обход — возвращает элементы в отсортированном порядке O(n)
  inOrder(node = this.root, result = ) {
    if (!node) return result;
    this.inOrder(node.left, result);
    result.push(node.val);
    this.inOrder(node.right, result);
    return result;
  }
}

const bst = new BST();
[8, 3, 10, 1, 6, 14, 4, 7, 13].forEach(v => bst.insert(v));
console.log(bst.inOrder); // [1, 3, 4, 6, 7, 8, 10, 13, 14]

Удаление узла

Три случая:

  1. Узел — лист: удалить напрямую.
  2. Узел имеет одного ребёнка: заменить узел ребёнком.
  3. Узел имеет двух детей: заменить наименьшим узлом правого поддерева (in-order successor).

Сложность

Операция Средний случай Худший случай
Поиск O(log n) O(n)
Вставка O(log n) O(n)
Удаление O(log n) O(n)
In-order O(n) O(n)

Худший случай — вырожденное дерево (все элементы вставлены по порядку). Решение — Балансировка деревьев.

Частые ошибки

  • Вставлять элементы в отсортированном порядке без балансировки — высота достигает O(n).
  • Путать поиск в BST с бинарным поиском в массиве: BST работает с любыми данными, но требует дополнительной памяти для указателей.
  • Не обрабатывать удаление узла с двумя детьми — самый сложный из трёх случаев.
  • Предполагать, что in-order обход всегда O(log n) — он всегда O(n), посещая каждый узел.

Связанные темы

Ресурсы