2-3-дерево

TL;DR

2-3 дерево (2-3 tree) — сбалансированное дерево поиска, в котором каждый внутренний узел имеет двух или трёх детей и хранит один или два ключа, а все внешние листья лежат на одной глубине. Благодаря тому, что у каждого узла не меньше двух детей, высота не превосходит [math]\displaystyle{ \log_2(n+1) }[/math], а благодаря тому, что не больше трёх, — не меньше [math]\displaystyle{ \log_3(n+1) }[/math]; дерево всегда идеально сбалансировано без хранения полей баланса. Вставка добавляет ключ в последний внутренний узел и при переполнении расщепляет узел, поднимая средний ключ в родителя; удаление заимствует ключ у брата-3-узла или сливает узлы. Все операции работают за [math]\displaystyle{ O(\log n) }[/math], а расщепления при вставке — амортизированно [math]\displaystyle{ O(1) }[/math]. 2-3 дерево — частный случай B-дерева (порядок 3) и родоначальник идеи, из которой выросли 2-3-4 деревья и красно-чёрные деревья.

Свойство	Значение
Класс	Сбалансированное дерево поиска; B-дерево порядка 3
Изобретение	Дж. Хопкрофт, около 1970 (2-3 деревья); обобщение — Байер и Маккрейт, 1972 [3][4]
Типы узлов	2-узел (1 ключ, 2 ребёнка), 3-узел (2 ключа, 3 ребёнка)
Балансировка	Идеальная: все листья на одной глубине
Высота	[math]\displaystyle{ \log_3(n+1) \le h \le \log_2(n+1) }[/math]
Поиск	[math]\displaystyle{ O(\log n) }[/math]
Вставка	[math]\displaystyle{ O(\log n) }[/math]; расщепления амортизированно [math]\displaystyle{ O(1) }[/math]
Удаление	[math]\displaystyle{ O(\log n) }[/math] (заимствование или слияние)
Память	[math]\displaystyle{ O(n) }[/math]; узел хранит 1–2 ключа и 2–3 ссылки, поля баланса не нужны
Родственники	2-3-4-дерево, B-дерево, красно-чёрное дерево (соответствие)
Где встречается	учебная основа B-деревьев; идея используется в индексах СУБД и файловых систем

Определения

2-3 дерево — дерево поиска, в котором:

1. каждый внутренний узел имеет либо двух, либо трёх детей;
2. узел с двумя детьми (2-узел) хранит один ключ, узел с тремя детьми (3-узел) — два ключа;
3. ключи в узле упорядочены, и для 3-узла с ключами [math]\displaystyle{ k_1 \lt k_2 }[/math]: левое поддерево содержит ключи [math]\displaystyle{ \lt k_1 }[/math], среднее — между [math]\displaystyle{ k_1 }[/math] и [math]\displaystyle{ k_2 }[/math], правое — [math]\displaystyle{ \gt k_2 }[/math];
4. все листья находятся на одной глубине (дерево идеально сбалансировано).

2-узел — узел с одним ключом и двумя детьми. 3-узел — узел с двумя ключами и тремя детьми. Лист — внешний узел, не хранящий ключей. В этой статье ключи хранятся только во внутренних узлах, а все внешние листья лежат на одной глубине; в компактной реализации внешние листья не хранятся, и флаг leaf означает последний внутренний узел.

Высота [math]\displaystyle{ h }[/math]. Внутренний узел имеет не менее двух детей, поэтому в дереве высоты [math]\displaystyle{ h }[/math] не менее [math]\displaystyle{ 2^h }[/math] внешних листьев, откуда [math]\displaystyle{ h \le \log_2 L }[/math]. С другой стороны, не более трёх детей даёт [math]\displaystyle{ h \ge \log_3 L }[/math].

Соответствие. 2-3 дерево — это B-дерево порядка (степени) 3. Обобщение узлов до «2, 3 или 4 детей» даёт 2-3-4 дерево, а через кодировку 3-узлов красными рёбрами — красно-чёрное дерево.

