🔴 Сложный ⏱️ 55 минут

Сбалансированные деревья

📋 Содержание урока

Сбалансированные деревья ⚖️

В прошлом уроке ты построил бинарное дерево поиска и увидел, что поиск, вставка и удаление работают за время $O(h)$, где $h$ — высота дерева. Пока элементы вставляются в случайном, «перемешанном» порядке, высота обычно держится около $\log_2 n$, и всё работает быстро. Но там же прозвучало тревожное предупреждение: если вставлять элементы уже отсортированными, дерево вырождается в подобие связного списка, и те же самые операции скатываются к $O(n)$. Этот урок — прямой ответ на эту проблему: как заставить дерево оставаться низким и компактным при абсолютно любом порядке вставки, вставляют ли в него данные случайно, по возрастанию или намеренно враждебно.

Идея балансировки — не абстрактная математическая гимнастика, а инженерное решение конкретной инженерной проблемы, и в реальном мире оно повсюду. Открой документацию любой реляционной СУБД — PostgreSQL, MySQL, SQLite — и в разделе про индексы почти наверняка встретишь термин B-tree. B-дерево — близкий родственник сбалансированных бинарных деревьев поиска: та же идея (держать высоту структуры около логарифма от числа элементов за счёт автоматической перестройки при каждом изменении), но приспособленная под чтение с диска, где один узел хранит не один ключ, а сразу пачку ключей, чтобы за одно обращение к медленному диску прочитать максимум полезной информации. Когда ты как специалист по данным выполняешь SQL-запрос, чтобы вытащить обучающую выборку из продакшен-базы, где-то под капотом СУБД работает именно тот принцип автоматической балансировки, о котором пойдёт речь ниже — просто применённый не к одному ключу на узел, а к целому блоку.

Сама по себе гарантия «высота структуры не превышает $C \cdot \log n$» — куда более общая идея, чем частный случай АВЛ-деревьев или красно-чёрных деревьев. Та же логика — поддерживать структуру так, чтобы поиск не деградировал до линейного перебора, автоматически перестраивая её при добавлении новых элементов, — лежит в основе современных структур для приближённого поиска ближайших соседей (approximate nearest neighbors) в больших векторных индексах: именно на них держится любая система семантического поиска, рекомендательная система или retrieval-augmented generation поверх языковой модели. Алгоритм HNSW (Hierarchical Navigable Small World), один из самых популярных для векторного поиска, строит многоуровневую графовую структуру во многом по той же философии: логарифмическая по высоте иерархия, дисциплинированная перестройка связей при вставке новых точек, принципиальный отказ от полного перебора всех векторов. Понимание механики балансировки бинарных деревьев — это фундамент, на котором более сложные структуры вроде HNSW или B+-деревьев перестают быть магией и становятся понятной инженерией.

В этом уроке ты разберёшься, почему обычное BST может так драматично деградировать, какая общая идея стоит за словом «балансировка», а затем подробно — на интуитивном, а не строго формальном уровне — изучишь два главных инструмента практической балансировки: АВЛ-дерево с его коэффициентом баланса и системой поворотов, и красно-чёрное дерево с его более мягкими правилами окраски узлов. В конце ты увидишь, почему в реальных библиотеках вроде std::map в C++ и TreeMap в Java выбор почти всегда падает на красно-чёрные деревья, а не на АВЛ, и когда это правило всё же меняется на противоположное.

История: почему нужно было это придумать

В 1962 году два советских математика — Георгий Максимович Адельсон-Вельский и Евгений Михайлович Ландис — опубликовали в «Докладах Академии наук СССР» короткую статью «Один алгоритм организации информации». В ней впервые была строго описана структура данных, которая гарантированно сохраняет высоту, близкую к $\log_2 n$, при произвольных вставках — притом что дерево остаётся именно бинарным деревом поиска, без укрупнённых узлов. Структуру назвали АВЛ-деревом — по первым буквам фамилий авторов (в английской транслитерации AVL). Это было первое практичное самобалансирующееся дерево поиска в истории информатики, и появилось оно раньше очень многих привычных сегодня инструментов: раньше реляционных баз данных в их современном виде, раньше персональных компьютеров, ещё в эпоху, когда «компьютер» занимал целую комнату.

Задача, которую решали Адельсон-Вельский и Ландис, была предельно практической: в СССР в те годы активно развивались системы автоматизированной обработки информации, и требовалась структура данных, которая одинаково хорошо работала бы и при поиске уже существующей записи, и при постоянном добавлении новых — без деградации по мере роста базы. Идея, которую они предложили — жёстко контролировать разницу высот двух поддеревьев в каждом узле и локально перестраивать дерево, как только эта разница становится слишком большой, — оказалась настолько удачной, что легла в основу целого класса структур данных, разрабатывавшихся впоследствии.

Десятилетием позже, в 1972 году, немецкий информатик Рудольф Байер (тот самый, кто изобрёл и B-дерево) предложил другую конструкцию — «симметричные бинарные B-деревья» (symmetric binary B-trees), математически эквивалентную B-дереву порядка 4, но представленную в виде обычного бинарного дерева с дополнительной информацией. В 1978 году Лео Гибас и Роберт Седжвик переформулировали идею Байера в терминах, которые используются до сих пор: узлам дерева присваивается цвет — красный или чёрный, — а балансировка сводится к соблюдению нескольких простых правил окраски. Так родилось красно-чёрное дерево — структура более гибкая (реже требующая перестроек), чем строгий АВЛ, и именно поэтому ставшая стандартом в промышленных библиотеках нескольких десятилетий спустя.

Любопытно, что путь от статьи Адельсон-Вельского и Ландиса до массового промышленного использования сбалансированных деревьев занял не годы, а десятилетия. Долгое время АВЛ-дерево оставалось скорее объектом изучения в университетских курсах и узкоспециализированных системах, чем инструментом повседневной разработки, — компьютеры той эпохи оперировали настолько небольшими объёмами данных, что выигрыш от строгой балансировки часто не окупал сложность реализации. Ситуация изменилась вместе с ростом объёмов данных в 1980-х и 1990-х годах, когда стандартные библиотеки языков программирования начали требовать встроенных ассоциативных контейнеров с гарантированной производительностью — именно тогда красно-чёрное дерево, разработанное Байером, Гибасом и Седжвиком, оказалось наиболее удачным компромиссом между простотой реализации и эффективностью и заняло место, которое удерживает в промышленных библиотеках по сей день. Позже, уже в 1990-х годах, появились и другие идеи с похожей целью — например, декартово дерево (treap), сочетающее свойства дерева поиска и кучи через случайные приоритеты, или skip list, достигающий логарифмической сложности вовсе без дерева, через несколько уровней связных списков со случайно выбранной высотой узлов. Это отдельное направление развития идеи балансировки, которое стоит держать в уме: строгий контроль высоты через детерминированные правила (АВЛ, красно-чёрное дерево) — не единственный путь к логарифмической сложности, есть и вероятностные конструкции, добивающиеся того же результата в среднем случае за счёт случайности вместо жёстких инвариантов.

Проблема вырождения: почему обычное BST — это бомба замедленного действия

Интуиция

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

Проблема в том, что ни вставка, ни поиск в обычном BST не имеют встроенного механизма «заметить», что дерево становится перекошенным, и как-то на это отреагировать. Алгоритм вставки из предыдущего урока просто идёт от корня вниз, сравнивая значения и выбирая направление, и вставляет новый узел в первую же найденную свободную позицию — без единой мысли о том, что происходит с формой дерева в целом. Отсутствие такого «чувства формы» и есть корень проблемы: асимптотика $O(\log n)$ для BST — это утверждение не про худший случай, а лишь про случайный или удачный порядок вставки. Для худшего случая гарантии нет вообще никакой.

Формальное определение (что значит «сбалансировано»)

