2-3 дерево: узел с несколькими ключами

Коротко

2-3 дерево балансируется иначе, чем АВЛ и красно-чёрное: не вращениями, а тем, что узлу разрешено хранить НЕСКОЛЬКО ключей и иметь НЕСКОЛЬКО детей. Узел бывает 2-узлом (1 ключ, 2 ребёнка) или 3-узлом (2 ключа, 3 ребёнка); ключи внутри узла упорядочены, а дети - это диапазоны между ними. Главное свойство: ВСЕ ЛИСТЬЯ на одном уровне ВСЕГДА - дерево идеально сбалансировано по построению. Достигается это ростом ВВЕРХ: при переполнении узел РАСЩЕПЛЯЕТСЯ, средний ключ уходит к родителю, и если переполняется корень - дерево становится выше на весь уровень сразу. Высота Θ(log n) гарантирована без всяких поворотов. Это прямой предок B-дерева - структуры дисковых индексов (следующий урок).

Если ты понимаешь устройство 2- и 3-узлов, почему все листья 2-3 дерева всегда на одном уровне и как расщепление и рост вверх это обеспечивают, листай до «Теперь сам».

Как думаешь, как балансировать без вращений

АВЛ и красно-чёрное держат баланс, ПОВОРАЧИВАЯ узлы после того, как перекос уже возник, - лечат постфактум. А можно ли устроить дерево так, чтобы оно НЕ МОГЛО перекоситься в принципе? Перекос берётся из того, что узел жёстко двоичный: один ключ, максимум два ребёнка, и лишний элемент вынужден уходить вглубь, удлиняя одну ветку. А что если разрешить узлу РАСТИ ВШИРЬ - вмещать второй ключ и третьего ребёнка? Тогда лишний элемент не обязан углублять дерево: он поместится в существующий узел. А когда и узел переполнится - он поделится и вытолкнет серединку наверх, подняв не ветку, а весь уровень. Так дерево растёт только ВВЕРХ и целиком - и остаётся идеально ровным.

На что это похоже

Картотека с ящиками, где в каждом ящике помещается один-два разделителя. Пришла новая карточка - кладёшь в нужный ящик. Ящик забился (в нём уже два разделителя, третий не влезает) - ты его ДЕЛИШЬ: средний разделитель отдаёшь ящику уровнем выше (в общий каталог), а оставшиеся два разъезжаются по двум ящикам. Если и верхний каталог переполнился - делишь и его, надстраивая ещё уровень над всей картотекой. Заметь: надстройка идёт СВЕРХУ и сразу для всего шкафа - поэтому все ящики нижнего ряда всегда на одной высоте. Никто не тянется вниз в одиночку.

Механизм: 2-узлы, 3-узлы, расщепление

Узел 2-3 дерева бывает двух видов:

2-узел: [a]         дети: <a | >a                 (1 ключ, 2 ребёнка)
3-узел: [a  b]      дети: <a | между a,b | >b      (2 ключа, 3 ребёнка), a < b

Поиск - как в BST, но на узле сравниваем с одним-двумя ключами и уходим в нужный диапазон. Вставка - всегда в ЛИСТ (спускаемся, как при поиске):

вставка:
  1. спуститься в нужный лист, добавить ключ в него
  2. если в листе стало 2 ключа (3-узел) - всё, помещается
  3. если переполнился (стало 3 ключа - «4-узел») - РАСЩЕПИТЬ:
        средний ключ поднять к РОДИТЕЛЮ, крайние два оставить двумя узлами
  4. если от этого переполнился родитель - расщепить и его, и так вверх
  5. если переполнился КОРЕНЬ - расщепить, средний ключ станет НОВЫМ корнем
        → дерево выросло на уровень, ВСЕ листья по-прежнему на одной глубине

Ключевой момент: дерево НИКОГДА не растёт вниз в одну ветку - только вверх и целиком, при расщеплении корня. Поэтому все листья всегда на одном уровне, а высота ≤ log₂(n+1) - идеальный баланс без единого вращения.

2-узел хранит 1 ключ и 2 ребёнка, 3-узел - 2 ключа и 3 ребёнка (дети - диапазоны между ключами). Все листья всегда на одной глубине - дерево идеально сбалансировано.

Правило

2-3 дерево балансируется многоключевыми узлами, а не вращениями. Узел - 2-узел (1 ключ, 2 ребёнка) или 3-узел (2 ключа, 3 ребёнка); дети соответствуют диапазонам между ключами. Все листья ВСЕГДА на одном уровне - дерево идеально сбалансировано по построению. Вставка идёт в лист; при переполнении узел РАСЩЕПЛЯЕТСЯ, средний ключ поднимается к родителю, а расщепление корня надстраивает дерево на уровень целиком. Высота ≤ log₂(n+1) гарантирована без поворотов. Это идея, из которой выросло B-дерево - структура дисковых индексов.

Разбор: почему все листья всегда на одном уровне