Обозначения. [math]\displaystyle{ n }[/math] — число ключей; [math]\displaystyle{ L }[/math] — число внешних листьев; [math]\displaystyle{ h }[/math] — высота; [math]\displaystyle{ \log }[/math] — двоичный, если не оговорено.

Рис. 1. 2-узлы и 3-узлы; все листья на одной глубине. Высота заключена между [math]\displaystyle{ \log_3 L }[/math] и [math]\displaystyle{ \log_2 L }[/math].

Мотивация и интуиция

Двоичное дерево поиска простое, но легко вырождается в список. Сбалансированные BST (АВЛ, КЧ) чинят это поворотами и хранением баланса. 2-3 дерево предлагает другой подход: разрешить узлам хранить больше одного ключа. Как только узлу разрешено иметь три ребёнка, дереву становится «тесно» вырождаться: у внутренних узлов минимум два ребёнка, а значит, высота уже не может превысить [math]\displaystyle{ \log_2(n+1) }[/math].

Ключевая идея — локальность балансировки. Когда последний внутренний узел переполняется (в него попадает третий ключ), узел временно становится 4-узлом и расщепляется: средний ключ уходит в родителя, а крайние образуют два 2-узла. Баланс восстанавливается локально, а если переполнится родитель — расщепление продолжается вверх. Единственный случай, когда высота меняется, — расщепление корня. Аналогично удаление «разгружает» узел заимствованием у соседа или слиянием.

Так 2-3 дерево поддерживает идеальную балансировку структурно, без единого поля высоты или цвета: инварианты формы гарантируют [math]\displaystyle{ \Theta(\log n) }[/math] сами по себе. Это делает 2-3 деревья удобной учебной моделью и мостиком к B-деревьям и красно-чёрным деревьям.

Устройство

Узел 2-3 дерева — это небольшая запись с массивом ключей (до двух) и массивом детей (до трёх):

• 2-узел: keys[0], child[0], child[1].
• 3-узел: keys[0], keys[1], child[0], child[1], child[2].

Листья (внешние узлы) не хранят ключей и все находятся на одном уровне. Поиск спускается от корня, сравнивая ключ с одним или двумя ключами узла и выбирая ребёнка; при совпадении — успех.

Инварианты (поддерживаются всеми операциями):

1. Порядок: ключи вдоль обхода слева направо возрастают.
2. Степень: у внутреннего узла 2 или 3 ребёнка; у листа — 0.
3. Совершенная балансировка: все листья на одной глубине.

Именно третий инвариант и даёт [math]\displaystyle{ O(\log n) }[/math]: он сохраняется при вставках и удалениях автоматически.

Операции и алгоритмы

Операция: поиск (Search)

Идея. Спуск от корня: сравнить ключ с ключом (или двумя ключами) узла, выбрать нужного ребёнка.

Пошаговое описание.

1. В текущем узле найти позицию ключа среди keys[0..n-1].
2. Если ключ совпал — найдено.
3. Иначе при листе — не найдено; при внутреннем узле — спуститься в соответствующего ребёнка.

Инвариант. Искомый ключ, если есть, лежит в поддереве текущего узла.

Псевдокод.

Алгоритм Search(T, k)
1  cur ← root[T]
2  while cur ≠ NIL
3      i ← 0
4      while i < num[cur] and keys[cur][i] < k
5          i ← i + 1
6      if i < num[cur] and keys[cur][i] = k
7          return cur
8      if leaf[cur]
9          return NIL
10     cur ← child[cur][i]
11 return NIL

Сложность: O(log n) — не длиннее высоты.

Корректность: выбор ребёнка следует порядку ключей; свойство порядка гарантирует, что при наличии k спуск приведёт к нему.

Крайние случаи. Ключ меньше всех — спуск в child[0]; больше всех — в последнего ребёнка.

Операция: вставка (Insert)

Идея. Спуститься до последнего внутреннего узла и вставить ключ; при переполнении узла — расщепить его, подняв средний ключ в родителя (рекурсивно вверх).

Пошаговое описание.

1. Спуск до последнего внутреннего узла по ключу.
2. Вставка ключа в последний внутренний узел (он временно может стать 4-узлом с тремя ключами).
3. Если ключей стало три — расщепление: крайние остаются в двух 2-узлах, средний поднимается.
4. Если переполнился родитель — повторить расщепление выше.
5. Если расщепился корень — создать новый корень; высота растёт на 1.