Определение. Бинарное дерево называется сбалансированным по высоте, если для его высоты $h$ и числа узлов $n$ выполняется $h = O(\log n)$. Структура данных называется самобалансирующейся, если она автоматически поддерживает это свойство при любой последовательности операций вставки и удаления — то есть после каждой такой операции структура при необходимости перестраивается так, чтобы высота оставалась логарифмической, без вмешательства извне.

Ключевое слово здесь — «автоматически». Обычное BST может оказаться сбалансированным (если повезёт с порядком вставки), но не обязано им оставаться. Самобалансирующиеся структуры данных превращают удачу в гарантию: они платят небольшую дополнительную работу при каждой вставке и удалении (проверку и, если нужно, локальную перестройку), но взамен получают строгую верхнюю границу на высоту дерева при абсолютно любых входных данных, включая специально подобранные злоумышленником.

Примеры с разбором

Пример 1. Вырождение при отсортированной вставке. Вставь числа $1, 2, 3, 4, 5$ в обычное BST именно в этом порядке.

Каждое следующее число больше предыдущего, поэтому идёт направо. Высота получившегося дерева равна $4$ (четыре ребра от корня до самого глубокого листа), при том что число узлов $n=5$. Формула логарифмической высоты дала бы $\log_2 5 \approx 2{,}32$, округляя вверх — $3$. Уже на пяти элементах реальная высота почти вдвое превышает теоретический минимум, и с ростом $n$ разрыв только увеличивается линейно: высота вырожденного дерева из $n$ узлов равна ровно $n-1$, то есть растёт как $O(n)$, а не как $O(\log n)$.

Пример 2. То же множество чисел, другой порядок вставки. Вставь те же пять чисел в порядке $3, 1, 4, 2, 5$.

Высота этого дерева равна $2$ — гораздо ближе к теоретическому минимуму $\log_2 5 \approx 2{,}32$. Это ровно то же множество из пяти чисел, что и в первом примере, но порядок вставки полностью меняет форму дерева и, как следствие, стоимость поиска: для поиска числа $2$ здесь нужно три сравнения ($3 \to 1 \to 2$), а в вырожденном дереве из примера 1 — целых пять ($1\to2\to3\to4\to5$).

Пример 3. Количественная оценка на большом $n$. Пусть в базу вставляется $n = 1\,000\,000$ записей с автоинкрементным ключом (то есть строго по возрастанию — очень частый сценарий на практике: автоинкрементные первичные ключи, метки времени, порядковые номера транзакций). В вырожденном BST поиск конкретной записи потребует в худшем случае до миллиона сравнений — операция, которая должна была занимать микросекунды, займёт время, сравнимое с полным сканированием таблицы. При этом сбалансированное дерево с тем же числом узлов гарантировало бы высоту $\lceil \log_2 1\,000\,000 \rceil = 20$ — разница между $20$ и $1\,000\,000$ сравнениями на практике означает разницу между «мгновенно» и «база данных зависла».

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

def insert(root, key):
    if root is None:
        return Node(key)
    if key < root.key:
        root.left = insert(root.left, key)
    else:
        root.right = insert(root.right, key)
    return root

def height(root):
    if root is None:
        return -1
    return 1 + max(height(root.left), height(root.right))

root = None
for k in range(1, 1_000_001):          # автоинкрементные ключи
    root = insert(root, k)
print(height(root))                    # 999999 — линейный рост высоты

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

АВЛ-дерево: строгая балансировка через коэффициент баланса

Интуиция

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

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

Определение коэффициента баланса

Определение. Для узла $v$ бинарного дерева коэффициент баланса (balance factor) определяется как
$$BF(v) = h(\text{правое поддерево } v) - h(\text{левое поддерево } v),$$
где высота пустого поддерева считается равной $-1$. Дерево называется АВЛ-деревом, если для каждого его узла $v$ выполняется условие $BF(v) \in \{-1, 0, 1\}$ — то есть высоты двух поддеревьев любого узла отличаются не более чем на единицу.

Если после вставки или удаления коэффициент баланса какого-то узла становится равным $-2$ или $+2$, это сигнал: дерево вышло за допустимые рамки, и требуется восстанавливающая перестройка — поворот.

Повороты: интуитивный разбор всех четырёх случаев

Поворот — это локальная перестройка трёх узлов и их поддеревьев, которая меняет форму дерева, но сохраняет свойство упорядоченности BST (in-order обход даёт ту же последовательность ключей, что и до поворота). Есть четыре ситуации разбалансировки, и для каждой — свой рецепт восстановления.

Случай 1: правый-правый (перегруз справа от правого ребёнка) → левый поворот. Узел z перегружен справа, и его правый ребёнок y тоже перегружен справа (или сбалансирован). Лекарство — один левый поворот вокруг z: узел y поднимается на место z, а сам z становится его левым ребёнком.

До поворота:            После левого поворота вокруг z:
    z                              y
     \                            / \
      y          --->            z   T3
       \                          \
        T3                        (левое поддерево y, если было)

Разберём на конкретных числах: вставляем $10, 20, 30$ в этом порядке. После вставки $10$ и $20$ дерево — просто цепочка $10 \to 20$ направо, коэффициент баланса узла $10$ равен $+1$ — ещё в норме. После вставки $30$ (идёт направо от $20$) коэффициент баланса узла $10$ становится $+2$ — нарушение. Правое поддерево узла $10$ (это узел $20$) само перегружено вправо (там висит $30$) — это классический правый-правый случай. Выполняем левый поворот вокруг $10$: узел $20$ становится новым корнем, $10$ — его левым ребёнком, $30$ — правым.

До:         После:
10              20
 \             /  \
  20          10   30
   \
    30

Случай 2: левый-левый (перегруз слева от левого ребёнка) → правый поворот. Зеркальная ситуация: узел z перегружен слева, и его левый ребёнок y тоже перегружен слева. Лекарство — один правый поворот вокруг z.

Вставляем $30, 20, 10$ в этом порядке. После вставки $30$ и $20$ — цепочка $30 \to 20$ налево. После вставки $10$ (идёт налево от $20$) коэффициент баланса узла $30$ становится $-2$: левое поддерево (узел $20$) само перегружено влево. Выполняем правый поворот вокруг $30$: узел $20$ становится новым корнем, $10$ — его левым ребёнком, $30$ — правым.

До:            После:
    30              20
   /               /  \
  20              10   30
 /
10

Случай 3: левый-правый (большой левый поворот) → сначала левый поворот вокруг ребёнка, затем правый поворот вокруг узла. Это более коварная ситуация: узел z перегружен слева, но его левый ребёнок y перегружен не в ту же сторону, а вправо. Одного поворота здесь недостаточно — нужен «большой» (двойной) поворот: сначала левый поворот вокруг y (это превращает ситуацию в обычный случай левый-левый), а затем правый поворот вокруг z.

Вставляем $30, 10, 20$ в этом порядке. После вставки $30$ и $10$ — цепочка $30 \to 10$ налево. После вставки $20$ (это больше $10$, значит идёт направо от узла $10$) получаем: узел $30$ перегружен слева ($BF=-2$), а его левый ребёнок $10$ перегружен справа ($BF=+1$ у узла $10$) — несовпадение направлений, случай левый-правый.

До:                Шаг 1 (левый поворот      Шаг 2 (правый поворот
                    вокруг 10):                вокруг 30):
    30                     30                        20
   /                      /                         /  \
  10                     20                        10   30
   \                    /
    20                 10

Итог — узел $20$ становится новым корнем поддерева, $10$ и $30$ — его детьми. Обрати внимание: если бы был выполнен только один правый поворот вокруг $30$ (без предварительного шага), результат остался бы несбалансированным — именно поэтому такой случай называют «большим», двойным поворотом.

Случай 4: правый-левый (большой правый поворот) → сначала правый поворот вокруг ребёнка, затем левый поворот вокруг узла. Зеркальный вариант случая 3: узел z перегружен справа, а его правый ребёнок y перегружен влево.

