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 дерево — дерево поиска, в котором:
- каждый внутренний узел имеет либо двух, либо трёх детей;
- узел с двумя детьми (2-узел) хранит один ключ, узел с тремя детьми (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];
- все листья находятся на одной глубине (дерево идеально сбалансировано).
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] — двоичный, если не оговорено.
Мотивация и интуиция
Двоичное дерево поиска простое, но легко вырождается в список. Сбалансированные 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].
Листья (внешние узлы) не хранят ключей и все находятся на одном уровне. Поиск спускается от корня, сравнивая ключ с одним или двумя ключами узла и выбирая ребёнка; при совпадении — успех.
Инварианты (поддерживаются всеми операциями):
- Порядок: ключи вдоль обхода слева направо возрастают.
- Степень: у внутреннего узла 2 или 3 ребёнка; у листа — 0.
- Совершенная балансировка: все листья на одной глубине.
Именно третий инвариант и даёт [math]\displaystyle{ O(\log n) }[/math]: он сохраняется при вставках и удалениях автоматически.
Операции и алгоритмы
Операция: поиск (Search)
Идея. Спуск от корня: сравнить ключ с ключом (или двумя ключами) узла, выбрать нужного ребёнка.
Пошаговое описание.
- В текущем узле найти позицию ключа среди
keys[0..n-1]. - Если ключ совпал — найдено.
- Иначе при листе — не найдено; при внутреннем узле — спуститься в соответствующего ребёнка.
Инвариант. Искомый ключ, если есть, лежит в поддереве текущего узла.
Псевдокод.
Алгоритм 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)
Идея. Спуститься до последнего внутреннего узла и вставить ключ; при переполнении узла — расщепить его, подняв средний ключ в родителя (рекурсивно вверх).
Пошаговое описание.
- Спуск до последнего внутреннего узла по ключу.
- Вставка ключа в последний внутренний узел (он временно может стать 4-узлом с тремя ключами).
- Если ключей стало три — расщепление: крайние остаются в двух 2-узлах, средний поднимается.
- Если переполнился родитель — повторить расщепление выше.
- Если расщепился корень — создать новый корень; высота растёт на 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).
Крайние случаи. Вставка в пустое дерево — единственный внутренний узел с двумя внешними листьями. Вставка дубликата — либо игнорируется, либо хранится счётчик повторов.
Операция: удаление (Delete)
Идея. Удалить ключ; если узел «опустел» (стал недопустимым), восстановить инвариант заимствованием у соседа-3-узла или слиянием с соседом через ключ родителя.
Пошаговое описание.
- Найти ключ; если он во внутреннем узле, заменить его ключом-предшественником из последнего внутреннего узла (как в BST).
- Удалить ключ из последнего внутреннего узла.
- Если последний внутренний узел опустел: - у соседа справа/слева есть 3-узел — заимствовать: перебросить ключ через родителя; - у соседей только 2-узлы — слить узел с соседом, опустив ключ родителя.
- Если родитель потерял ребёнка и опустел — повторить пункт 3 выше.
- Если корень опустел — сделать его единственного ребёнка новым корнем (высота −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.
Операции: минимум, максимум и обход
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проверяет все три инварианта, включая одну глубину листьев.- Удаление реализуется тем же рекурсивным приёмом с «подъёмом недостачи», но содержит больше случаев (заимствование/слияние).
Сводная таблица сложности
| Операция | Худший | Амортизированная | Замечание |
|---|---|---|---|
| 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]: каждое расщепление одного узла оплачивается предшествующими вставками — тот же аргумент, что и у двоичного счётчика (сравните с двоичной кучей и биномиальной кучей).
Трассировка примера
Вставим ключи [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 дерево и классическое соответствие КЧ-дереву.
Сравнение с альтернативами
| Структура | Хранит баланс | Высота | Поиск | Вставка/удаление | Особенность |
|---|---|---|---|---|---|
| 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-деревья, и красно-чёрные деревья.
Где применяется
- Учебная основа B-деревьев. 2-3 дерево вводит ключевые приёмы B-деревьев — расщепление, слияние, заимствование — в минимальном виде.
- Символьные таблицы и словари в памяти. Там, где важны локальность и отсутствие полей баланса, многоключевые узлы дают хорошую кэш-эффективность.
- Индексы СУБД и файловых систем (через обобщение). Реальные системы используют B-деревья и B⁺-деревья больших порядков, но их балансировка — прямое развитие идей 2-3 дерева.
- Функциональные и неизменяемые структуры. 2-3 деревья и их аналоги (2-3 finger trees) применяются в чисто функциональных языках для неизменяемых упорядоченных множеств.
- Соответствие красно-чёрным деревьям. Понимание 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] — безопасно; но удаление легко реализовать с ошибками в индексах детей.
Задачи для практики
- Реализация вставки. Реализуйте рекурсивное расщепление; проверьте инварианты на [math]\displaystyle{ 10^5 }[/math] случайных вставках. Подсказка:
validateс проверкой глубины листьев. - Поиск и диапазон. Реализуйте
containsи вывод ключей в диапазоне [math]\displaystyle{ [a, b] }[/math] за [math]\displaystyle{ O(\log n + k) }[/math]. Подсказка: симметричный обход с отсечением. - Удаление. Реализуйте заимствование и слияние; проверьте уменьшение высоты при опустевшем корне. Подсказка: подъём «недостачи».
- Высота. Докажите [math]\displaystyle{ \log_3 n \le h \le \log_2 n }[/math] и постройте деревья, дающие обе крайности. Подсказка: все узлы 2-узлы против всех 3-узлов.
- Соответствие LLRB. Закодируйте 3-узлы красными рёбрами и проверьте свойства КЧ-дерева. Подсказка: красное ребро наклонено влево.
- Амортизированные расщепления. Докажите, что [math]\displaystyle{ n }[/math] вставок дают [math]\displaystyle{ O(n) }[/math] расщеплений. Подсказка: аналогия с двоичным счётчиком.
- Обобщение до 2-3-4. Измените код на 2-3-4 дерево и сравните число операций. Подсказка: 4-узел расщепляется на два 2-узла с подъёмом среднего ключа.
- Много дубликатов. Добавьте счётчик повторов в узел. Подсказка: ключ хранится один раз, счётчик растёт/убывает.
Связанные темы
- 2-3-4 дерево — обобщение до четырёх детей, изоморфное красно-чёрному дереву.
- Красно-чёрное дерево — двоичная кодировка 3-узлов (LLRB).
- АВЛ-дерево — строгий баланс в двоичном дереве.
- Двоичное дерево поиска — базовая структура.
- Асимптотическая сложность — нотация [math]\displaystyle{ O }[/math], [math]\displaystyle{ \Omega }[/math], [math]\displaystyle{ \Theta }[/math].
Источники
- Cormen T. H., Leiserson C. E., Rivest R. L., Stein C. Introduction to Algorithms (CLRS). 3rd ed. — MIT Press, 2009. — Гл. 18 «B-Trees» (многоключевые узлы, расщепление и слияние).
- Sedgewick R., Wayne K. Algorithms. 4th ed. — Addison-Wesley, 2011. — Гл. 3 (сбалансированные деревья поиска).
- Knuth D. E. The Art of Computer Programming. Vol. 3: Sorting and Searching. — Addison-Wesley, 2nd ed., 1998. — §6.2.4 (многопутевые деревья; 2-3 деревья приписываются Хопкрофту).
- Bayer R., McCreight E. Organization and Maintenance of Large Ordered Indexes // Acta Informatica. — 1972. — Vol. 1, No. 3. — P. 173–189.
- Guibas L. J., Sedgewick R. A Dichromatic Framework for Balanced Trees // FOCS. — 1978.
- Wikipedia: 2–3 tree. URL: https://en.wikipedia.org/wiki/2%E2%80%933_tree.