Что такое binary search tree?
На этой странице
Binary Search Tree, BST, - бинарное дерево, где для каждого узла значения слева меньше, а значения справа больше. Это позволяет искать, вставлять и удалять элементы в среднем за O(log n), если дерево сбалансировано.
Вопрос
Что такое binary search tree и почему без балансировки он может выродиться?
Правило BST
left subtree < node < right subtreeДля каждого узла, не только для root.
8
/ \
3 10
/ \ \
1 6 14Поиск 6: 6 < 8 - идем влево, 6 > 3 - идем вправо, нашли. На каждом шаге отбрасываем целое поддерево, как половину массива в binary search.
А вот это дерево - не BST, хотя каждый узел правильно расположен относительно своих детей:
8
/
3
\
9 <- 9 в левом поддереве 8, а должен быть меньше 8Поиск
type TreeNode = {
value: number
left: TreeNode | null
right: TreeNode | null
}
function search(root: TreeNode | null, target: number): TreeNode | null {
let current = root
while (current) {
if (current.value === target) return current
current = target < current.value ? current.left : current.right
}
return null
}Вставка
function insert(root: TreeNode | null, value: number): TreeNode {
if (!root) return { value, left: null, right: null }
if (value < root.value) root.left = insert(root.left, value)
else root.right = insert(root.right, value)
return root
}Новое значение всегда становится листом: спускаемся, как при поиске, и подвешиваем узел в первое пустое место.
Сложность
Balanced BST:
O(log n)Degenerate tree:
O(n)Если дерево превратилось в список, преимуществ почти нет. Так происходит, если вставлять уже отсортированные значения 1, 2, 3, 4:
1
\
2
\
3
\
4Высота стала n, и поиск идет по всем узлам. Самобалансирующиеся деревья (AVL, red-black) после вставки перестраиваются, чтобы высота оставалась O(log n), - их обычно не пишут на собеседовании, но идею стоит знать.
Проверка BST
function isValidBST(root: TreeNode | null, min = -Infinity, max = Infinity): boolean {
if (!root) return true
if (root.value <= min || root.value >= max) return false
return (
isValidBST(root.left, min, root.value) &&
isValidBST(root.right, root.value, max)
)
}Что отвечать на собеседовании?
BST - binary tree с порядковым invariant: все значения слева меньше текущего, справа больше. Если дерево сбалансировано, поиск/вставка/удаление занимают O(log n). В худшем случае несбалансированное BST становится похожим на linked list и операции деградируют до O(n).
Что важно помнить: частые ошибки
- Проверять только прямых детей, а не весь диапазон subtree.
- Не учитывать duplicates.
- Считать BST всегда balanced.
- Не понимать inorder traversal.
- Забывать worst case
O(n).
Мини-шпаргалка
- Left < node < right.
- Inorder дает sorted order.
- Balanced ->
O(log n). - Worst ->
O(n). - Validate через min/max.
- Duplicates нужно оговаривать.