Инвариант. После каждого шага дерево остаётся 2-3 деревом (порядок, степень, одна глубина внешних листьев); нарушением может быть лишь временное переполнение одного узла.

Псевдокод (рекурсивный, возвращает «подъём» при переполнении).

Алгоритм Insert(T, k)
1  (overflow, mid, right) ← Insert-Rec(root[T], k)
2  if overflow                            # расщепился корень
3      newRoot ← новый узел с ключом mid
4      child[newRoot][0] ← root[T];  child[newRoot][1] ← right
5      root[T] ← newRoot                  # высота +1

Алгоритм Insert-Rec(node, k)              # возвращает (overflow, mid, right)
6  if все дети node — внешние листья
7      вставить k в keys[node] (с сохранением порядка)
8      if num[node] ≤ 2
9          return (false, NIL, NIL)
10     keys[node] ← keys[node][0]         # левый 2-узел
11     right ← 2-узел с ключом keys[node][2] # правый 2-узел
12     return (true, keys[node][1], right)  # средний ключ — вверх
13 i ← 0
14 while i < num[node] and keys[node][i] < k
15     i ← i + 1
16 (overflow, mid, right) ← Insert-Rec(child[node][i], k)
17 if not overflow
18     return (false, NIL, NIL)
19 вставить mid в keys[node] (позиция i) и right в child[node] (позиция i+1)
20 if num[node] ≤ 2
21     return (false, NIL, NIL)
22 left  ← 2-узел с keys[node][0]
23 rightNode ← 2-узел с keys[node][2]
24 return (true, keys[node][1], rightNode)

Сложность: O(log n) времени; расщеплений не более высоты, амортизированно O(1) на вставку.

Корректность: расщепление заменяет один узел двумя на том же уровне, поэтому глубина внешних листьев не меняется; новый корень увеличивает глубину сразу всех внешних листьев.

Разбор на примере. Вставка 20 в 3-узел [15 | 25] даёт временный 4-узел [15 | 20 | 25], который расщепляется: ключ 20 поднимается, а 15 и 25 образуют два 2-узла (рис. 2). Если при этом переполнился и родитель, расщепление идёт выше; расщепление корня повышает высоту (рис. 3).

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

Рис. 2. Вставка в 3-узел: временный 4-узел расщепляется, средний ключ поднимается в родителя.

Рис. 3. Расщепление доходит до корня; корень разделяется, высота растёт на 1, а листья остаются на одном уровне.

Операция: удаление (Delete)

Идея. Удалить ключ; если узел «опустел» (стал недопустимым), восстановить инвариант заимствованием у соседа-3-узла или слиянием с соседом через ключ родителя.

Пошаговое описание.

1. Найти ключ; если он во внутреннем узле, заменить его ключом-предшественником из последнего внутреннего узла (как в BST).
2. Удалить ключ из последнего внутреннего узла.
3. Если последний внутренний узел опустел: - у соседа справа/слева есть 3-узел — заимствовать: перебросить ключ через родителя; - у соседей только 2-узлы — слить узел с соседом, опустив ключ родителя.
4. Если родитель потерял ребёнка и опустел — повторить пункт 3 выше.
5. Если корень опустел — сделать его единственного ребёнка новым корнем (высота −1).

Инвариант. Свойства порядка и одна глубина внешних листьев сохраняются; временным нарушением может быть лишь недостача ключей в одном узле.

Псевдокод (схема).

Алгоритм Delete(T, k)
1  найти ключ k в узле z
2  if k во внутреннем узле
3      заменить k его предшественником из последнего внутреннего узла;  z ← этот узел
4  удалить k из z
5  while z опустел и z ≠ root[T]
6      p ← parent[z]
7      if у соседа z есть три ребёнка        # 3-узел
8          заимствовать ключ у соседа через p (перераспределение)
9          break
10     else
11         слить z с соседом, опустив разделяющий ключ из p
12         z ← p                              # недостача поднялась выше
13 if root[T] опустел
14     root[T] ← единственный ребёнок root[T]   # высота −1

