Дерево поиска (BST)

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

BST (Binary Search Tree) — бинарное дерево с правилом упорядочивания: для любого узла все значения слева меньше его, все справа — больше. Это правило позволяет искать как в бинарном поиске: на каждом шаге отбрасываем половину дерева. Поиск, вставка и удаление — в среднем O(log n).

Поиск идёт по одной ветке: сравнили с узлом и сразу решили, в какую половину спускаться. Для сбалансированного дерева высота ≈ log n, поэтому и поиск O(log n) — гораздо быстрее линейного перебора спискаИзменяемая упорядоченная коллекция элементов: [1, 2, 3]. По-английски list..

Вставка в BST

Вставка следует тому же правилу: спускаемся влево или вправо, пока не найдём пустое место, и подвешиваем новый узел туда. Так дерево остаётся упорядоченным.

Высота окажется 5 — дерево превратилось в цепочку, потому что каждое следующее число больше предыдущего и уходит только вправо. Это наглядно показывает, почему важна сбалансированность.

⚠️ Частые ошибки новичков

Ошибка. При вставке забыть вернуть узел (return node) и не присвоить результат обратно (node.left = insert(...)). Тогда новые узлы «теряются» — дерево не меняется. Рекурсивная вставка должна возвращать поддерево и пере-привязывать его. Запустите сломанный код: дерево останется из одного узла.