re:re:actable
Урок 023 минуты чтения

Что такое 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 нужно оговаривать.

Документация

Wikipedia: Binary search tree, VisuAlgo: BST.

Дочитали до конца?
Отметьте урок — прогресс сохранится в браузере.

Поиск

Поиск по урокам