Сложность: O(log n) времени; слияние/заимствование — O(1), повторов не более высоты.

Корректность: каждое действие восстанавливает степень узлов, сохраняя одну глубину внешних листьев.

Крайние случаи. Удаление последнего ключа корня — последнего внутреннего узла — дерево пустеет. Удаление отсутствующего ключа — no-op.

Рис. 4. Опустевший 2-узел восстанавливают заимствованием у соседа-3-узла или слиянием с соседом; слияние может подняться до корня и уменьшить высоту.

Операции: минимум, максимум и обход

Min/Max — спуск в крайнего левого/правого ребёнка до листа, [math]\displaystyle{ O(\log n) }[/math]. Обход по возрастанию — симметричный обход: для 3-узла сначала левое поддерево, keys[0], среднее поддерево, keys[1], правое поддерево; [math]\displaystyle{ O(n) }[/math].

Реализация на C++

Реализация с вставкой (рекурсивное расщепление), поиском и проверкой инвариантов validate (порядок, степень, одна глубина листьев). Удаление оставлено как упражнение — оно заметно объёмнее.

#include <iostream>
#include <cassert>

template <typename K>
class TwoThreeTree {
    struct Node {
        int n = 0;                        // число ключей: 1 или 2
        K keys[2];
        Node* child[3] = {nullptr, nullptr, nullptr};
        bool leaf = true;                  // последний внутренний узел; внешние листья не хранятся
    };

    struct Split { bool overflow; K mid; Node* right; };

    Node* root_ = nullptr;

    Split insertRec(Node* node, const K& k) {
        if (node->leaf) {
            K tmp[3];
            int cnt = 0;
            bool placed = false;
            for (int j = 0; j < node->n; ++j) {
                if (!placed && k < node->keys[j]) { tmp[cnt++] = k; placed = true; }
                tmp[cnt++] = node->keys[j];
            }
            if (!placed) tmp[cnt++] = k;
            if (cnt <= 2) {
                for (int j = 0; j < cnt; ++j) node->keys[j] = tmp[j];
                node->n = cnt;
                return {false, K{}, nullptr};
            }
            // переполнение листа: расщепляем
            node->keys[0] = tmp[0];
            node->n = 1;
            Node* right = new Node();
            right->leaf = true;
            right->keys[0] = tmp[2];
            right->n = 1;
            return {true, tmp[1], right};
        }
        int i = 0;
        while (i < node->n && node->keys[i] < k) ++i;
        Split s = insertRec(node->child[i], k);
        if (!s.overflow) return {false, K{}, nullptr};

        // вставить ключ s.mid в позицию i и s.right в позицию i+1
        K keys[3];
        Node* ch[4];
        for (int j = 0; j < node->n; ++j) keys[j] = node->keys[j];
        for (int j = 0; j <= node->n; ++j) ch[j] = node->child[j];
        for (int j = node->n; j > i; --j) keys[j] = keys[j - 1];
        keys[i] = s.mid;
        for (int j = node->n + 1; j > i + 1; --j) ch[j] = ch[j - 1];
        ch[i + 1] = s.right;
        int nk = node->n + 1;

        if (nk <= 2) {
            for (int j = 0; j < nk; ++j) node->keys[j] = keys[j];
            for (int j = 0; j <= nk; ++j) node->child[j] = ch[j];
            node->n = nk;
            return {false, K{}, nullptr};
        }
        // переполнение внутреннего узла
        node->keys[0] = keys[0];
        node->n = 1;
        node->child[0] = ch[0];
        node->child[1] = ch[1];
        Node* right = new Node();
        right->leaf = false;
        right->keys[0] = keys[2];
        right->n = 1;
        right->child[0] = ch[2];
        right->child[1] = ch[3];
        return {true, keys[1], right};
    }

    static void destroy(Node* n) {
        if (!n) return;
        if (!n->leaf) for (int j = 0; j <= n->n; ++j) destroy(n->child[j]);
        delete n;
    }