Это свойство, которое АВЛ и красно-чёрное лишь приближают, а 2-3 дерево держит ТОЧНО - и вот почему. Дерево меняет высоту ТОЛЬКО в одном случае: когда расщепляется КОРЕНЬ. Все остальные расщепления (в листе, в промежуточном узле) выталкивают средний ключ ВВЕРХ, к родителю, не меняя глубину листьев - они просто перераспределяют ключи по существующим уровням. А расщепление корня добавляет новый уровень СВЕРХУ, над всем деревом сразу: старый корень делится на два узла, а над ними встаёт новый корень с одним ключом. При этом КАЖДЫЙ лист опускается ровно на один уровень - все одновременно. Поэтому разница глубин между листьями не может возникнуть: рост всегда общий. Сравни с BST, где новый лист удлиняет ОДНУ ветку (отсюда перекос): в 2-3 дереве лишний элемент либо помещается вширь, либо поднимает серединку - вниз в одиночку никто не растёт.

Разбор: почему расщепление держит высоту логарифмической

Высота логарифмична, потому что каждый узел ВЕТВИТСЯ минимум надвое (2-узел) или натрое (3-узел), а элементы копятся ВШИРЬ, прежде чем углубить дерево. Прикинем по худшему случаю: самое «худое» 2-3 дерево высоты h - это все узлы 2-узлы, и даже оно, раз листья на одном уровне, полное двоичное: в нём 2^h − 1 ключей. Значит n ≥ 2^h − 1, и высота ≤ log₂(n+1) - и это ГАРАНТИЯ, а не «в среднем», потому что листья строго на одном уровне. Расщепление - дешёвая локальная операция (O(1) на узел), а цепочка расщеплений вверх не длиннее высоты, то есть O(log n). Так 2-3 дерево получает железный Θ(log n) на всё без вращений: баланс встроен в само правило «узел растёт вширь, а переполняясь, делится и растит дерево вверх целиком».

Что ломается без этого

Первая ошибка - вставлять не в лист, а в промежуточный узел: 2-3 дерево всегда добавляет ключ в ЛИСТ (как BST спускается до низа), а балансировку делает расщеплением снизу вверх; вставка «в середину» нарушит структуру. Вторая - при расщеплении поднять к родителю не СРЕДНИЙ ключ, а крайний: тогда диапазоны детей перестанут соответствовать ключам, инвариант сломается; наверх идёт именно медиана из трёх. Третья - забыть, что расщепление может пойти ЦЕПОЧКОЙ вверх до корня: остановиться на первом узле недостаточно, надо проверять родителя. Четвёртая - думать, что 2-3 дерево - просто «другой BST»: у него узел многоключевой, поиск сравнивает с одним-двумя ключами, и это принципиально для перехода к B-деревьям.

Зачем это в работе

2-3 дерево само по себе применяют редко, но оно - концептуальный мост к двум важным вещам. Первое: красно-чёрное дерево - это, по сути, 2-3(-4) дерево, ЗАКОДИРОВАННОЕ двоичными узлами с цветами (3-узел = чёрный узел с красным ребёнком). Поняв 2-3 дерево, понимаешь, ОТКУДА берутся правила цвета - они имитируют многоключевые узлы в двоичной форме. Второе и главное: B-дерево (следующий урок) - это то же 2-3 дерево, но с узлами на СОТНИ ключей, и именно оно лежит в основе индексов всех баз данных и файловых систем. Идея «узел растёт вширь, дерево - вверх целиком, листья всегда ровно» - то, что делает дисковые индексы низкими и быстрыми. Так что 2-3 дерево - маленькая модель большой и повсеместной структуры; разобравшись с ним, ты поймёшь и красно-чёрные деревья глубже, и B-деревья сразу.

Теперь сам

В 2-3 дерево, где корень - 3-узел [10 20] с листьями-детьми [5], [15], [25 30], вставляют 27. Что произойдёт и почему все листья останутся на одном уровне?

Ответ. Спускаемся: 27 > 20, идём в правого ребёнка - лист [25 30]. Добавляем 27 туда: лист становится [25 27 30] - это три ключа, переполнение («4-узел»). РАСЩЕПЛЯЕМ: средний ключ 27 поднимается к родителю (корню), а 25 и 30 остаются двумя отдельными 2-узлами. Корень был [10 20], получает 27 и становится [10 20 27] - тоже три ключа, тоже переполнение! Расщепляем и КОРЕНЬ: средний 20 становится новым корнем (2-узел [20]), а [10] и [27] - его дети; при этом [10] забирает прежних левых детей ([5] и [15]), а [27] - правых ([25] и [30]). Дерево выросло на уровень: новый корень [20], под ним [10] и [27], а под ними четыре листа [5] [15] [25] [30]. Все листья опустились ОДНОВРЕМЕННО на один уровень, поэтому по-прежнему на одной глубине - дерево осталось идеально сбалансированным. Рост пошёл вверх и целиком, а не одной веткой вниз.

Главное

2-3 дерево балансируется многоключевыми узлами, а не вращениями. Узел - 2-узел (1 ключ, 2 ребёнка) или 3-узел (2 ключа, 3 ребёнка); дети - диапазоны между ключами. ВСЕ ЛИСТЬЯ ВСЕГДА на одном уровне (идеальный баланс по построению), потому что дерево растёт только ВВЕРХ и ЦЕЛИКОМ: вставка идёт в лист, переполненный узел расщепляется (средний ключ - наверх), а расщепление корня надстраивает уровень над всем деревом сразу. Высота ≤ log₂(n+1) гарантирована без поворотов. Наверх при расщеплении идёт СРЕДНИЙ ключ; расщепление может пойти цепочкой до корня. 2-3 дерево - модель, из которой выросли красно-чёрное дерево (3-узел = чёрный + красный) и B-дерево (узлы на сотни ключей, дисковые индексы - следующий урок).