Вставляем $10, 30, 20$ в этом порядке. После вставки $10$ и $30$ — цепочка $10 \to 30$ направо. После вставки $20$ (меньше $30$, значит идёт налево от узла $30$) получаем: узел $10$ перегружен справа ($BF=+2$), его правый ребёнок $30$ перегружен слева. Выполняем правый поворот вокруг $30$, затем левый поворот вокруг $10$ — итоговый корень поддерева снова $20$, симметрично случаю 3.

До:                Шаг 1 (правый поворот    Шаг 2 (левый поворот
                    вокруг 30):               вокруг 10):
10                        10                        20
 \                         \                        / \
  30                        20                     10  30
 /                            \
20                             30

Наблюдение, которое стоит унести с собой: во всех четырёх случаях после восстанавливающего поворота высота перестроенного поддерева возвращается точно к той, что была до вставки, вызвавшей разбалансировку. Именно поэтому при вставке в АВЛ-дерево никогда не требуется больше одного поворота (одинарного или двойного) на всё дерево целиком — достаточно исправить самый нижний узел, у которого коэффициент баланса вышел за пределы, и дальше вверх по пути к корню коррекция уже не нужна. При удалении, в отличие от вставки, каскад перестроек в худшем случае может дойти до самого корня — это одна из причин, почему удаление в АВЛ-дереве в среднем чуть дороже вставки.

def get_height(node):
    return node.height if node else -1

def get_balance(node):
    return get_height(node.left) - get_height(node.right) if node else 0

def update_height(node):
    node.height = 1 + max(get_height(node.left), get_height(node.right))

def rotate_right(z):
    y = z.left
    z.left = y.right
    y.right = z
    update_height(z)
    update_height(y)
    return y            # y — новый корень поддерева

def rotate_left(z):
    y = z.right
    z.right = y.left
    y.left = z
    update_height(z)
    update_height(y)
    return y

def rebalance(z):
    update_height(z)
    balance = get_balance(z)
    if balance > 1:                              # перегруз слева
        if get_balance(z.left) < 0:
            z.left = rotate_left(z.left)          # левый-правый: большой поворот
        return rotate_right(z)
    if balance < -1:                             # перегруз справа
        if get_balance(z.right) > 0:
            z.right = rotate_right(z.right)       # правый-левый: большой поворот
        return rotate_left(z)
    return z

Почему это важно

АВЛ-дерево даёт самую строгую из практически используемых гарантий баланса: доказано, что высота АВЛ-дерева с $n$ узлами не превышает примерно $1{,}44 \log_2(n+2)$ — то есть очень близка к теоретическому минимуму $\log_2 n$. Это значит максимально предсказуемое время поиска в худшем случае. Расплата за такую строгость — более частые перестройки при изменениях структуры, особенно при удалении. Поэтому АВЛ-деревья особенно хороши там, где данные вставляются редко, а ищутся очень часто (классический read-heavy сценарий): например, в качестве статического или почти статического индекса, построенного один раз и затем интенсивно используемого только для запросов.

Красно-чёрное дерево: мягкая балансировка через окраску узлов

Интуиция

Если АВЛ-дерево — это весы, требующие точного равновесия на каждом узле, то красно-чёрное дерево — это структура с более щадящими, «допускающими люфт» правилами. Идея в том, чтобы не гнаться за идеальной сбалансированностью высот, а вместо этого гарантировать более слабое, но всё ещё достаточное свойство: самый длинный путь от корня до листа не может быть более чем в два раза длиннее самого короткого. Этого оказывается достаточно, чтобы высота дерева оставалась $O(\log n)$, но правило перестройки при этом срабатывает реже, чем в АВЛ-дереве, — а значит, в среднем требуется меньше поворотов на одну вставку или удаление.

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

Правила красно-чёрного дерева

Определение. Бинарное дерево поиска называется красно-чёрным деревом, если каждому его узлу присвоен цвет — красный или чёрный — так, что выполняются следующие свойства:

Каждый узел — красный или чёрный.

Корень дерева — всегда чёрный.

Каждый лист (представляемый как пустой nil-узел) считается чёрным.

Если узел красный, оба его ребёнка — чёрные (у красного узла не может быть красного родителя и не может быть красного ребёнка — красные узлы никогда не идут подряд).

Для каждого узла все простые пути от него до любого листа в его поддереве содержат одинаковое число чёрных узлов — эта величина называется чёрной высотой узла.

Из правил 4 и 5 математически следует ограничение на высоту дерева: самый длинный возможный путь от корня до листа не более чем в два раза длиннее самого короткого. Интуиция такая: самый короткий путь состоит только из чёрных узлов (чёрная высота корня, назовём её $bh$), а самый длинный путь может чередовать чёрные и красные узлы, но красные не могут идти подряд — значит, красных узлов на пути не больше, чем чёрных, и длина самого длинного пути не превышает $2 \cdot bh$. Поскольку число узлов растёт экспоненциально с чёрной высотой, отсюда выводится итоговая гарантия: высота красно-чёрного дерева с $n$ узлами не превышает $2 \log_2(n+1)$.

Примеры с разбором

Пример 1. Проверка корректности раскраски. Дано дерево:

        10(Ч)
       /     \
    5(Кр)    15(Ч)
    /   \        \
  3(Ч) 7(Ч)      20(Кр)

(здесь «Ч» — чёрный узел, «Кр» — красный узел; nil-листья на схеме не показаны, но по правилу 3 они всегда чёрные). Проверим правило 4: единственный красный узел $5$ имеет детьми $3$ и $7$ — оба чёрные, правило соблюдено; узел $20$ красный, его дети — nil-листья, то есть чёрные, тоже соблюдено. Проверим правило 5 (чёрная высота): путь $10 \to 5 \to 3 \to nil$ содержит чёрные узлы $10, 3, nil$ — три чёрных узла. Путь $10 \to 15 \to 20 \to nil$ содержит чёрные узлы $10, 15, nil$ — тоже три чёрных узла (красный $20$ в счёт не идёт). Все пути от корня до любого листа дают одинаковую чёрную высоту $3$ — дерево корректно.

Пример 2. Вставка и необходимость перекраски (без поворота). В дерево из примера 1 вставляется ключ $6$. По правилам BST он попадает правым ребёнком узла $5$ (поскольку $6 > 5$, но $6 < 7$, точнее становится левым ребёнком узла $7$, так как $6 < 7$). Новый узел по умолчанию красится в красный цвет (это стандартное правило вставки — новый узел всегда красный, чтобы не нарушить чёрную высоту существующих путей). Но узел $7$, родитель нового узла $6$, — чёрный, значит правило 4 (красный не может быть ребёнком красного) не нарушено, никаких дальнейших действий не требуется — дерево остаётся корректным сразу после вставки без единого поворота. Это ключевое отличие от АВЛ-дерева: не каждая вставка требует перестройки.

        10(Ч)
       /     \
    5(Кр)    15(Ч)
    /   \        \
  3(Ч) 7(Ч)      20(Кр)
        /
      6(Кр)

Пример 3. Вставка, требующая перекраски родителя и дяди («recoloring»). Продолжим с деревом из примера 2 и вставим ключ $4$. Он становится правым ребёнком узла $3$ (поскольку $3 < 4 < 5$) и по умолчанию красится в красный. Но родитель $3$ — чёрный, значит немедленного нарушения нет: узел $4$(Кр) — ребёнок чёрного узла $3$(Ч), правило 4 соблюдено. Разберём чуть более сложный вариант: если бы узел $3$ был красным (представим альтернативную раскраску, где $3$ покрашен в красный при сохранении корректности чёрной высоты за счёт другой конфигурации поддерева), то вставка красного ребёнка под красным узлом $3$ немедленно нарушила бы правило 4 — потребовалась бы либо перекраска родителя, дяди и деда (если «дядя» вставленного узла, то есть второй ребёнок деда, тоже красный), либо поворот с перекраской (если дядя чёрный или отсутствует). Такое ветвление реакции на конфликт — перекраска без поворота, если «дядя» красный, и поворот с перекраской, если «дядя» чёрный, — центральный алгоритмический приём вставки в красно-чёрное дерево, и именно он позволяет обойтись без изменения формы дерева в большинстве случаев, ограничиваясь лишь сменой цветов.