    bool check(const Node* n, int depth, int& leafDepth,
               const K* lo, const K* hi) const {
        if (n->n < 1 || n->n > 2) return false;
        for (int j = 0; j < n->n; ++j) {
            if (lo && !(*lo < n->keys[j])) return false;
            if (hi && !(n->keys[j] < *hi)) return false;
            if (j > 0 && !(n->keys[j - 1] < n->keys[j])) return false;
        }
        if (n->leaf) {
            if (n->child[0] || n->child[1] || n->child[2]) return false;
            if (leafDepth == -1) leafDepth = depth;
            return depth == leafDepth;
        }
        for (int j = 0; j <= n->n; ++j) if (!n->child[j]) return false;
        for (int j = 0; j <= n->n; ++j) {
            const K* l = (j == 0) ? lo : &n->keys[j - 1];
            const K* h = (j == n->n) ? hi : &n->keys[j];
            if (!check(n->child[j], depth + 1, leafDepth, l, h)) return false;
        }
        return true;
    }

public:
    TwoThreeTree() = default;
    ~TwoThreeTree() { destroy(root_); }
    TwoThreeTree(const TwoThreeTree&) = delete;
    TwoThreeTree& operator=(const TwoThreeTree&) = delete;

    void insert(const K& k) {
        if (!root_) {
            root_ = new Node();
            root_->keys[0] = k;
            root_->n = 1;
            root_->leaf = true;
            return;
        }
        Split s = insertRec(root_, k);
        if (s.overflow) {
            Node* newRoot = new Node();
            newRoot->leaf = false;
            newRoot->n = 1;
            newRoot->keys[0] = s.mid;
            newRoot->child[0] = root_;
            newRoot->child[1] = s.right;
            root_ = newRoot;
        }
    }

    bool contains(const K& k) const {
        const Node* cur = root_;
        while (cur) {
            int i = 0;
            while (i < cur->n && cur->keys[i] < k) ++i;
            if (i < cur->n && !(k < cur->keys[i])) return true;   // равенство
            if (cur->leaf) return false;
            cur = cur->child[i];
        }
        return false;
    }

    bool validate() const {
        if (!root_) return true;
        int leafDepth = -1;
        return check(root_, 0, leafDepth, nullptr, nullptr);
    }
};

int main() {
    TwoThreeTree<int> t;
    for (int v : {10, 20, 5, 15, 25, 30, 28, 35, 40, 50, 3, 7})
        t.insert(v);
    assert(t.validate());
    for (int v : {10, 20, 5, 15, 25, 30, 28, 35, 40, 50, 3, 7})
        assert(t.contains(v));
    assert(!t.contains(99));

    TwoThreeTree<int> u;                       // много вставок с расщеплениями
    for (int i = 1; i <= 200; ++i) u.insert((i * 37) % 200);
    assert(u.validate());

    std::cout << "ok\n";
    return 0;
}

Замечания по реализации.

• При переполнении узел временно содержит три ключа; расщепление оставляет по одному ключу в двух узлах и поднимает средний.
• Наследование ребёнка child[i+1] при вставке ключа — частый источник ошибок; сверяйтесь с псевдокодом.
• validate проверяет все три инварианта, включая одну глубину внешних листьев.
• В коде внешние листья не хранятся: leaf == true означает последний внутренний узел, а его дети — внешние листья. Глубина в validate считается по последним внутренним узлам (на 1 меньше глубины внешних листьев) и не влияет на проверку баланса.
• Удаление реализуется тем же рекурсивным приёмом с «подъёмом недостачи», но содержит больше случаев (заимствование/слияние).

Сводная таблица сложности

Операция	Худший	Амортизированная	Замечание
Search	[math]\displaystyle{ O(\log n) }[/math]	[math]\displaystyle{ O(\log n) }[/math]	сравнение с 1–2 ключами на узел
Insert	[math]\displaystyle{ O(\log n) }[/math]	[math]\displaystyle{ O(\log n) }[/math]	расщеплений амортизированно [math]\displaystyle{ O(1) }[/math]
Delete	[math]\displaystyle{ O(\log n) }[/math]	[math]\displaystyle{ O(\log n) }[/math]	заимствование/слияние за [math]\displaystyle{ O(1) }[/math]
Min / Max	[math]\displaystyle{ O(\log n) }[/math]	[math]\displaystyle{ O(\log n) }[/math]	спуск к листу
Traversal	[math]\displaystyle{ O(n) }[/math]	[math]\displaystyle{ O(n) }[/math]	симметричный обход
Память	[math]\displaystyle{ O(n) }[/math]	—	1–2 ключа и 2–3 ссылки на узел

