Зачем балансировать

В прошлом уроке мы видели: naive BST на отсортированных данных деградирует до O(N). Это делает его непригодным для production. Решение — balanced BST: специальные алгоритмы, которые при каждой вставке/удалении локально перестраивают дерево, чтобы держать высоту O(log N).

Три главных семейства balanced trees, которые встретятся в реальной работе:

1. AVL — самая строгая балансировка, теоретически идеальная высота.
2. Red-black — слабее AVL, проще в реализации, используется в Linux kernel, Java TreeMap.
3. B-tree (и B+-tree) — для disk-based индексов, основа всех реляционных БД.

В этом уроке посмотрим на каждое семейство, поймём идею rotations (главного приёма) и сравним их. Глубокие реализации — это отдельный курс; нам важно знать названия, идеи и где они применяются.

Идея: rotations

Все balanced trees используют локальные rotations — поворот, который сохраняет BST-инвариант, но меняет форму дерева.

left rotation на узле X:
       X                Y
        \              / \
         Y     -->    X   Z
          \
           Z

right rotation на узле Y:
       Y                X
      / \                \
     X   Z   -->          Y
                           \
                            Z

Rotation:

• Сохраняет BST-инвариант (если был валидным, остаётся валидным).
• Изменяет высоту локально на ±1.
• Стоит O(1) — пара переустановок указателей.

Balanced trees вставляют ключ как в обычном BST, потом по пути обратно к root проверяют локальный баланс и делают rotation’ы, если нужно. Это даёт O(log N) на одну вставку с поддержанием баланса.

AVL tree

Самое строгое определение балансировки. Для каждого узла:

|height(left subtree) - height(right subtree)| <= 1

Если после вставки/удаления баланс нарушен, выполняется одна из 4 rotation’ов (LL, LR, RL, RR — по типу нарушения). Все за O(1).

Свойства AVL:

• Высота гарантированно ≤ 1.44 * log2(N + 2). Очень близко к теоретическому минимуму.
• Search, insert, delete — O(log N) worst case (не just average).
• Достаточно сложно в реализации.

Применение: AVL встречается в редакторских курсах по DSA. В прод-коде чаще используют red-black trees из-за simpler implementation.

Red-black tree

Более слабая балансировка, но проще:

• Каждый узел красный или чёрный.
• Корень всегда чёрный.
• Никаких двух красных подряд.
• Каждый путь от root до листа имеет одинаковое число чёрных узлов.

Из этих правил следует: высота дерева ≤ 2 * log2(N + 1). Чуть хуже AVL, но всё ещё O(log N).

Свойства red-black:

• Высота: O(log N), константа чуть хуже AVL.
• Search, insert, delete — O(log N) worst case.
• Меньше rotation’ов при insert/delete — лучше для write-heavy.

Применение:

• Linux kernel: epoll, scheduler, ext3/ext4 directory.
• Java TreeMap / TreeSet: внутри red-black.
• C++ std::map / std::set: обычно red-black.
• Rust BTreeMap: используют B-tree (не red-black), но с похожей логикой.

B-tree и B+-tree

В отличие от AVL/red-black (бинарные деревья), B-tree — это многоарное дерево: каждый узел может иметь сотни детей.

node-arity (например 100):
- каждый узел хранит до 100 ключей
- имеет до 101 child указателей
- ключи в узле отсортированы

высота B-tree с N записями: log_100(N) — то есть для N=1M высота ~3
для N=1B высота ~4-5

Это дизайн для disk-based индексов. Логика:

1. Disk reads дороги (миллисекунды vs наносекунды для CPU).
2. Лучше прочитать один большой узел (4-16 KB) за раз, чем много маленьких.
3. Уменьшить число disk seek’ов = уменьшить высоту дерева.

PostgreSQL/MySQL/Oracle используют B-tree (или B+-tree, вариант с listами в листьях) для всех индексов. Высота индекса на миллиарде записей — 4-5 уровней. Lookup = 4-5 disk seek’ов = ~50ms.

B+-tree — модификация: все данные в листьях, листья связаны в linked list для эффективного range scan’а.

Почему hash обычно быстрее BST

В большинстве случаев hash-таблица быстрее BST. Причины:

Главные причины hash быстрее:

1. Cache locality: open addressing хранит данные в массиве, BST — узлы в случайных местах heap’а.
2. Меньше операций per lookup: hash — 1 хеш + 1-2 проверки eq, BST — log N сравнений с навигацией по указателям.
3. Без перебалансировки: hash при resize дешевле, чем balanced tree.

Hash проигрывает только когда нужен порядок. Это и определяет выбор: hash для point-lookup, BST для ordered operations.

Range query — главный use-case BST

Range query — это «найти все ключи в диапазоне [low, high]». Это операция, для которой BST идеален:

def range_query(node, low, high, result):
    if node is None:
        return
    # если левая часть может содержать ключи >= low
    if node.key > low:
        range_query(node.left, low, high, result)
    # сам узел в диапазоне
    if low <= node.key <= high:
        result.append(node.key)
    # если правая часть может содержать ключи <= high
    if node.key < high:
        range_query(node.right, low, high, result)

Сложность: O(log N + k), где k — размер результата. log N — спуститься до начала диапазона, потом k — обойти найденные узлы.

В hash-таблице это невозможно сделать быстрее O(N) — нужно пройти все ключи и проверить каждый. На миллиарде записей это разница между мс и часами.

-- range query в SQL
-- использует B-tree индекс на created_at
SELECT * FROM events 
WHERE created_at BETWEEN '2025-01-01' AND '2025-01-31'
ORDER BY created_at;