Почему это важно. Мягкость правил красно-чёрного дерева — не недостаток, а осознанный инженерный компромисс. Раз не каждая вставка требует поворота (как показал пример 2), а многие конфликты решаются простой перекраской нескольких узлов без изменения формы дерева (как в примере 3), среднее число структурных перестроек на одну операцию оказывается меньше, чем в строгом АВЛ-дереве. За это платится незначительно большей высотой дерева в худшем случае ($\approx 2\log_2 n$ против $\approx 1{,}44\log_2 n$ у АВЛ) — но для подавляющего большинства практических нагрузок, где вставки и удаления происходят так же часто, как и поиски, этот компромисс оказывается выгоднее.

Сравнение подходов и практическое применение

Интуиция: нет «лучшей» структуры — есть подходящая под нагрузку

Выбор между АВЛ-деревом, красно-чёрным деревом и B-деревом — это классический инженерный компромисс между строгостью гарантии и стоимостью её поддержания. Чем строже структура балансирует себя после каждой операции, тем быстрее в ней проходит поиск (высота ближе к теоретическому минимуму), но тем дороже обходятся вставка и удаление (перестройки требуются чаще). Понимание этого компромисса — то, что отличает разработчика, который «просто выбирает первую попавшуюся реализацию из библиотеки», от того, кто понимает, почему конкретная библиотека сделала именно такой выбор.

Сравнение по ключевым характеристикам

Сводка. АВЛ-дерево: высота $\le 1{,}44\log_2(n+2)$, строгий баланс, до двух поворотов на вставку и до $O(\log n)$ поворотов на удаление в худшем случае — оптимально при частых поисках и редких изменениях. Красно-чёрное дерево: высота $\le 2\log_2(n+1)$, мягкий баланс, не более трёх поворотов на любую вставку и не более трёх поворотов на любое удаление — оптимально при сопоставимой частоте поисков, вставок и удалений. B-дерево: узел хранит десятки-сотни ключей, высота крайне мала даже при огромном $n$, минимизирует число обращений к медленной внешней памяти — оптимально для индексов на диске.

Полезно взглянуть на эти три структуры и с точки зрения эмпирических измерений, которые регулярно публикуются в сравнительных бенчмарках стандартных библиотек: на типичной смешанной нагрузке (примерно поровну поисков, вставок и удалений случайных ключей) красно-чёрное дерево обычно опережает АВЛ-дерево по суммарному времени выполнения на несколько процентов — за счёт меньшего числа поворотов, — но проигрывает ему на нагрузке, где поиски составляют подавляющее большинство операций, а вставки и удаления единичны. Разница обычно не драматическая (десятки процентов, а не разы), и на многих реальных задачах её вообще не заметно на фоне других узких мест программы — что отчасти объясняет, почему стандартные библиотеки в основном остановились на одном универсальном выборе (красно-чёрном дереве) вместо того, чтобы предлагать разработчику вручную выбирать между несколькими реализациями словаря под конкретный профиль нагрузки. B-дерево в такое прямое сравнение по «числу сравнений» обычно не включают вовсе, потому что оно решает принципиально другую задачу — минимизацию не вычислительных операций, а операций ввода-вывода, — и сравнивать его с оперативными структурами имеет смысл только тогда, когда данные физически не помещаются в оперативную память целиком.

Пример 1. Где используется АВЛ-дерево. Классический пример — базы данных и структуры, где после однократного построения индекса основная нагрузка — это чтение (например, справочники с редкими обновлениями, статические словари, построенные один раз при старте приложения). Ещё один известный пример — реализация некоторых структур в файловых системах и в системах управления версиями, где после коммита данные почти не меняются, но интенсивно читаются. АВЛ-деревья также иногда предпочитают в задачах, где важна предсказуемость времени отклика поиска (например, в системах реального времени), потому что гарантия высоты у АВЛ строже, чем у красно-чёрного дерева, а значит, худший случай времени поиска — меньше.

Пример 2. Где используется красно-чёрное дерево. std::map и std::set в стандартной библиотеке C++ — практически всегда реализованы как красно-чёрное дерево (это не прописано жёстко в стандарте языка, но во всех массовых реализациях — libstdc++, libc++, MSVC STL — используется именно эта структура). TreeMap и TreeSet в Java — тоже красно-чёрное дерево, это явно задокументированное поведение стандартной библиотеки. Планировщик задач ядра Linux (Completely Fair Scheduler) использует красно-чёрное дерево для хранения процессов, упорядоченных по «времени ожидания выполнения» — структуру одновременно часто читают (кому передать процессор) и часто изменяют (добавление нового процесса, удаление завершённого), что ровно соответствует профилю нагрузки, для которого красно-чёрное дерево — оптимальный выбор.

Пример 3. Где используется B-дерево (и его варианты) — и связь с ML-практикой. Практически все индексы в реляционных СУБД — PostgreSQL, MySQL (InnoDB), Oracle, SQL Server — построены на B+-деревьях, разновидности B-дерева, где все данные хранятся только в листьях, а внутренние узлы содержат исключительно указатели для навигации. Причина выбора именно этой структуры, а не АВЛ или красно-чёрного дерева, — физика диска: чтение одного блока с диска или SSD стоит на порядки дороже, чем сравнение чисел в оперативной памяти, поэтому выгодно минимизировать число обращений к диску даже ценой того, что внутри одного узла придётся сделать больше сравнений в памяти. Узел B+-дерева обычно подгоняется по размеру ровно под один блок файловой системы (типично 4–16 килобайт), так что в нём помещаются сотни ключей — и высота дерева, индексирующего миллиарды записей, редко превышает 3–4 уровня. Когда ты как специалист по данным строишь WHERE-запрос с условием по индексированному столбцу, чтобы выгрузить подмножество данных для обучения модели, именно эта структура (а не «чистое» АВЛ- или красно-чёрное дерево) обеспечивает то, что запрос отрабатывает за миллисекунды на таблице с миллиардом строк. Тот же принцип — крупные узлы, минимизирующие число обращений к медленному хранилищу, логарифмическая высота — используется и в некоторых структурах для векторных баз данных, где «диском» выступает уже не жёсткий диск, а сетевой обмен между шардами при поиске ближайших соседей в распределённом индексе.

Почему это важно. Различие между АВЛ-деревом, красно-чёрным деревом и B-деревом — это не абстрактная теоретическая тонкость, а прямое следствие того, где физически хранятся данные и какова структура нагрузки. В оперативной памяти, где сравнение ключей практически бесплатно, а перестройка структуры — относительно дорогая операция, побеждает более «ленивое» красно-чёрное дерево. На диске, где каждое обращение к странице данных стоит на порядки дороже сравнения в памяти, побеждает структура с максимально широкими узлами и минимальной высотой — B-дерево. Осознанный выбор структуры данных под конкретный профиль нагрузки и физику хранения — ровно тот навык, который отличает инженера, способного объяснить, почему база данных выбрала B-tree-индекс, от того, кто просто знает, что «индексы ускоряют запросы».

Практика: 30 заданий

Базовые (задания 1–10)

Задание 1. Вставь числа $1, 2, 3, 4$ в обычное BST именно в этом порядке (без балансировки). Нарисуй получившееся дерево и укажи его высоту.

Задание 2. Для узла с левым поддеревом высоты $3$ и правым поддеревом высоты $1$ вычисли коэффициент баланса $BF$. Является ли такой узел допустимым в АВЛ-дереве?

Задание 3. Сформулируй своими словами, чем отличается «сбалансированное дерево» от «самобалансирующегося дерева».