Примечание. Число расщеплений при вставке может достигать высоты, но амортизированно их [math]\displaystyle{ O(1) }[/math]: каждое расщепление одного узла оплачивается предшествующими вставками — тот же аргумент, что и у двоичного счётчика (сравните с двоичной кучей и биномиальной кучей).

Рис. 5. Высота между [math]\displaystyle{ \log_3 n }[/math] и [math]\displaystyle{ \log_2 n }[/math]; операции логарифмические, расщепления амортизированно константны.

Трассировка примера

Вставим ключи [math]\displaystyle{ 10, 20, 5, 15, 25, 30 }[/math]. Показываем состояние после каждой вставки (ключи узла через |).

Шаг	Ключ	Действие	Дерево (в порядке возрастания)
1	10	первый лист	[10]
2	20	в лист [10]	`[10	20]`
3	5	в лист `[10	20]` → расщепление	корень [10], дети [5], [20]
4	15	спуск к [20] (между 10 и 20)	корень [10], дети [5], `[15	20]`
5	25	в лист `[15	20]` → расщепление	корень `[10	20], дети [5], [15], [25]`
6	30	в лист [25]	корень `[10	20], дети [5], [15], [25	30]`

На шаге 3 расщепился лист, на шаге 5 — лист, а его средний ключ (20) поднялся в корень, превратив его в 3-узел; высота не менялась. Все ключи выходят в порядке возрастания, validate() подтверждает инварианты.

Корректность и оценка сложности

Лемма 1 (граница высоты). 2-3 дерево с [math]\displaystyle{ n }[/math] ключами имеет высоту [math]\displaystyle{ h }[/math], где [math]\displaystyle{ \log_3 n \le h \le \log_2 n }[/math].

Доказательство. У каждого внутреннего узла от 2 до 3 детей, все листья на глубине [math]\displaystyle{ h }[/math]. Число листьев [math]\displaystyle{ L }[/math] удовлетворяет [math]\displaystyle{ 2^h \le L \le 3^h }[/math]. Так как ключей [math]\displaystyle{ n = L - 1 }[/math] (или [math]\displaystyle{ L \approx n }[/math]), то [math]\displaystyle{ 2^h \le n }[/math] и [math]\displaystyle{ n \le 3^h }[/math], откуда [math]\displaystyle{ \log_3 n \le h \le \log_2 n }[/math]. [math]\displaystyle{ \blacksquare }[/math]

Теорема 2 (корректность вставки). После Insert дерево остаётся 2-3 деревом с тем же множеством ключей плюс новый.

Доказательство. Расщепление переполненного узла заменяет один узел двумя (или, на верхнем уровне, создаёт новый корень), сохраняя порядок ключей и глубину листьев: крайние ключи остаются на прежней глубине, средний поднимается на уровень выше, где для него освобождается место; при расщеплении корня все листья углубляются на один уровень одновременно. Инварианты порядка и степени восстанавливаются на каждом уровне, значит, и во всём дереве. [math]\displaystyle{ \blacksquare }[/math]

Теорема 3 (корректность удаления). После Delete дерево остаётся 2-3 деревом без удалённого ключа.

Доказательство. Заимствование переносит ключ из соседа-3-узла через родителя, сохраняя и порядок, и число детей; слияние объединяет два 2-узла и разделяющий ключ родителя в один 3-узел, уменьшая число детей родителя на один — недостача поднимается вверх и в итоге поглощается, а опустевший корень заменяется единственным ребёнком. Все листья остаются на одной глубине. [math]\displaystyle{ \blacksquare }[/math]