-- БД находит первый ключ '2025-01-01' за O(log N) спуском по индексу
-- затем обходит индекс в-order, пока не достигнет '2025-01-31'

ordered iteration

Если вам нужно проитерировать все записи в отсортированном порядке, BST даёт это за O(N) через in-order traversal:

def in_order(node, result):
    if node is None:
        return
    in_order(node.left, result)
    result.append(node.key)
    in_order(node.right, result)

В hash-таблице нужен O(N) обход + O(N log N) сортировка = O(N log N).

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

B-tree индексы — везде в БД

Любой CREATE INDEX в PostgreSQL/MySQL/Oracle создаёт B-tree (default). Это используется для:

• Equality queries (WHERE id = 42).
• Range queries (WHERE created_at > '2025-01-01').
• ORDER BY на этой колонке.
• min/max через SELECT MIN(col) FROM t.

Hash-индексы тоже бывают, но они уступают B-tree по гибкости (только equality, не range).

Sorted-структуры в Python

• sortedcontainers.SortedDict / SortedSet / SortedList — production-ready, использует sorted list of lists (не классический BST), но интерфейс BST’шный.
• bisect модуль — для sorted list, бинарный поиск за O(log N), вставка O(N) (нужно сдвигать). Дёшево если редкая вставка, частый поиск.
• heapq — это heap (см. модуль 11), не BST.

LSM-trees в NoSQL

RocksDB, Cassandra, LevelDB используют LSM-tree (Log-Structured Merge tree) — это не BST в классическом смысле, а серия отсортированных файлов с background-merge. Но идея «keep data sorted for range queries» та же.

Когда BST лучше hash

Резюме:

1. Нужны range queries (SELECT WHERE col BETWEEN ... AND ...).
2. Нужна ordered iteration (ORDER BY col).
3. Нужны min/max queries.
4. Нужны predecessor/successor.
5. Нужны pagination через cursor (key-based, не offset-based — миллион раз эффективнее на больших данных).

В остальных случаях — hash. Поэтому в Python стандартный dict это hash, а sorted-map это отдельная библиотека.

Эксперимент: hash vs sortedcontainers

import time
from sortedcontainers import SortedDict

n = 100_000

# 1. Hash-словарь (dict)
d = {}
start = time.perf_counter()
for i in range(n):
    d[i] = i
t_dict_insert = time.perf_counter() - start

# 2. SortedDict
sd = SortedDict()
start = time.perf_counter()
for i in range(n):
    sd[i] = i
t_sd_insert = time.perf_counter() - start

# lookup
start = time.perf_counter()
for i in range(n):
    _ = d[i]
t_dict_lookup = time.perf_counter() - start

start = time.perf_counter()
for i in range(n):
    _ = sd[i]
t_sd_lookup = time.perf_counter() - start

# range query [50000, 60000]
# для dict это full scan + filter
start = time.perf_counter()
result = [v for k, v in d.items() if 50000 <= k <= 60000]
t_dict_range = time.perf_counter() - start

# для SortedDict — irange
start = time.perf_counter()
result = list(sd.irange(50000, 60000))
t_sd_range = time.perf_counter() - start

print(f"insert:")
print(f"  dict:       {t_dict_insert*1000:.0f} ms")
print(f"  SortedDict: {t_sd_insert*1000:.0f} ms  ({t_sd_insert/t_dict_insert:.1f}x slower)")

print(f"\nlookup:")
print(f"  dict:       {t_dict_lookup*1000:.0f} ms")
print(f"  SortedDict: {t_sd_lookup*1000:.0f} ms")

print(f"\nrange [50K, 60K]:")
print(f"  dict (filter): {t_dict_range*1000:.0f} ms")
print(f"  SortedDict:    {t_sd_range*1000:.0f} ms")

Типичный результат:

insert:
  dict:       8 ms
  SortedDict: 40 ms  (5x slower)

lookup:
  dict:       6 ms
  SortedDict: 25 ms

range [50K, 60K]:
  dict (filter): 7 ms
  SortedDict:    0.3 ms

Hash в 5× быстрее на insert/lookup, но в 20× медленнее на range query. Выбор зависит от паттерна работы.

Попробуй сам

from sortedcontainers import SortedDict
import random

# 1. Range query на 1M ключей
n = 1_000_000
sd = SortedDict({k: k for k in range(n)})

import time
start = time.perf_counter()
result = list(sd.irange(500000, 500100))
print(f"Range [500K, 500K+100]: {(time.perf_counter()-start)*1e6:.0f} us, {len(result)} items")
# обычно <100 us

# 2. min, max
start = time.perf_counter()
mn = sd.peekitem(0)
mx = sd.peekitem(-1)
print(f"min={mn[0]}, max={mx[0]}, elapsed={(time.perf_counter()-start)*1e6:.0f} us")

# 3. Pagination через cursor (offset-based vs key-based)
items = list(sd.items())
page_size = 100

# offset-based: O(skipping)
offset = 999_000
start = time.perf_counter()
page = items[offset:offset+page_size]
t_offset = time.perf_counter() - start

# key-based: O(log N)
start = time.perf_counter()
page = list(sd.irange(999_000, 999_100))
t_keyed = time.perf_counter() - start

print(f"offset pagination: {t_offset*1000:.1f} ms")
print(f"key pagination:    {t_keyed*1e6:.0f} us")
# key-based в тысячи раз быстрее на больших offset'ах

Это завершает модуль про деревья. В следующем модуле — heap и priority queue — особый случай complete binary tree, оптимизированный под top-K и Dijkstra.