Алгоритмы с нуля

Двоичные деревья поиска

Суть Двоичное дерево, где каждое значение в левом поддереве меньше узла и в правом больше. Это свойство порядка делает поиск и вставку O(h). Обход inorder даёт отсортированный порядок. Высота варьируется от O(log n) для сбалансированных до O(n) для вырожденных деревьев.

◷ 26 min

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

Цель

После этого урока вы сможете определить свойство BST (левое поддерево меньше, правое больше), реализовать поиск и вставку в BST, трассировать обе операции, чтобы проверить корректность, объяснить, почему обход в порядке inorder дерева поиска даёт отсортированный порядок, предсказать временную сложность поиска и вставки (O(h) где h — высота), и признать риск того, что несбалансированное дерево может выродиться до O(n) высоты.

Идея

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

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

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

Свойство BST (левое < узел < правое)

Для каждого узла:

Все значения в левом поддереве < значение узла.
Все значения в правом поддереве > значение узла.
Оба левое и правое поддеревья также являются BST-ами (свойство применяется рекурсивно).

Пример:

Здесь узел 5 имеет левое поддерево 4 (все < 5) и правое поддерево 9 (все > 5). Узел 3 имеет левое поддерево 1 (< 3) и правое поддерево 4 (> 3).

Поиск в BST

Чтобы найти значение:

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

На каждом шаге вы исключаете половину оставшегося дерева (или большую часть, если дерево не идеально сбалансировано). Это даёт O(h) сравнений, где h — высота.

Вставка в BST

Чтобы вставить значение:

Начните с корня.
Сравните значение с текущим узлом.
Если значение меньше, рекурсируйте влево; если больше, рекурсируйте вправо.
Когда вы достигнете null, это место, где вы прикрепляете новый лист.

Вставка также занимает O(h) времени, потому что вы должны найти место вставки, сравнивая на каждом уровне.

Обход в порядке inorder даёт отсортированный порядок

Обход в порядке inorder (левое, текущее, правое) BST посещает узлы в восходящем порядке. Это потому что:

Вы посещаете левое поддерево (все значения меньше узла).
Потом сам узел.
Потом правое поддерево (все значения больше узла).

Поэтому значения появляются в отсортированном порядке.

Высота критична

Времена поиска и вставки зависят от высоты h:

Сбалансированное дерево: высота O(log n), поэтому операции O(log n).
Вырожденное дерево (например, все левые дети): высота O(n), поэтому операции O(n).

Если вы вставляете значения в отсортированном порядке [1, 2, 3, 4, 5], дерево вырождается в связный список, и вы теряете логарифмическое-временное преимущество. Самобалансирующиеся деревья (AVL, красно-чёрные) сохраняют баланс, но они выходят за рамки этого урока.

Код

Пример 1: Поиск значения в BST


      1
      function search(node, target) {
    

      2
      // Базовый случай: значение не найдено
    

      3
      if (node === null) return false;
    

      4
       
    

      5
      // Проверь текущий узел
    

      6
      if (node.value === target) return true;
    

      7
       
    

      8
      // Рекурсируй влево если цель меньше
    

      9
      if (target < node.value) {
    

      10
        return search(node.left, target);
    

      11
      }
    

      12
       
    

      13
      // Рекурсируй вправо если цель больше
    

      14
      return search(node.right, target);
    

      15
      }

L1 Функция поиска: принимает узел и целевое значение.
L3 Базовый случай: если узел null, значение не было найдено.
L6 Если цель равна значению узла, мы нашли его.
L9 Если цель меньше, она может быть только в левом поддереве (свойство BST).
L10 Рекурсируй на левое поддерево.
L13 Иначе, цель должна быть больше, поэтому рекурсируй на правое поддерево.

Пример: Поиск 4 в дереве:

Начните с 5. Цель (4) < 5, идите влево.
На 3. Цель (4) > 3, идите вправо.
На 4. Цель (4) == 4, вернулась true.

Поиск занял 3 сравнения.

Пример 2: Вставка значения в BST


      1
      function insert(node, value) {
    

      2
      // Базовый случай: прикрепи новый узел здесь
    

      3
      if (node === null) {
    

      4
        return new Node(value);
    

      5
      }
    

      6
       
    

      7
      // Рекурсируй влево если значение меньше
    

      8
      if (value < node.value) {
    

      9
        node.left = insert(node.left, value);
    

      10
      }
    

      11
      // Рекурсируй вправо если значение больше
    

      12
      else if (value > node.value) {
    

      13
        node.right = insert(node.right, value);
    

      14
      }
    

      15
      // Игнорируй дубликаты (опционально; некоторые BST их позволяют)
    

      16
       
    

      17
      return node;
    

      18
      }