Задание 4. В дереве, где корень имеет коэффициент баланса $+2$, а его правый ребёнок — коэффициент баланса $+1$, какой поворот нужно выполнить для восстановления баланса?

Задание 5. Дано красно-чёрное дерево, где путь от корня до одного листа содержит чёрные узлы в количестве $4$, а путь до другого листа — чёрные узлы в количестве $3$. Нарушено ли правило красно-чёрного дерева, и если да, то какое?

Задание 6. Может ли корень красно-чёрного дерева быть красным? Обоснуй ответ ссылкой на правило.

Задание 7. Для АВЛ-дерева с $n=15$ узлами оцени верхнюю границу высоты по формуле $h \le 1{,}44 \log_2(n+2)$ и сравни с высотой идеально сбалансированного дерева $\lceil \log_2(n+1) \rceil - 1$.

Задание 8. Объясни, почему в определении коэффициента баланса высота пустого поддерева условно считается равной $-1$, а не $0$.

Задание 9. В красно-чёрном дереве узел $A$ — красный. Какого цвета обязаны быть его дети? А какого цвета может быть его родитель?

Задание 10. Назови главное практическое отличие между реакцией на конфликт при вставке в АВЛ-дерево и при вставке в красно-чёрное дерево — с точки зрения того, как часто требуется менять форму дерева (выполнять повороты).

Средние (задания 11–20)

Задание 11. Вставь числа $5, 3, 8, 1, 4$ в обычное (небалансирующееся) BST в этом порядке. Нарисуй дерево, укажи его высоту и коэффициент баланса каждого узла.

Решение:

Шаг 1. Вставляем последовательно: $5$ — корень. $3 < 5$ — левый ребёнок $5$. $8 > 5$ — правый ребёнок $5$. $1 < 5, 1 < 3$ — левый ребёнок $3$. $4 < 5, 4 > 3$ — правый ребёнок $3$.

Шаг 2. Получившееся дерево:

Шаг 3. Высоты: узлы $1, 4, 8$ — листья, высота $0$, $BF=0$. Узел $3$: левое поддерево (узел $1$) высоты $0$, правое (узел $4$) высоты $0$, $BF(3)=0-0=0$. Узел $5$: левое поддерево (узел $3$ с детьми) высоты $1$, правое (узел $8$) высоты $0$, $BF(5)=0-1=-1$.

Шаг 4. Высота всего дерева $=2$.

Ответ: высота дерева $=2$; коэффициенты баланса: $BF(1)=BF(4)=BF(8)=0$, $BF(3)=0$, $BF(5)=-1$ — дерево уже удовлетворяет условиям АВЛ-дерева без единого поворота

Задание 12. В АВЛ-дерево с корнем $50$ (левое поддерево — узел $30$ с $BF=0$, правое — узел $70$ с $BF=0$) вставляется ключ $80$. Определи, какой узел разбалансируется, какого типа этот случай, и какой поворот нужен.

Задание 13. В условиях предыдущего задания в дерево дополнительно вставляется ключ $90$ (после $80$). Теперь определи, какой узел разбалансируется, тип случая и нужный поворот.

Задание 14. Дано красно-чёрное дерево: корень $20$(Ч) с левым ребёнком $10$(Кр) и правым ребёнком $30$(Ч). У узла $10$(Кр) есть правый ребёнок $15$(Ч). Проверь все пять правил красно-чёрного дерева для этой конфигурации (учитывая nil-листья как чёрные).

Задание 15. Даны два множества операций вставки одинаковых $7$ ключей в изначально пустое АВЛ-дерево и в изначально пустое обычное BST, в порядке $1,2,3,4,5,6,7$. Сравни итоговые высоты обеих структур.

Задание 16. Приведи пример последовательности вставок из трёх ключей, которая в обычном BST создаёт ситуацию «левый-правый» (требующую большого поворота при АВЛ-балансировке), и опиши, какие два элементарных поворота потребуются для исправления.

Задание 17. Объясни, почему при удалении узла в АВЛ-дереве перебалансировка может каскадом дойти до самого корня, в отличие от вставки, где обычно достаточно одного (одинарного или двойного) поворота.

Решение:

Шаг 1. При вставке высота поддерева, в которое был добавлен новый узел, либо не меняется (если баланс на этом уровне уже позволял добавить узел без роста высоты), либо увеличивается ровно на единицу — и как только выполняется поворот, восстанавливающий баланс в самой нижней точке конфликта, высота этого поддерева возвращается точно к значению до вставки, поэтому дальнейшие узлы вверх по пути к корню не видят никаких изменений.

Шаг 2. При удалении, наоборот, высота поддерева, из которого удалён узел, может уменьшиться на единицу — и после поворота, восстанавливающего локальный баланс, высота перестроенного поддерева иногда всё равно оказывается на единицу меньше, чем была до удаления (в отличие от вставки, где после поворота высота гарантированно восстанавливается).

Шаг 3. Раз высота поддерева могла реально уменьшиться, это уменьшение способно повлиять на коэффициент баланса родительского узла, затем его родителя, и так далее — в худшем случае цепочка перебалансировок доходит до корня.

Ответ: при вставке поворот восстанавливает исходную высоту поддерева, и распространение конфликта вверх останавливается сразу; при удалении высота поддерева после поворота иногда всё равно уменьшается, поэтому проверка баланса и возможные повороты могут потребоваться на каждом уровне вплоть до корня

Задание 18. В красно-чёрном дереве узел $X$ красный, а его «дядя» (второй ребёнок деда) — тоже красный. Какая реакция требуется по стандартному алгоритму вставки — перекраска или поворот, и почему?

Задание 19. Дано дерево из $31$ узла. Оцени верхнюю границу высоты для идеально сбалансированного дерева, для АВЛ-дерева (по формуле $1{,}44\log_2(n+2)$) и для красно-чёрного дерева (по формуле $2\log_2(n+1)$). Сравни все три оценки.

Задание 20. Опиши на словах (без формального доказательства), почему из правил 4 и 5 красно-чёрного дерева следует, что самый длинный путь от корня до листа не может быть более чем вдвое длиннее самого короткого.

Продвинутые (задания 21–30)

Задание 21. В базу данных с автоинкрементным первичным ключом вставляется $n=10^7$ записей строго по возрастанию. Оцени (в порядке величины) число сравнений для поиска одной записи в: а) обычном BST; б) АВЛ-дереве; в) B-дереве с коэффициентом ветвления $200$.

Задание 22. Постройте АВЛ-дерево пошаговой вставкой чисел $1, 2, 3, 4, 5, 6, 7$ по порядку, выполняя необходимые повороты после каждой вставки, которая приводит к нарушению баланса. Опиши финальную структуру.

Решение:

Шаг 1. Вставка $1$: дерево — просто узел $1$.

Шаг 2. Вставка $2$: узел $2$ становится правым ребёнком $1$. $BF(1)=+1$ — допустимо, поворот не нужен.

Шаг 3. Вставка $3$: узел $3$ идёт вправо от $2$. Теперь $BF(1)=+2$ (случай «правый-правый», так как $BF(2)=+1\ge0$). Левый поворот вокруг $1$: новый корень $2$, левый ребёнок $1$, правый ребёнок $3$.

Шаг 4. Вставка $4$: идёт вправо от $3$. $BF(3)$ становится $+1$, $BF(2) = h(\text{право})-h(\text{лево}) = 1-0=+1$ — всё ещё допустимо.

Шаг 5. Вставка $5$: идёт вправо от $4$. Теперь у узла $3$ $BF=+2$ (случай «правый-правый», $BF(4)=+1$). Левый поворот вокруг $3$: поддерево $3$ заменяется на $4$ с детьми $3$ и $5$. После этого пересчитываем корень: $BF(2) = h(\text{право, т.е. поддерево с корнем }4) - h(\text{лево, узел }1) = 1-0=+1$ — допустимо.

