Деревья и бинарные деревья поиска

Зачем вообще дерево, если есть массив и хеш-таблица

У нас уже есть две отличные структуры для хранения пар «ключ → значение».

Отсортированный массив (https://courses.digitable.life/post/data-structures/02-arrays-and-strings/) даёт поиск за O(log n) бинарным поиском, идеальную локальность кэша и бесплатные порядковые запросы: «все ключи между 100 и 200», «следующий после X», «k-й по величине». Но вставка в середину — O(n) сдвигов. Он прекрасен, пока данные не меняются.

Хеш-таблица (https://courses.digitable.life/post/data-structures/05-hash-tables/) даёт O(1) в среднем на вставку, удаление и точечный поиск. Но она принципиально не хранит порядок: хеш-функция специально разбрасывает соседние ключи как можно дальше друг от друга. Спросить у хеш-таблицы «а какой ключ идёт после 42?» можно только полным перебором за O(n).

Дерево поиска — это компромисс, закрывающий дыру между ними:

Динамическое множество с сохранением порядка. Вставка, удаление и поиск за O(log n), плюс min, max, successor, predecessor, floor, ceiling, диапазонный запрос и обход по возрастанию — тоже дёшево.

Аналогия: отсортированный массив — это книга с алфавитным указателем; чтобы вставить новую страницу в середину, нужно переклеить всю книгу. Хеш-таблица — это гардероб с номерками: мгновенно найдёшь свою вещь по номерку, но не ответишь, чья куртка висит «следующей по алфавиту». Дерево поиска — это папка-скоросшиватель: чтобы вставить лист в середину, достаточно перецепить два кольца, а порядок листов сохраняется.

Из этой карты в текущей статье мы разбираем корень слева — обычный BST. Сбалансированные варианты — в статье https://courses.digitable.life/post/data-structures/07-balanced-trees/, кучи — в https://courses.digitable.life/post/data-structures/08-heaps-priority-queues/, строковые — в https://courses.digitable.life/post/data-structures/09-tries-and-string-structures/, агрегирующие — в https://courses.digitable.life/post/data-structures/12-segment-and-fenwick-trees/.

Терминология и базовые свойства

Дерево — связный ациклический граф (https://courses.digitable.life/post/data-structures/10-graphs-representation/). Корневое дерево — дерево с выделенной вершиной-корнем, что задаёт направление «сверху вниз» и отношение родитель/ребёнок.

• Узел (node) — элемент дерева; корень (root) — узел без родителя; лист (leaf) — узел без детей; внутренний узел — не лист.
• Глубина узла — число рёбер от корня до него (у корня 0). Высота узла — максимальное число рёбер до листа в его поддереве. Высота дерева h — высота корня. Пустое дерево обычно считают имеющим высоту −1, дерево из одного узла — 0.
• Степень узла — число детей. Бинарное дерево — каждый узел имеет не более двух детей, причём левый и правый различимы (дерево с одним левым ребёнком ≠ дерево с одним правым).

Полезные тождества, которые стоит держать в голове:

Последнее тождество — тот самый факт, из-за которого в куче ровно ⌈n/2⌉ листьев, а в дереве Хаффмана число внутренних узлов на единицу меньше числа символов.

Ключевой вывод, который определит весь остаток статьи: все операции в дереве поиска стоят Θ(h), а h может быть чем угодно от log₂ n до n − 1. Вся дальнейшая инженерия деревьев — это борьба за то, чтобы h оставалось логарифмическим.

Как дерево лежит в памяти

Есть три принципиально разных способа представить дерево, и выбор между ними — это выбор между гибкостью и локальностью (https://courses.digitable.life/post/data-structures/01-complexity-and-memory/).

1. Указатели (PointerNode). Классика, гибкая: любая форма дерева, дешёвое перевешивание поддеревьев. Цена — по узлу на аллокацию, 16–24 байта накладных расходов на указатели и, главное, отсутствие локальности: каждый шаг вниз — потенциальный промах кэша. Поле parent нужно не всегда — рекурсия и явный стек часто заменяют его бесплатно, а хранение родителя удваивает работу при любой перевязке.
2. Неявный массив (ImplicitArray). Узел i держит детей в 2i+1 и 2i+2. Ноль накладных расходов, идеальная локальность на верхних уровнях — так реализована бинарная куча. Но для BST это годится только если дерево почти полное: на цепочке из 30 узлов такому массиву понадобится 2³⁰ ячеек.
3. Арена / пул индексов (Arena). Узлы лежат в одном непрерывном Vec/[]Node, «указатели» — 32-битные индексы. Это компромисс, который в проде встречается чаще всего: локальность и половинный размер указателя, сериализуемость (дерево можно записать в файл одним write), и отсутствие миллиона мелких аллокаций. Так устроены арены в компиляторах, индексы в БД и большинство embedded-реализаций.

Обходы: четыре способа посмотреть на дерево

Обход (traversal) — это порядок, в котором мы посещаем узлы. Для бинарного дерева есть три классических DFS-порядка, различающихся лишь местом, где мы «обрабатываем» текущий узел относительно рекурсивных вызовов, и один BFS.

class Node:
    """Узел: ключ, значение, два ребёнка и размер поддерева (понадобится для rank/select)."""
    def __init__(self, key, value=None):
        self.key, self.value = key, value
        self.left = self.right = None
        self.size = 1

def preorder(node):    # корень → левое → правое
    if node is None:
        return
    yield node.key
    yield from preorder(node.left)
    yield from preorder(node.right)

def inorder(node):     # левое → корень → правое
    if node is None:
        return
    yield from inorder(node.left)
    yield node.key
    yield from inorder(node.right)

def postorder(node):   # левое → правое → корень
    if node is None:
        return
    yield from postorder(node.left)
    yield from postorder(node.right)
    yield node.key

def bfs(root):         # по уровням, слева направо
    from collections import deque
    if root is None:
        return
    q = deque([root])
    while q:
        node = q.popleft()
        yield node.key
        if node.left:
            q.append(node.left)
        if node.right:
            q.append(node.right)

Каждый обход стоит Θ(n) по времени — каждое ребро проходится ровно дважды. Память: DFS — O(h) на стек вызовов, BFS — O(w), где w — максимальная ширина уровня, что для полного дерева равно n/2. Это важная асимметрия: на широком дереве BFS съедает линейную память, на глубоком DFS переполняет стек.

Зачем нужен каждый:

• pre-order — сериализация и клонирование: узел записывается раньше детей, поэтому при чтении родитель уже существует. Так работает вывод дерева каталогов и печать AST.
• in-order — только для BST: даёт ключи по возрастанию. Это и есть операционное определение инварианта поиска.
• post-order — освобождение памяти, du -sh, вычисление значения выражения в AST, любой расчёт «снизу вверх», где результат родителя зависит от результатов детей (высота, размер поддерева, агрегаты).
• BFS — поиск кратчайшего по числу рёбер, печать по уровням, ограничение глубины обхода.

Мнемоника: pre/in/post говорят, когда посещается корень — до детей, между детьми, после детей.

Итеративный in-order и трюк Морриса

Рекурсия на дереве глубины 10⁶ (а вырожденный BST именно таков) кладёт процесс по RecursionError/stack overflow. Итеративная версия с явным стеком (https://courses.digitable.life/post/data-structures/04-stacks-queues-deques/) — обязательный инструмент:

def inorder_iterative(root):
    stack, node = [], root
    while stack or node is not None:
        while node is not None:      # спускаемся по левым рёбрам до упора
            stack.append(node)
            node = node.left
        node = stack.pop()           # самый левый непосещённый узел
        yield node.key
        node = node.right            # переключаемся в правое поддерево

Память здесь всё ещё O(h). Убрать и её позволяет обход Морриса (J. H. Morris, «Traversing binary trees simply and cheaply», Information Processing Letters, 1979): мы временно превращаем дерево в «прошитое» (threaded), подвешивая правый указатель самого правого узла левого поддерева обратно на текущий узел, а на обратном проходе снимаем нить.

def morris_inorder(root):
    """In-order за O(n) времени и O(1) дополнительной памяти.
    Дерево временно мутируется, но к концу обхода восстанавливается полностью."""
    cur = root
    while cur is not None:
        if cur.left is None:
            yield cur.key
            cur = cur.right
        else:
            pred = cur.left                       # ищем in-order предшественника
            while pred.right is not None and pred.right is not cur:
                pred = pred.right
            if pred.right is None:
                pred.right = cur                  # ставим нить и уходим влево
                cur = cur.left
            else:
                pred.right = None                 # нить сработала — снимаем её
                yield cur.key
                cur = cur.right

Каждое ребро проходится не более трёх раз, поэтому суммарно всё ещё O(n), несмотря на внутренний цикл. Ограничение: обход мутирует дерево по ходу, поэтому он несовместим с конкурентным чтением (https://courses.digitable.life/post/data-structures/14-persistent-and-concurrent/) и с деревьями в read-only памяти. На практике его берут в embedded и в задачах, где O(h) памяти реально дорого.

Инвариант BST

Binary Search Tree — бинарное дерево, в котором для каждого узла x:

все ключи в левом поддереве x строго меньше x.key, а все ключи в правом поддереве — строго больше.

Обратите внимание на слова «во всём поддереве», а не «у непосредственных детей» — это источник самой популярной ошибки при валидации, к которой мы вернёмся. Эквивалентная формулировка, которую удобно держать как рабочее определение: in-order обход BST выдаёт строго возрастающую последовательность ключей.

Дубликаты в классический BST не помещаются красиво. Три рабочие стратегии: (1) запретить — вставка существующего ключа перезаписывает значение (так делают map/dict-структуры); (2) хранить счётчик count в узле — это multiset без структурного раздувания; (3) складывать равные ключи строго в одну сторону — работает, но ломает симметрию удаления и на практике приносит больше багов, чем пользы.

Поиск, минимум, преемник

def search(root, key):
    """O(h). Итеративно, чтобы не зависеть от глубины рекурсии."""
    node = root
    while node is not None:
        if key < node.key:
            node = node.left
        elif key > node.key:
            node = node.right
        else:
            return node
    return None

def min_node(node):
    while node.left is not None:      # минимум — самый левый узел
        node = node.left
    return node

Преемник (следующий по возрастанию ключ) устроен так: если у узла есть правое поддерево — это его минимум; иначе это первый предок, для которого наш узел лежит в левом поддереве. При наличии поля parent это O(h) без всякой памяти; без него ту же роль играет стек из inorder_iterative выше — именно он и есть итератор дерева.

Путь поиска однозначно определён ключом: на каждом узле мы делаем ровно одно сравнение и уходим в одну сторону. Отсюда Θ(h) — и ни одного лишнего сравнения. Это принципиально отличает BST от хеш-таблицы, где стоимость определяется коэффициентом заполнения, а не структурой ключа.

Вставка

Вставка — это неудачный поиск, который заканчивается созданием листа на месте, где поиск упёрся в null. Форма дерева, таким образом, полностью определяется порядком вставки — и это главный подвох BST.

def insert(node, key, value):
    """Возвращает новый корень поддерева. O(h)."""
    if node is None:
        return Node(key, value)
    if key < node.key:
        node.left = insert(node.left, key, value)
    elif key > node.key:
        node.right = insert(node.right, key, value)
    else:
        node.value = value            # ключ уже есть — обновляем значение
        return node
    node.size = 1 + size(node.left) + size(node.right)
    return node

Приём «функция вставки возвращает новый корень поддерева, а вызывающий присваивает результат в node.left/node.right» — идиома, которую стоит усвоить намертво. Она избавляет от возни с указателем на родителя и от разбора случая «мы меняем сам корень», и именно в этом стиле написаны все реализации в Algorithms, 4th Edition Седжвика.

Удаление

Удаление — единственная нетривиальная операция BST. Разбор по числу детей:

Случаи «нет детей» и «один ребёнок» схлопываются в одну строку: вернуть того ребёнка, который есть (для листа это null). Настоящая работа — случай двух детей. Идея: мы не можем просто выкинуть узел, но можем подменить его содержимое на ключ, который в отсортированном порядке стоит вплотную к нему, — на in-order преемника (минимум правого поддерева) либо предшественника (максимум левого). У такого узла заведомо нет левого (соответственно правого) ребёнка, поэтому его удаление сводится к простому случаю.

def delete(node, key):
    """Возвращает новый корень поддерева. O(h)."""
    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:         # 0 или 1 ребёнок
            return node.right
        if node.right is None:
            return node.left
        succ = min_node(node.right)   # 2 ребёнка: подмена на преемника
        node.key, node.value = succ.key, succ.value
        node.right = delete(node.right, succ.key)
    node.size = 1 + size(node.left) + size(node.right)
    return node

Тонкость, о которой редко пишут: если всегда брать преемника, дерево при большом числе удалений систематически кренится влево. Хиббард (1962) предложил именно этот вариант, и эмпирически известно, что после Θ(n²) случайных вставок/удалений средняя глубина растёт с √n вместо log n. Лечится чередованием: брать преемника или предшественника в зависимости от, например, чётности счётчика операций или от того, какое поддерево выше. В сбалансированных деревьях проблема снимается автоматически.

Порядковая статистика: зачем в узле поле size

Если каждый узел хранит размер своего поддерева (мы уже поддерживали это поле в insert/delete), BST бесплатно превращается в order-statistic tree: select(k) — k-й по возрастанию ключ, rank(key) — сколько ключей строго меньше данного. Обе операции — O(h).

def size(node):
    return 0 if node is None else node.size

def select(node, k):
    """k-й ключ в порядке возрастания, k с нуля. O(h)."""
    while node is not None:
        left_size = size(node.left)
        if k < left_size:
            node = node.left
        elif k > left_size:
            k -= left_size + 1        # пропускаем левое поддерево и сам узел
            node = node.right
        else:
            return node
    raise IndexError("k вне диапазона")

def rank(node, key):
    """Число ключей строго меньше key. O(h)."""
    result = 0
    while node is not None:
        if key < node.key:
            node = node.left
        elif key > node.key:
            result += size(node.left) + 1
            node = node.right
        else:
            return result + size(node.left)
    return result

def range_keys(node, lo, hi):
    """Все ключи из [lo, hi] по возрастанию. O(h + m), где m — размер ответа."""
    if node is None:
        return
    if lo < node.key:                        # в левое поддерево есть смысл идти,
        yield from range_keys(node.left, lo, hi)   # только если lo может там оказаться
    if lo <= node.key <= hi:
        yield node.key
    if node.key < hi:
        yield from range_keys(node.right, lo, hi)

def floor(node, key):
    """Наибольший ключ ≤ key. O(h)."""
    best = None
    while node is not None:
        if key < node.key:
            node = node.left
        elif key > node.key:
            best = node.key               # кандидат; вдруг справа найдётся ближе
            node = node.right
        else:
            return node.key
    return best

Именно rank/select делают дерево незаменимым там, где хеш-таблица бессильна: скользящая медиана в потоке, «сколько заказов дешевле текущего», лидерборд с ответом «твоё место — 4718-е», перцентили в мониторинге. Обратите внимание на сложность range_keys: O(h + m) — вывод пропорционален размеру ответа, а не размеру дерева, потому что две проверки на границах отсекают поддеревья целиком.

Отдельно про floor: паттерн «запоминаем кандидата при уходе вправо» одинаково работает для ceiling (зеркально) и является основой почти всех «ближайший подходящий» запросов — от роутинга по префиксу до подбора тарифа по объёму.

Сложность и вероятностная картина

Строка «средний случай» требует пояснения, потому что среднее берётся по случайным порядкам вставки, а не по случайным деревьям. Классические результаты:

• Средняя глубина узла в BST, построенном вставкой случайной перестановки, равна ≈ 2 ln n ≈ 1.386 log₂ n. То есть успешный поиск в среднем требует примерно на 39% больше сравнений, чем в идеально сбалансированном дереве, — терпимо.
• Ожидаемая высота случайного BST — ≈ 4.311 log₂ n (Брюс Рид, The height of a random binary search tree, JACM 50(3), 2003, doi.org/10.1145/765568.765571). Заметно хуже среднего, но всё ещё логарифмическая.
• Если строить BST из n отсортированных ключей, высота ровно n − 1, и построение стоит Θ(n²).

Практический вывод жёсткий: «в среднем логарифм» — это утверждение о ваших входных данных, а не о структуре. А реальные ключи почти никогда не случайны: автоинкрементные id, timestamp событий, лексикографически растущие UUIDv7, отсортированный дамп из БД, ключи после ORDER BY — всё это ровно тот вход, который превращает BST в связный список (https://courses.digitable.life/post/data-structures/03-linked-lists/), только с лишним полем left = null и вдвое худшей локальностью.

Отсюда два выхода. Первый — балансировать структуру (AVL, красно-чёрные, B-деревья: статья https://courses.digitable.life/post/data-structures/07-balanced-trees/). Второй — рандомизировать вход: перемешать ключи перед массовой вставкой или использовать treap/randomized BST, где приоритеты берутся из ГПСЧ и высота становится O(log n) с высокой вероятностью независимо от порядка ключей. Если же отсортированный массив известен заранее, есть третий путь: строить дерево не вставками, а рекурсивным делением пополам — медиана становится корнем, половины рекурсивно становятся поддеревьями. Это даёт идеально сбалансированное дерево за Θ(n) вместо Θ(n²), и ровно так делают bulk-load индексов в СУБД.

Типичные ошибки

1. Неправильная валидация BST. Самая частая ошибка на собеседованиях и в коде: проверять только node.left.key < node.key < node.right.key. Это локальное условие, а инвариант — глобальный. Контрпример: корень 10, левый ребёнок 5, у которого правый ребёнок 12. Локально всё верно, но 12 находится в левом поддереве десятки. Правильно — протаскивать границы:

def is_bst(node, lo=None, hi=None):
    """O(n). Границы сужаются при спуске — это и есть глобальный инвариант."""
    if node is None:
        return True
    if (lo is not None and node.key <= lo) or (hi is not None and node.key >= hi):
        return False
    return is_bst(node.left, lo, node.key) and is_bst(node.right, node.key, hi)

Альтернатива, которую полезно знать: сделать in-order обход и проверить, что последовательность строго возрастает. Это то же самое утверждение, записанное иначе, и в тестах оно читается лучше.

2. Мутация ключа у вставленного узла. Если ключ — изменяемый объект и вы правите его «на месте», узел остаётся физически там же, но логически оказывается не в том поддереве. Дерево тихо ломается: search начинает не находить существующие элементы. Правило: ключ иммутабелен; чтобы изменить ключ — удалить и вставить заново. Ровно та же проблема, что с мутацией ключа в хеш-таблице.

3. Переполнение стека на глубоком дереве. Рекурсивный обход дерева на 10⁶ узлах, выродившегося в цепочку, гарантированно падает: у CPython лимит sys.setrecursionlimit по умолчанию 1000, у JVM стек около 512 КБ–1 МБ. Продакшн-код обходит деревья итеративно либо явно ограничивает глубину.

4. Забытое обновление агрегатов. Если в узле есть size, height, sum — их надо пересчитывать на обратном пути рекурсии, во всех ветках, включая ветку удаления. Пропущенная строка node.size = ... в одной ветке delete даёт баг, который проявится через недели: select(k) начнёт возвращать соседний элемент.

5. Сравнение несравнимых ключей. NaN нарушает трихотомию (NaN < x, NaN > x и NaN == x — всё False), поэтому узел с NaN в дереве недостижим. Строки в разных локалях и регистро-нечувствительные компараторы, не удовлетворяющие транзитивности, ломают дерево так же надёжно. Компаратор обязан задавать строгий полный порядок.

6. Удаление узла копированием ссылки, а не значения. В языках со ссылочной семантикой соблазнительно написать node = succ. Это переприсваивает локальную переменную и не меняет дерево вообще. Нужно либо копировать поля (node.key, node.value = succ.key, succ.value), либо честно перевязывать указатели у родителя.

7. Модификация дерева во время обхода. for key in tree: tree.delete(key) ломается ровно так же, как модификация списка во время итерации. Собирайте ключи в буфер или используйте API вроде retain.

Как это выглядит в проде

Здесь важный поворот: чистый BST в продакшн-библиотеках почти не встречается. Он ценен как базовая модель, но в реальных map-структурах лежит что-то более сложное — по двум причинам: гарантии худшего случая и кэш.

• C++ std::map / std::set — красно-чёрное дерево. Стандарт требует O(log n) в худшем случае и валидность итераторов при вставке, что фактически исключает и хеш-таблицу, и переупаковку узлов (cppreference).
• Java TreeMap / TreeSet — тоже красно-чёрное дерево, реализующее NavigableMap с floorKey, ceilingKey, subMap — ровно теми порядковыми операциями, ради которых дерево и берут (docs.oracle.com).
• Rust BTreeMap — намеренно не бинарное дерево, а B-дерево с фактором ветвления 6 (до 11 ключей в узле). Документация прямо объясняет мотив: на современном железе стоимость доминируется промахами кэша, и сравнение нескольких ключей внутри одной кэш-линии дешевле одного лишнего прыжка по указателю (doc.rust-lang.org).
• Индексы в СУБД — B+ деревья: PostgreSQL, MySQL InnoDB, SQLite. Узел равен странице (обычно 8 КБ), высота дерева на миллиарде строк — 3–4 уровня, то есть 3–4 обращения к диску (postgresql.org/docs/current/btree.html).
• Ядро Linux до недавнего времени держало VMA (области виртуальной памяти) в красно-чёрном дереве, а в 6.1 заменило их на maple tree — RCU-безопасное B-дерево, оптимизированное под кэш и конкурентное чтение (kernel.org). Отличная иллюстрация того же тренда: от бинарного к широкому.
• Go ordered map в стандартной библиотеке не имеет вовсе: есть map (хеш) и sort по срезу. Идиома «собрать ключи и отсортировать» покрывает большинство случаев, потому что реальные n малы (https://courses.digitable.life/post/golang/00-overview/). Когда нужен настоящий порядок — берут сторонние B-деревья вроде google/btree.
• C# предлагает SortedDictionary<K,V> (красно-чёрное дерево, быстрая вставка) и SortedList<K,V> (два отсортированных массива, быстрый индексный доступ и меньше памяти, но O(n) вставка) — редкий случай, когда стандартная библиотека честно показывает оба конца trade-off (https://courses.digitable.life/post/csharp/00-overview/).

Где бинарные деревья поиска остаются в первозданном виде:

• Треапы и splay-деревья в спортивном программировании и in-memory движках — там, где важна простота кода и амортизированные гарантии.
• Интервальные деревья и k-d деревья — BST с дополнительным полем-агрегатом (максимум правого конца интервала; координата вдоль оси). Идея аугментации напрямую наследуется от size из раздела выше.
• Внутренности планировщиков. CFS в Linux хранил задачи в красно-чёрном дереве по vruntime, потому что нужен не просто минимум (для этого хватило бы кучи), а порядок и дешёвое удаление произвольной задачи.

Мини-эталон: когда что брать

Полная версия таблицы решений — в обзоре трека https://courses.digitable.life/post/data-structures/00-overview/.

Мини-итог

• Дерево — это O(log n) на динамическом множестве с сохранением порядка: ниша между отсортированным массивом (быстрый поиск, дорогая вставка) и хеш-таблицей (быстро всё, но порядка нет). Все его операции стоят Θ(h), и вся дальнейшая теория деревьев — про удержание h = O(log n).
• Инвариант BST глобальный: сравнение с прямыми детьми ничего не доказывает. In-order обход BST строго возрастает — это рабочее операционное определение.
• Вставка тривиальна; в удалении нетривиален один случай — узел с двумя детьми, решаемый подменой на in-order преемника.
• Поле size в узле бесплатно даёт rank/select за O(log n) — порядковую статистику, которую хеш-таблица не умеет в принципе.
• Форму дерева задаёт порядок вставки: случайный даёт высоту ≈ 4.3 log₂ n, отсортированный — цепочку и Θ(n) на операцию. Реальные ключи почти всегда отсортированы, поэтому голый BST в проде опасен.
• В настоящих библиотеках лежат красно-чёрные деревья (гарантии худшего случая) и B-деревья (кэш). Знать BST нужно, чтобы понимать их — и чтобы аугментировать деревья под свою задачу.

Источники

• Кормен, Лейзерсон, Ривест, Штайн. Introduction to Algorithms, 4-е изд., глава 12 «Binary Search Trees» — каноничные доказательства и разбор случайных BST. mitpress.mit.edu
• Sedgewick, Wayne. Algorithms, 4th Edition, раздел 3.2 — реализации в стиле «функция возвращает корень поддерева», rank/select, визуализации. algs4.cs.princeton.edu/32bst
• Knuth. The Art of Computer Programming, Vol. 3: Sorting and Searching, §6.2.2 — исходный анализ средней глубины и удаления по Хиббарду.
• Reed B. The height of a random binary search tree, JACM 50(3), 2003 — точная константа 4.311…. doi.org/10.1145/765568.765571
• Morris J. H. Traversing binary trees simply and cheaply, Information Processing Letters 9(5), 1979 — обход с O(1) памяти.
• Rust std::collections::BTreeMap — документированное объяснение, почему B-дерево бьёт BST на современном железе. doc.rust-lang.org
• Linux kernel, Maple Tree — современная замена RB-дереву в управлении памятью. docs.kernel.org/core-api/maple_tree.html

Что дальше

Мы выяснили, что BST хорош ровно настолько, насколько повезло с порядком вставки, — и что «повезло» в проде не бывает. Следующий шаг: как заставить дерево держать логарифмическую высоту при любом входе. Повороты, инварианты AVL, правила перекраски красно-чёрных деревьев и высокоразветвлённые B-деревья, живущие в каждом индексе каждой базы данных, — в статье Сбалансированные деревья: AVL, красно-чёрные, B-деревья.