BST: бинарное дерево с порядком

Binary Search Tree (BST) — это бинарное дерево с одним дополнительным инвариантом:

Для каждого узла N: все ключи в left subtree < N.value < все ключи в right subtree.

Этот простой инвариант даёт три ключевых свойства:

1. Поиск за O(log n) в сбалансированном дереве — двигаемся всегда в правильную сторону.
2. In-order обход даёт отсортированный поток ключей.
3. Range queries работают быстро: найди все ключи в [10, 50] — обход поддерева.

BST — основа B-tree (и B+-tree), которые в свою очередь — основа всех реляционных индексов. Понять BST — значит понять, как работает CREATE INDEX.

Пример BST

            (50)
           /    \
         (30)   (70)
         /  \    /  \
       (20)(40)(60)(80)
       /     \
     (10)   (45)

Проверим инвариант:

• Для 50: left subtree 45 — все < 50. Right 80 — все > 50. [ok]
• Для 30: left 20 < 30, right 45 > 30. [ok]
• И так далее для каждого узла.

In-order обход: 10, 20, 30, 40, 45, 50, 60, 70, 80 — отсортировано.

Структура и операции

class BSTNode:
    def __init__(self, key):
        self.key = key
        self.left = None
        self.right = None

class BST:
    def __init__(self):
        self.root = None

    def search(self, key):
        return self._search(self.root, key)

    def _search(self, node, key):
        if node is None:
            return None
        if key == node.key:
            return node
        if key < node.key:
            return self._search(node.left, key)
        return self._search(node.right, key)

    def insert(self, key):
        self.root = self._insert(self.root, key)

    def _insert(self, node, key):
        if node is None:
            return BSTNode(key)
        if key < node.key:
            node.left = self._insert(node.left, key)
        elif key > node.key:
            node.right = self._insert(node.right, key)
        # если key == node.key, ничего не делаем (или обновляем)
        return node

Search: путь сверху вниз

Поиск ключа в BST — это спуск по дереву, где на каждом шаге мы выбираем direction по сравнению key vs node.key:

поиск 45 в дереве выше:
50 -> 45 < 50, идём в left
30 -> 45 > 30, идём в right
40 -> 45 > 40, идём в right
45 -> нашли!

Это 3 шага для 9-узлового дерева. В general случае search делает O(h) шагов, где h — высота дерева.

def search(node, key):
    while node:
        if key == node.key:
            return node
        node = node.left if key < node.key else node.right
    return None

Insert: дойти до конца, прицепить

Вставка работает аналогично — спускаемся, пока не найдём пустое место:

def insert(node, key):
    if node is None:
        return BSTNode(key)
    if key < node.key:
        node.left = insert(node.left, key)
    elif key > node.key:
        node.right = insert(node.right, key)
    return node

# для itererative:
def insert_iter(root, key):
    if root is None:
        return BSTNode(key)
    cur = root
    while True:
        if key < cur.key:
            if cur.left is None:
                cur.left = BSTNode(key)
                return root
            cur = cur.left
        elif key > cur.key:
            if cur.right is None:
                cur.right = BSTNode(key)
                return root
            cur = cur.right
        else:
            return root   # уже есть, ничего не делаем

Также O(h) — спускаемся по высоте дерева.

Delete: три случая

Удаление сложнее. Три случая:

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

def delete(node, key):
    if node is None:
        return None
    if key < node.key:
        node.left = delete(node.left, key)
    elif key > node.key:
        node.right = delete(node.right, key)
    else:
        # нашли узел для удаления
        if node.left is None:
            return node.right
        if node.right is None:
            return node.left
        # 2 детей: найдём in-order successor
        successor = node.right
        while successor.left:
            successor = successor.left
        node.key = successor.key
        node.right = delete(node.right, successor.key)
    return node

Сложность операций

Когда BST вырождается: skewed tree

BST не балансируется автоматически. Если вставлять ключи в отсортированном порядке, получите вырожденное дерево (skewed) — фактически связный список:

bst = BST()
for i in range(10):
    bst.insert(i)

# получившееся "дерево":
#  0
#   \
#    1
#     \
#      2
#       \
#        3
#         \
#          ...

Каждая вставка идёт в right child, потому что новый ключ всегда больше предыдущего. Высота = N - 1. Search и insert деградируют до O(N).

# измерим худший случай
import time

bst = BST()
n = 10_000

# вставка в отсортированном порядке — skewed
start = time.perf_counter()
for i in range(n):
    bst.insert(i)
t_skewed = time.perf_counter() - start

# вставка в случайном порядке — почти balanced
import random
keys = list(range(n))
random.shuffle(keys)
bst2 = BST()
start = time.perf_counter()
for k in keys:
    bst2.insert(k)
t_random = time.perf_counter() - start

print(f"skewed insert: {t_skewed*1000:.0f} ms")    # ~3-5 секунд
print(f"random insert: {t_random*1000:.0f} ms")    # ~30-50 мс
print(f"ratio: {t_skewed/t_random:.0f}x")           # 50-100×

При n=10000 разница в 50-100 раз. При n=100000 — 500-1000 раз. Это и есть катастрофическая деградация.

Почему случайные данные дают почти balanced дерево

Это удивительный факт: если вставлять N ключей в случайном порядке, BST имеет высоту O(log N) в среднем (с малой константой ~1.4).

Интуиция: первый ключ становится root, дальше вероятность каждого ключа попасть в left или right subtree пропорциональна размеру субдерева. На случайных данных распределение примерно равномерное, и дерево саморасчищается.