Шаг 6. Вставка $6$: идёт в поддерево $4$, вправо от $5$. У узла $4$ теперь $BF=+2$ (случай «правый-правый», $BF(5)=+1$). Левый поворот вокруг $4$: поддерево заменяется на $5$ с детьми $4$ и $6$. Корень $2$: $BF(2) = h(\text{право, поддерево }5) - h(\text{лево, узел }1)= 1-0=+1$... на самом деле после этого шага высота правого поддерева корня стала $2$ (у $5$ есть дети $4$ и $6$, у $4$ есть ребёнок $3$), значит $BF(2)=2-0=+2$ — требуется поворот и на уровне корня: левый поворот вокруг $2$. Новый корень — $4$ (поднявшийся из правого поддерева), с левым поддеревом $\{1,2,3\}$ (корень $2$, дети $1$ и $3$) и правым поддеревом $\{5,6\}$ (корень $5$, ребёнок $6$).

Шаг 7. Вставка $7$: идёт вправо от $6$. У узла $5$ $BF=+2$ (случай «правый-правый»), левый поворот вокруг $5$ даёт поддерево с корнем $6$, детьми $5$ и $7$. Финальная проверка корня $4$: левое поддерево ($2$ с детьми $1,3$) высоты $1$, правое ($6$ с детьми $5,7$) высоты $1$ — $BF(4)=0$, баланс полный.

Ответ: финальное АВЛ-дерево — корень $4$, левое поддерево: корень $2$ с детьми $1$ и $3$; правое поддерево: корень $6$ с детьми $5$ и $7$ — идеально сбалансированное дерево высоты $2$ на всех семи ключах, несмотря на изначально «враждебный» возрастающий порядок вставки

Задание 23. Объясни, почему для реализации кэша LRU (least recently used) с требованием быстрого поиска по ключу и быстрого удаления самого старого элемента красно-чёрное дерево обычно не является первым выбором, хотя формально могло бы обеспечить нужные асимптотики.

Задание 24. В индексе PostgreSQL используется B+-дерево с коэффициентом ветвления около $300$ (типичный порядок для узла размером 8 килобайт с ключами типа integer). Оцени высоту дерева, индексирующего $5 \times 10^9$ строк, и сравни с гипотетическим АВЛ-деревом на том же числе элементов, полностью размещённым в оперативной памяти.

Задание 25. Даны два красно-чёрных дерева с одинаковым числом узлов $n=63$: в одном все узлы, кроме листьев, чёрные (то есть красных узлов совсем нет), в другом — почти половина внутренних узлов красная. У какого из них высота ближе к теоретическому минимуму $\log_2(n+1)-1$, и почему?

Задание 26. Реализация красно-чёрного дерева в стандартной библиотеке C++ (std::map) не проверяет условие $BF\in\{-1,0,1\}$ в каждом узле. Объясни, почему в этом нет противоречия с тем, что std::map всё равно гарантирует $O(\log n)$ на все основные операции.

Задание 27. В векторном индексе для поиска ближайших соседей алгоритм HNSW строит многоуровневую графовую структуру, где верхние уровни содержат экспоненциально меньше узлов, чем нижние, и поиск начинается с самого верхнего, разреженного уровня. В чём концептуальное сходство этой идеи с балансировкой бинарных деревьев поиска, разобранной в этом уроке?

Решение:

Шаг 1. В сбалансированном бинарном дереве поиска идея логарифмической сложности достигается за счёт того, что на каждом шаге спуска от корня к листу количество оставшихся «кандидатов» примерно вдвое сокращается — высота дерева при этом растёт как $\log_2 n$ от общего числа элементов.

Шаг 2. В HNSW многоуровневая структура достигает похожего эффекта иначе: поиск сначала идёт по самому разреженному верхнему уровню, где переходы между узлами покрывают большие «расстояния» в пространстве данных, а затем спускается на более плотные нижние уровни для уточнения — то есть тоже логарифмически сокращает область поиска с каждым уровнем, вместо того чтобы перебирать все точки на одном плоском уровне.

Шаг 3. Общая идея в обоих случаях одна: вместо линейного перебора всех элементов, структура данных заранее организована в иерархию, которая на каждом шаге отбрасывает бо́льшую часть кандидатов, и глубина этой иерархии растёт логарифмически, а не линейно, от общего числа элементов.

Ответ: сходство — в принципе иерархического сокращения пространства поиска: и балансированное дерево, и многоуровневый граф HNSW организованы так, что глубина структуры (и, соответственно, время поиска) растёт логарифмически от числа элементов, а не линейно, за счёт заранее выстроенной иерархии «от общего к частному»

Задание 28. Оцени (без точного построения) минимальное и максимальное возможное число красных узлов в корректном красно-чёрном дереве с чёрной высотой корня $bh=4$ и общим числом узлов $n=31$, все из которых — внутренние (не считая nil-листьев).

Решение:

Шаг 1. Минимальное число красных узлов — $0$: дерево, где все узлы чёрные, полностью допустимо по правилам (правило 4 не запрещает отсутствие красных узлов вовсе), и при чёрной высоте $4$ такое дерево — это идеально сбалансированное дерево с $2^4-1=15$ узлами. Но нам дано $n=31$ — значит, при чёрной высоте ровно $4$ и всех чёрных узлах число узлов было бы $15$, а не $31$, то есть для получения $31$ узла при той же чёрной высоте часть узлов обязана быть красной (чтобы «вместить» больше узлов без увеличения чёрной высоты).

Шаг 2. Максимальное число красных узлов ограничено правилом 4: красные узлы не могут идти подряд, значит между чёрными узлами дерева они могут «прослаиваться», но не более чем в половину общего числа узлов в худшем регулярном случае — для дерева с чёрной высотой $4$ теоретический максимум узлов (с учётом максимально возможного использования красных прослоек) может доходить почти до $2\cdot(2^4-1)+1 = 31$, то есть именно наш случай $n=31$ близок к максимально допустимому использованию красных узлов при данной чёрной высоте.

Шаг 3. Отсюда следует, что при $n=31$ и $bh=4$ дерево близко к предельному случаю: значительная часть узлов (порядка половины, то есть около $15$–$16$) — красные, поскольку именно эта конфигурация позволяет «вместить» $31$ узел при ограниченной чёрной высоте $4$.

Ответ: при $bh=4$ дерево из $15$ узлов возможно вообще без красных узлов; чтобы вместить все $31$ узел при той же чёрной высоте, около половины узлов (порядка $15$–$16$) должны быть красными — это иллюстрирует, как именно красные узлы позволяют красно-чёрному дереву быть заметно «гуще» чисто чёрного дерева при той же чёрной высоте

Задание 29. Приведи содержательный (не строго формальный) аргумент, почему АВЛ-дерево гарантированно выполняет не более одного (одинарного или двойного) поворота на каждую вставку, а красно-чёрное дерево — не более трёх поворотов на любую вставку.

Решение:

Шаг 1. В АВЛ-дереве после вставки нарушение баланса может возникнуть только в одном, самом нижнем узле на пути от места вставки до корня (первом узле, чей коэффициент баланса вышел за $\{-1,0,1\}$). Поворот (одинарный или двойной) в этой точке восстанавливает исходную высоту поддерева до значения, которое было до вставки, — а значит, все узлы выше по пути к корню вообще не замечают, что что-то произошло, и дальнейшие проверки не выявляют нового нарушения.

Шаг 2. В красно-чёрном дереве вставленный узел всегда красный, поэтому конфликт может возникнуть только если его родитель тоже красный — и тогда возможны два сценария: либо «дядя» тоже красный (решается перекраской, без поворотов, но конфликт может подняться выше и повториться, однако это не поворот, а лишь перекраска — цикл перекрасок не требует ни одного поворота), либо «дядя» чёрный или отсутствует — тогда требуется один или два поворота (в зависимости от того, с какой стороны находится вставленный узел относительно родителя и деда), и после этого поворота структурный конфликт гарантированно исчерпан на этом уровне.