L1 Функция вставки: добавь значение в дерево с корнем node.
L3 Базовый случай: если узел null, создай и верни новый узел с этим значением.
L7 Если значение меньше текущего узла, оно принадлежит левому поддереву.
L8 Рекурсивно вставь в левое поддерево и обнови левого ребёнка.
L10 Если значение больше, оно принадлежит правому поддереву.
L12 Рекурсивно вставь в правое поддерево и обнови правого ребёнка.
L16 Верни (возможно обновленный) узел.

Пример: Вставить 6 в дерево:

Начните с 5. Значение (6) > 5, идите вправо.
На 8. Значение (6) < 8, идите влево.
На 7. Значение (6) < 7, идите влево.
На null. Создайте новый узел со значением 6.

Результат:

Вставка также заняла 4 шага (сравнения + навигация по дереву).

Запуск поиска и вставки на конкретном дереве

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

function search(node, target) {
if (node === null) return false;
if (node.value === target) return true;
if (target < node.value) return search(node.left, target);
return search(node.right, target);
}

function inorder(node, result = []) {
if (node === null) return result;
inorder(node.left, result);
result.push(node.value);
inorder(node.right, result);
return result;
}

// Построим дерево:
//      5
//     / \
//    3   8
//   / \ / \
//  1  4 7  9

let node1 = new Node(1);
let node4 = new Node(4);
let node3 = new Node(3, node1, node4);
let node7 = new Node(7);
let node9 = new Node(9);
let node8 = new Node(8, node7, node9);
let root = new Node(5, node3, node8);

console.log("Поиск 4:", search(root, 4));
console.log("Поиск 6:", search(root, 6));

// Вставим 6
root = insert(root, 6);
console.log("После вставки 6:");
console.log("Обход inorder:", inorder(root).join(", "));

Output

Пошаговый разбор


      1
      let root = new Node(5, new Node(3, new Node(1), new Node(4)), new Node(8, new Node(7), new Node(9)));
    

      2
      search(root, 4);


      1
      let root = new Node(5, new Node(3, new Node(1), new Node(4)), new Node(8, new Node(7), new Node(9)));
    

      2
      insert(root, 6);

Сложность

Временная сложность: поиск и вставка

Обе операции поиска и вставки проходят путь от корня к либо найденному узлу (поиск), либо к листу (вставка). Число сравнений равно глубине этого пути, что максимум — высота h дерева.

Лучший случай (сбалансированное дерево): Высота O(log n), поэтому поиск и вставка оба O(log n).
Средний случай (случайные вставки): Высота примерно O(log n), поэтому оба O(log n).
Худший случай (вырожденное дерево): Высота O(n) (дерево — связный список), поэтому оба O(n).

Для операций в коде этого урока (поиск и вставка), временная сложность — O(h), где h — высота.

Пространственная сложность

И поиск, и вставка используют рекурсию, поэтому глубина стека вызовов — O(h). Обход inorder также использует O(h) рекурсивную глубину.

Практика 0 / 5

Какое из этих деревьев удовлетворяет свойству BST?

Вы ищите значение 6 в этом BST. На каждом шаге, сколько узлов вы сравниваете?

Что производит обход в порядке inorder BST?

BST построен вставкой значений в этом порядке: [1, 2, 3, 4, 5]. Какова высота получившегося дерева?

В худшем случае (вырожденное BST), какова временная сложность поиска значения?

lesson.inset.undefined

Зачем BST? Неупорядоченные двоичные деревья позволяют вам ходить, но не искать эффективно. Если вы хотите искать без проверки каждого узла, вам нужна структура: упорядочение. Свойство BST даёт вам эту структуру. На каждом узле вы знаете, какое поддерево исследовать, поэтому вы сокращаете проблему (в сбалансированном дереве) на каждом шаге.

lesson.inset.undefined

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

lesson.inset.undefined

Путаница BST с гарантией отсортированного порядка. BST НЕ гарантирует, что стандартный обход дерева (как level-order) производит отсортированный порядок. Только обход inorder производит отсортированный порядок. Если вы хотите отсортировать последовательность, вы строите BST и обходите его inorder. Но BST — это не в первую очередь алгоритм сортировки — это динамическая структура данных для быстрого поиска.

Проверь себя

Викторина

Что такое свойство BST и почему оно позволяет быстрый поиск?

Итог

Двоичные деревья поиска организуют данные со свойством порядка: левое поддерево < узел < правое поддерево. Это свойство позволяет быстрый поиск и вставку за O(h) времени, где h — высота дерева. Для сбалансированного дерева h — это O(log n), делая операции логарифмическими. Обход в порядке inorder BST даёт значения в отсортированном порядке — следствие свойства порядка. Критическая оговорка: если дерево несбалансировано (вырожено), высота становится O(n), и все операции деградируют. Самобалансирующиеся деревья (AVL, красно-чёрные) сохраняют баланс автоматически, но они значительно более сложны и выходят за рамки этого урока. Следующий урок охватывает древовидное динамическое программирование — техники решения рекурсивных задач на деревьях с мемоизацией.

Продолжить восхождение ↑Динамическое программирование на деревьях