случайные вставки 1..15: 
получаем дерево с h ≈ 4 (вместо 14 для отсортированных)

Но в реальной жизни данные часто не случайны. ID растёт монотонно. Timestamp растёт монотонно. Если просто insert по ID — получите skewed дерево.

BST не сохраняет порядок сам по себе

Важная тонкость: BST хранит ключи в порядке поиска, не вставки. Чтобы получить отсортированный вывод, нужен in-order traversal. Если хотите порядок вставки — нужна отдельная структура (например, dict).

bst = BST()
for k in [3, 1, 4, 1, 5, 9, 2, 6]:
    bst.insert(k)

# in-order даст отсортированно:
# 1, 2, 3, 4, 5, 6, 9

BST vs hash-таблица

В чём преимущество BST перед hash-таблицей, если hash O(1) против BST O(log N)?

BST выигрывает там, где нужен порядок:

• Range queries в БД: WHERE id BETWEEN 100 AND 200. B-tree индекс позволяет найти 100, потом обойти его поддерево, пока не достигнем 200.
• ORDER BY: in-order обход даёт отсортированный результат без отдельной сортировки.
• min/max queries: спустимся в самый левый/правый узел.
• next/prev: в B-tree индексе можно эффективно найти «следующий ключ после X».

Hash для всего этого бесполезен — он не знает о порядке.

Применения в DE

B-tree индексы в реляционных БД

PostgreSQL/MySQL/Oracle используют B-tree (или B+-tree), который является обобщением BST: каждый узел имеет до сотен детей. Высота B-tree на миллиарде записей — 4-5 уровней. Lookup — 4-5 disk seek’ов.

CREATE INDEX idx_user_id ON events(user_id);

-- быстро: O(log N) — спускаемся по индексу
SELECT * FROM events WHERE user_id = 12345;

-- ещё быстро: range query
SELECT * FROM events WHERE user_id BETWEEN 100 AND 200;

-- быстро: in-order обход индекса
SELECT * FROM events ORDER BY user_id LIMIT 100;

sortedcontainers.SortedDict в Python

Стандартная Python dict — hash. Для sorted-словаря используется sortedcontainers.SortedDict, который держит ключи в отсортированном порядке. Внутри — не классический BST, а sorted list of lists, но интерфейс BST’шный:

from sortedcontainers import SortedDict

sd = SortedDict()
sd[3] = 'c'
sd[1] = 'a'
sd[2] = 'b'

print(list(sd))            # [1, 2, 3] — отсортированно
print(sd.irange(2, 3))     # [2, 3] — range query

Попробуй сам

class BSTNode:
    def __init__(self, key):
        self.key = key
        self.left = None
        self.right = None

class BST:
    def __init__(self):
        self.root = None
        self.size = 0

    def insert(self, key):
        if self.root is None:
            self.root = BSTNode(key)
            self.size += 1
            return
        cur = self.root
        while True:
            if key < cur.key:
                if cur.left is None:
                    cur.left = BSTNode(key)
                    self.size += 1
                    return
                cur = cur.left
            elif key > cur.key:
                if cur.right is None:
                    cur.right = BSTNode(key)
                    self.size += 1
                    return
                cur = cur.right
            else:
                return   # уже есть

    def search(self, key):
        cur = self.root
        while cur:
            if key == cur.key:
                return cur
            cur = cur.left if key < cur.key else cur.right
        return None

    def in_order(self):
        result = []
        def helper(node):
            if not node:
                return
            helper(node.left)
            result.append(node.key)
            helper(node.right)
        helper(self.root)
        return result

    def height(self):
        def h(node):
            if not node:
                return -1
            return 1 + max(h(node.left), h(node.right))
        return h(self.root)

# 1. Постройте BST и проверьте in-order даёт отсортированно
bst = BST()
for k in [50, 30, 70, 20, 40, 60, 80, 10, 45]:
    bst.insert(k)

print(bst.in_order())   # [10, 20, 30, 40, 45, 50, 60, 70, 80]
print(f"height = {bst.height()}")   # 3

# 2. Сравните skewed vs random
import time
import random

n = 5000

bst_skewed = BST()
start = time.perf_counter()
for i in range(n):
    bst_skewed.insert(i)
t_skewed = time.perf_counter() - start

keys = list(range(n))
random.shuffle(keys)
bst_random = BST()
start = time.perf_counter()
for k in keys:
    bst_random.insert(k)
t_random = time.perf_counter() - start

print(f"skewed: {t_skewed*1000:.0f} ms, height = {bst_skewed.height()}")
print(f"random: {t_random*1000:.0f} ms, height = {bst_random.height()}")
print(f"ratio: {t_skewed/t_random:.0f}x")

# Ожидаемо:
# skewed: height ~= 5000-1, очень медленно
# random: height ~= 25-30, быстро

# 3. Range query: все ключи в диапазоне [start, end]
def range_query(node, start, end, result):
    if not node:
        return
    if node.key >= start:
        range_query(node.left, start, end, result)
    if start <= node.key <= end:
        result.append(node.key)
    if node.key <= end:
        range_query(node.right, start, end, result)

result = []
range_query(bst_random.root, 100, 200, result)
print(f"Keys in [100, 200]: {sorted(result)[:10]}... ({len(result)} total)")

В следующем уроке — balanced trees: AVL, red-black, B-tree (упомянем). Поймём, почему именно эти структуры выбрали для индексов в БД и где у них есть слабости.