Шаг 3. Поскольку случай «дядя чёрный» возникает не более одного раза за всю цепочку исправлений (после единственного такого поворота дальнейшего распространения конфликта вверх уже не происходит), общее число поворотов на одну вставку в красно-чёрном дереве ограничено малой константой (не более двух-трёх, в зависимости от точной формулировки алгоритма), даже если цепочка перекрасок перед этим поднялась через много уровней.

Ответ: в обоих случаях структурная перестройка (поворот) локализует и «закрывает» конфликт сразу после её выполнения — разница в том, что у АВЛ-дерева единственный поворот всегда достаточен благодаря строгому условию баланса, а у красно-чёрного дерева перед единственным необходимым поворотом может понадобиться несколько раундов чистой перекраски (не поворотов), после чего требуется не более двух-трёх поворотов для окончательного исправления

Задание 30. Спроектируй (в общих чертах, без кода) выбор структуры данных для трёх разных сценариев: (а) словарь синонимов в текстовом редакторе, который загружается один раз при старте и после этого только читается; (б) очередь заявок в биржевом стакане, где заявки на покупку/продажу постоянно добавляются и удаляются, а нужно быстро находить лучшую цену; (в) индекс для таблицы из миллиардов строк в реляционной СУБД, хранящейся на SSD. Обоснуй выбор для каждого сценария.

Решение:

Шаг 1 (сценарий а). Нагрузка почти целиком состоит из чтений после однократного построения — это классический профиль для строгой балансировки. Оптимальный выбор — АВЛ-дерево (или даже просто идеально сбалансированное статическое дерево, построенное один раз из отсортированного массива, если структура вообще никогда не изменяется после загрузки): минимальная высота даёт максимально быстрый поиск, а редкость операций изменения делает неважной более высокую стоимость перебалансировки при возможных редких обновлениях.

Шаг 2 (сценарий б). Заявки постоянно добавляются и удаляются, частота изменений сопоставима с частотой запросов («лучшая цена» — это, по сути, поиск минимума/максимума, что для сбалансированного дерева тоже $O(\log n)$ через спуск в крайний левый/правый узел). Здесь оптимален красно-чёрное дерево: частые вставки и удаления обходятся дешевле благодаря более редким поворотам по сравнению с АВЛ, при этом высота остаётся логарифмической, что достаточно для быстрого поиска экстремума. Именно такой профиль нагрузки типичен для биржевых стаканов и планировщиков задач.

Шаг 3 (сценарий в). Данные не помещаются целиком в оперативную память и хранятся на медленном по сравнению с RAM носителе (SSD, хоть и быстрее жёсткого диска, всё равно на порядки медленнее оперативной памяти на операцию произвольного доступа). Здесь решающий фактор — минимизация числа обращений к внешнему хранилищу, а не число сравнений в памяти. Оптимальный выбор — B+-дерево с большим коэффициентом ветвления, подогнанным под размер страницы файловой системы: такая структура даёт высоту в единицы уровней даже при миллиардах строк, что напрямую означает минимальное число операций ввода-вывода на один запрос.

Ответ: (а) АВЛ-дерево — read-heavy нагрузка требует максимально строгого баланса; (б) красно-чёрное дерево — сопоставимая частота вставок/удалений и запросов требует более дешёвой перебалансировки; (в) B+-дерево — данные на диске требуют минимизации числа обращений к внешней памяти за счёт крупных узлов и малой высоты

Частые ошибки

❌ Ошибка: Считать, что любое бинарное дерево поиска автоматически работает за $O(\log n)$.

✅ Правильно: Гарантия $O(\log n)$ справедлива только для сбалансированных деревьев; обычное BST без механизма самобалансировки может выродиться в структуру, эквивалентную связному списку.

💡 Почему: Алгоритм вставки в обычное BST не имеет встроенного механизма контроля формы дерева — при неудачном (например, отсортированном) порядке вставки высота растёт линейно, а не логарифмически.

❌ Ошибка: Путать коэффициент баланса АВЛ-дерева с высотой узла — считать, что $BF(v)$ равен высоте узла $v$.

✅ Правильно: Коэффициент баланса — это разница высот правого и левого поддеревьев узла, а не высота самого узла.

💡 Почему: Смешение этих понятий приводит к неправильному определению момента, когда нужен поворот, и к ошибкам при выборе типа поворота (левый-левый, правый-правый, левый-правый, правый-левый).

❌ Ошибка: При обнаружении разбалансировки узла в АВЛ-дереве выполнять поворот, ориентируясь только на знак коэффициента баланса самого разбалансированного узла, без учёта коэффициента баланса его перегруженного ребёнка.

✅ Правильно: Тип нужного поворота (одинарный или двойной) определяется комбинацией знаков $BF$ узла и его перегруженного ребёнка — только по знаку узла нельзя различить, например, случаи «правый-правый» и «правый-левый».

💡 Почему: Применение одинарного поворота там, где нужен двойной, не восстанавливает баланс дерева — результат остаётся разбалансированным даже после «исправления».

❌ Ошибка: Считать, что в красно-чёрном дереве количество красных и чёрных узлов должно быть примерно одинаковым.

✅ Правильно: Правила красно-чёрного дерева не требуют никакого конкретного соотношения числа красных и чёрных узлов — единственное требование касается равенства чёрной высоты по всем путям и запрета двух красных узлов подряд.

💡 Почему: В корректном красно-чёрном дереве число красных узлов может варьироваться от нуля (дерево вообще без красных узлов — тоже полностью допустимая конфигурация) до почти половины всех узлов, в зависимости от истории вставок и удалений.

❌ Ошибка: Полагать, что красно-чёрное дерево «менее эффективно», чем АВЛ-дерево, потому что допускает бо́льшую высоту в худшем случае.

✅ Правильно: Бо́льшая допустимая высота красно-чёрного дерева компенсируется меньшим числом операций перестройки при вставках и удалениях — итоговая эффективность зависит от профиля нагрузки, а не только от высоты в худшем случае.

💡 Почему: Для нагрузки со сравнимой частотой чтений и изменений среднее время выполнения операций на красно-чёрном дереве может быть лучше, чем на АВЛ-дереве, несмотря на менее строгую гарантию высоты.

❌ Ошибка: Использовать B-дерево (или его аналог) внутри программы, работающей полностью в оперативной памяти, «по инерции», раз оно используется в базах данных.

✅ Правильно: Преимущество B-дерева (крупные узлы, минимизация обращений к диску) актуально именно для данных на внешнем, медленном по сравнению с RAM носителе; для структур, полностью помещающихся в оперативную память, красно-чёрное дерево или АВЛ-дерево обычно эффективнее.

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

Главное запомнить

✅ Обычное бинарное дерево поиска (урок 257) не имеет встроенной защиты от вырождения: при неудачном порядке вставки (например, строго по возрастанию) оно превращается в структуру, эквивалентную связному списку, с высотой $O(n)$ вместо $O(\log n)$

✅ Самобалансирующееся дерево — это структура, которая автоматически восстанавливает логарифмическую высоту после каждой вставки и удаления, а не полагается на удачный порядок операций

✅ АВЛ-дерево контролирует коэффициент баланса $BF(v) = h(\text{право}) - h(\text{лево})$ в каждом узле и требует $BF(v)\in\{-1,0,1\}$; высота АВЛ-дерева не превышает $\approx 1{,}44\log_2(n+2)$

✅ Восстановление баланса в АВЛ-дереве выполняется через один из четырёх поворотов: левый (случай «правый-правый»), правый (случай «левый-левый»), большой левый (случай «левый-правый», два поворота), большой правый (случай «правый-левый», два поворота)

✅ Красно-чёрное дерево гарантирует более мягкое условие через пять правил окраски узлов (красный/чёрный, корень чёрный, листья чёрные, у красного узла оба ребёнка чёрные, равная чёрная высота по всем путям); высота не превышает $2\log_2(n+1)$