Оценка сложности. Высота [math]\displaystyle{ O(\log n) }[/math], на каждом уровне [math]\displaystyle{ O(1) }[/math] работы (сравнения, один раскол или слияние) — операции за [math]\displaystyle{ O(\log n) }[/math]. Число расщеплений при вставке амортизированно [math]\displaystyle{ O(1) }[/math] (аргумент счётчика: узел можно расщепить лишь после того, как его заполняли вставками).

Соответствие красно-чёрному дереву. Если каждый 3-узел закодировать чёрным узлом и его красным левым ребёнком, получится лево-ориентированное красно-чёрное дерево (LLRB) — вариант красно-чёрного дерева с запретом красных правых рёбер. Обобщение узлов до трёх ключей/четырёх детей даёт 2-3-4 дерево и классическое соответствие КЧ-дереву.

50] кодируется чёрным узлом 50 и красным левым ребёнком 30 — так 2-3 дерево превращается в лево-ориентированное красно-чёрное дерево.

Сравнение с альтернативами

Структура	Хранит баланс	Высота	Поиск	Вставка/удаление	Особенность
2-3 дерево	нет (структурно)	[math]\displaystyle{ \le \log_2 n }[/math]	[math]\displaystyle{ O(\log n) }[/math]	[math]\displaystyle{ O(\log n) }[/math]	2–3 ребёнка на узел
2-3-4 дерево	нет	[math]\displaystyle{ \le \log_2 n }[/math]	[math]\displaystyle{ O(\log n) }[/math]	[math]\displaystyle{ O(\log n) }[/math]	2–4 ребёнка; изоморфно КЧ
АВЛ-дерево	BF/высота	[math]\displaystyle{ \le 1.44\log_2 n }[/math]	[math]\displaystyle{ O(\log n) }[/math]	[math]\displaystyle{ O(\log n) }[/math]	строгий баланс, много поворотов
Красно-чёрное	цвет	[math]\displaystyle{ \le 2\log_2 n }[/math]	[math]\displaystyle{ O(\log n) }[/math]	[math]\displaystyle{ O(\log n) }[/math]	двоичное, стандарт STL
B-дерево порядка [math]\displaystyle{ t }[/math]	нет	[math]\displaystyle{ \le \log_t n }[/math]	[math]\displaystyle{ O(\log n) }[/math]	[math]\displaystyle{ O(\log n) }[/math]	рассчитано на страницы диска

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

Где применяется

1. Учебная основа B-деревьев. 2-3 дерево вводит ключевые приёмы B-деревьев — расщепление, слияние, заимствование — в минимальном виде.
2. Символьные таблицы и словари в памяти. Там, где важны локальность и отсутствие полей баланса, многоключевые узлы дают хорошую кэш-эффективность.
3. Индексы СУБД и файловых систем (через обобщение). Реальные системы используют B-деревья и B⁺-деревья больших порядков, но их балансировка — прямое развитие идей 2-3 дерева.
4. Функциональные и неизменяемые структуры. 2-3 деревья и их аналоги (2-3 finger trees) применяются в чисто функциональных языках для неизменяемых упорядоченных множеств.
5. Соответствие красно-чёрным деревьям. Понимание 2-3 (и 2-3-4) деревьев объясняет, почему КЧ-дерево сбалансировано и как устроены операции LLRB.

Историческая справка

• 1970. Дж. Хопкрофт предложил 2-3 деревья — одну из первых сбалансированных структур с многоключевыми узлами [3].
• 1972. Р. Байер и Э. Маккрейт обобщили идею до B-деревьев, ориентированных на внешнюю память [4].
• 1978. Л. Гийба и Р. Седжвик показали соответствие между такими деревьями и красно-чёрными деревьями [5].
• 2008. Р. Седжвик предложил лево-ориентированные красно-чёрные деревья (LLRB) — прямую кодировку 2-3 деревьев.

Типичные ошибки и подводные камни