✅ Многие конфликты при вставке в красно-чёрное дерево решаются простой перекраской узлов без изменения формы дерева — поэтому в среднем красно-чёрное дерево перестраивается реже, чем АВЛ, ценой чуть бо́льшей допустимой высоты

✅ АВЛ-дерево оптимально при редких изменениях и частых поисках (более строгий баланс — быстрее поиск); красно-чёрное дерево оптимально при сопоставимой частоте изменений и поисков (более дешёвая перебалансировка)

✅ B-дерево — родственная структура с укрупнёнными узлами (десятки-сотни ключей на узел), оптимизированная для хранения на медленной внешней памяти: лежит в основе почти всех индексов реляционных баз данных

✅ В реальных библиотеках std::map/std::set (C++) и TreeMap/TreeSet (Java) используют именно красно-чёрное дерево — компромисс между строгостью баланса и стоимостью перестройки, подходящий для универсального контейнера общего назначения

✅ Общая идея логарифмической по высоте, автоматически перестраиваемой структуры выходит далеко за пределы бинарных деревьев — та же философия лежит в основе структур для приближённого поиска ближайших соседей в векторных индексах (например, HNSW)

Связь с другими темами курса

🔙 Откуда пришли: Из урока 257 — бинарные деревья поиска и их базовые операции; проблема вырождения BST при неудачном порядке вставки, обозначенная там как ограничение, здесь получает развёрнутое решение через самобалансировку.

🔜 Куда идём:

Графы (урок 259) — следующий шаг обобщения: деревья — это частный случай графов без циклов, а многие структуры для баллансировки поиска (включая упомянутый HNSW) на самом деле строятся поверх более общих графовых структур
B-деревья и их варианты как отдельная, более глубокая тема — естественное продолжение идеи балансировки применительно к хранению данных на внешней памяти
Хеш-таблицы (урок 255) — альтернативный, не основанный на сравнении, подход к быстрому поиску: полезно сравнить асимптотику $O(1)$ в среднем для хеш-таблиц с $O(\log n)$ для сбалансированных деревьев и понимать, когда каждый подход предпочтительнее (деревья, в отличие от хеш-таблиц, сохраняют порядок ключей и поддерживают эффективный поиск диапазона)

🎯 В машинном обучении: Принцип автоматической балансировки, разобранный в этом уроке на примере АВЛ- и красно-чёрных деревьев, — прямой концептуальный предок структур, применяемых для эффективного приближённого поиска ближайших соседей (ANN) в больших векторных индексах, на которых строятся системы семантического поиска и retrieval-augmented generation. B-деревья, родственные структурам этого урока, лежат в основе индексов реляционных СУБД, через которые специалист по данным извлекает обучающие выборки из продакшен-систем — понимание того, почему запрос с условием по индексированному столбцу выполняется за миллисекунды даже на таблице из миллиардов строк, напрямую опирается на идею логарифмической высоты самобалансирующихся структур, изученную в этом уроке.

Интересные факты

📌 Статья Адельсон-Вельского и Ландиса 1962 года, в которой было впервые описано АВЛ-дерево, называлась «Один алгоритм организации информации» — предельно скромное, техническое название для работы, представившей первую в истории по-настоящему практичную самобалансирующуюся структуру данных, до сих пор изучаемую по всему миру и носящую имена авторов.

📌 Название «красно-чёрное дерево» — не изначальное. Рудольф Байер в 1972 году описал математически эквивалентную структуру под названием «симметричные бинарные B-деревья» без единого упоминания цвета; современная терминология с красными и чёрными узлами появилась только в 1978 году в работе Лео Гибаса и Роберта Седжвика, которые нашли более наглядный и интуитивный способ описать те же самые правила.

📌 В 2008 году Роберт Седжвик, один из авторов современной терминологии красно-чёрных деревьев, предложил упрощённый вариант — левонаклонное красно-чёрное дерево (left-leaning red-black tree, LLRB), которое добавляет дополнительное ограничение (красные узлы могут быть только левыми детьми) ради значительного упрощения кода вставки и удаления; вариант часто используется в учебных целях и в некоторых реализациях именно из-за простоты, хотя классическая версия остаётся более распространённой в промышленных библиотеках.

📌 Планировщик процессов ядра Linux (Completely Fair Scheduler, CFS), отвечающий за то, какому процессу передать процессор на каждом тике таймера, с 2007 года использует именно красно-чёрное дерево для хранения очереди процессов, упорядоченных по накопленному «виртуальному времени выполнения» — редкий пример структуры данных из учебника по алгоритмам, работающей внутри ядра операционной системы на миллиардах устройств по всему миру.

Лайфхаки и полезные трюки

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

💡 При отладке реализации АВЛ-дерева полезно писать отдельную функцию-валидатор, которая рекурсивно проверяет для каждого узла условие $BF\in\{-1,0,1\}$ и корректность высот, и вызывать её после каждой операции в тестах — это быстро вылавливает ошибки в логике поворотов, которые иначе проявились бы только на больших объёмах данных.

💡 Для красно-чёрного дерева аналогичный валидатор проверяет все пять правил сразу: цвет корня, отсутствие двух красных узлов подряд и равенство чёрной высоты по всем путям (последнее удобно реализовать рекурсивно — функция возвращает чёрную высоту поддерева или сигнализирует об ошибке, если у двух поддеревьев одного узла чёрные высоты не совпали).

💡 На собеседованиях и в учебных задачах реализацию красно-чёрного дерева с нуля почти никогда не спрашивают целиком (код вставки и удаления действительно объёмный) — куда чаще проверяют именно понимание: способность объяснить, почему правила гарантируют логарифмическую высоту, и разобрать конкретный пример на корректность. Стоит готовиться именно к этому, а не к заучиванию кода перекрасок наизусть.

💡 В своём коде на практике почти никогда не стоит реализовывать АВЛ- или красно-чёрное дерево с нуля вручную — в подавляющем большинстве языков есть готовые, тщательно протестированные реализации (std::map в C++, TreeMap в Java, модуль sortedcontainers в Python, где SortedList использует внутри более практичную для интерпретируемого языка структуру на основе списков блоков). Понимание принципов балансировки нужно не для того, чтобы писать их заново, а для того, чтобы осознанно выбирать между готовыми структурами и объяснять их поведение.

💡 Если стоит выбор между хеш-таблицей и сбалансированным деревом для конкретной задачи, задай себе один вопрос: нужен ли тебе упорядоченный обход, поиск ближайшего меньшего/большего элемента или поиск по диапазону значений? Если да — выбирай дерево, несмотря на то что хеш-таблица в среднем быстрее на «точечных» операциях; если нужен только точечный поиск по точному ключу без всякого порядка — хеш-таблица почти всегда выигрывает по константе.

Сбалансированные деревья — это тот редкий случай в информатике, когда красивая математическая идея (строгий контроль высоты через локальные инварианты в каждом узле) напрямую превращается в код, который прямо сейчас работает внутри операционной системы на твоём компьютере, внутри базы данных, к которой ты обращаешься за обучающей выборкой, и внутри стандартной библиотеки практически любого языка программирования. Ты увидел, как именно устроена страховка от вырождения обычного BST — через строгий коэффициент баланса АВЛ-дерева или через более гибкие правила окраски красно-чёрного дерева — и почему выбор между ними, а также между ними и B-деревом, определяется не абстрактным «что лучше», а конкретным профилем нагрузки и физикой хранения данных. Дальше в курсе эта идея иерархической, логарифмической организации данных прорастёт в графы — куда более общую структуру, частным случаем которой является дерево, — а вместе с ней и в алгоритмы обхода, без которых не обходится почти ни одна практическая задача, от поиска кратчайшего пути до анализа связей в графе знаний.

Понял тему? Закрепи в боте! 🚀

Попрактикуйся на задачах и получи персональные рекомендации от AI

💪 Начать тренировку

💬 Нашёл ошибку или есть вопрос по уроку? Написать в Telegram →