• Нарушение «одной глубины» листьев. Расщепление и слияние должны сохранять глубину; ошибка в наследовании детей ломает баланс.
• Неверный выбор «подъёмного» ключа при расщеплении. Поднимается средний ключ; крайние образуют два 2-узла.
• Спутанный порядок ключей в 3-узле. Между [math]\displaystyle{ k_1 }[/math] и [math]\displaystyle{ k_2 }[/math] идёт среднее поддерево; легко перепутать child[1] и child[2].
• Забыть случай переполнения внутреннего узла. Расщепление должно продолжаться вверх, а не только на уровне листа.
• Удаление: неправильное заимствование. Ключ идёт через родителя (перераспределение), а не напрямую; иначе нарушается порядок.
• Забыть про опустевший корень. При удалении корень может остаться без ключей — его нужно заменить единственным ребёнком (высота −1).
• Путаница 2-3 и 2-3-4. У 2-3 максимум 3 ребёнка, у 2-3-4 — 4; набор инвариантов и число случаев различаются.
• Дубликаты. Стандартное 2-3 дерево хранит уникальные ключи; для мультимножества нужен счётчик.
• Рекурсия. Вставка/удаление рекурсивны по высоте [math]\displaystyle{ O(\log n) }[/math] — безопасно; но удаление легко реализовать с ошибками в индексах детей.

Задачи для практики

1. Реализация вставки. Реализуйте рекурсивное расщепление; проверьте инварианты на [math]\displaystyle{ 10^5 }[/math] случайных вставках. Подсказка: validate с проверкой глубины листьев.
2. Поиск и диапазон. Реализуйте contains и вывод ключей в диапазоне [math]\displaystyle{ [a, b] }[/math] за [math]\displaystyle{ O(\log n + k) }[/math]. Подсказка: симметричный обход с отсечением.
3. Удаление. Реализуйте заимствование и слияние; проверьте уменьшение высоты при опустевшем корне. Подсказка: подъём «недостачи».
4. Высота. Докажите [math]\displaystyle{ \log_3 n \le h \le \log_2 n }[/math] и постройте деревья, дающие обе крайности. Подсказка: все узлы 2-узлы против всех 3-узлов.
5. Соответствие LLRB. Закодируйте 3-узлы красными рёбрами и проверьте свойства КЧ-дерева. Подсказка: красное ребро наклонено влево.
6. Амортизированные расщепления. Докажите, что [math]\displaystyle{ n }[/math] вставок дают [math]\displaystyle{ O(n) }[/math] расщеплений. Подсказка: аналогия с двоичным счётчиком.
7. Обобщение до 2-3-4. Измените код на 2-3-4 дерево и сравните число операций. Подсказка: 4-узел расщепляется на два 2-узла с подъёмом среднего ключа.
8. Много дубликатов. Добавьте счётчик повторов в узел. Подсказка: ключ хранится один раз, счётчик растёт/убывает.

Связанные темы

• 2-3-4 дерево — обобщение до четырёх детей, изоморфное красно-чёрному дереву.
• Красно-чёрное дерево — двоичная кодировка 3-узлов (LLRB).
• АВЛ-дерево — строгий баланс в двоичном дереве.
• Двоичное дерево поиска — базовая структура.
• Асимптотическая сложность — нотация [math]\displaystyle{ O }[/math], [math]\displaystyle{ \Omega }[/math], [math]\displaystyle{ \Theta }[/math].

Источники

1. Cormen T. H., Leiserson C. E., Rivest R. L., Stein C. Introduction to Algorithms (CLRS). 3rd ed. — MIT Press, 2009. — Гл. 18 «B-Trees» (многоключевые узлы, расщепление и слияние).
2. Sedgewick R., Wayne K. Algorithms. 4th ed. — Addison-Wesley, 2011. — Гл. 3 (сбалансированные деревья поиска).
3. Knuth D. E. The Art of Computer Programming. Vol. 3: Sorting and Searching. — Addison-Wesley, 2nd ed., 1998. — §6.2.4 (многопутевые деревья; 2-3 деревья приписываются Хопкрофту).
4. Bayer R., McCreight E. Organization and Maintenance of Large Ordered Indexes // Acta Informatica. — 1972. — Vol. 1, No. 3. — P. 173–189.
5. Guibas L. J., Sedgewick R. A Dichromatic Framework for Balanced Trees // FOCS. — 1978.
6. Wikipedia: 2–3 tree. URL: https://en.wikipedia.org/wiki/2%E2%80%933_tree.