2-3-дерево | это... Что такое 2-3-дерево? (original) (raw)
2-3 дерево — структура данных являющаяся B-деревом Степени 1, страницы которого могут содержать только 2-вершины (вершины с одним полем и 2-мя детьми) и 3-вершины (вершины с 2-мя полями и 3-мя детьми). Листовые вершины являются исключением — у них нет детей (но может быть одно или два поля). 2-3 деревья сбалансированы, то есть каждое левое, правое, и центральное поддерево одинаковой высоты, и таким образом содержат равное (или почти равное) число данных.
2-Вершина
3-Вершина
Свойства
- Все нелистовые вершины содержат одно поле и 2 поддерева или 2 поля и 3 поддерева.
- Все листовые вершины находятся на одном уровне (на нижнем уровне) и содержат 1 или 2 поля.
- Все данные отсортированы (по принципу двоичного дерева поиска).
Нелистовые вершины
Нелистовые вершины содержат одно или два поля, указывающие на диапазон значений в их поддеревьях. Значение первого поля строго больше наибольшего значения в левом поддереве и меньше или равно наименьшему значению в правом поддереве (или в центральном поддереве, если это 3-вершина); аналогично, значение второго поля (если оно есть) строго больше наибольшего значения в центральном поддереве и меньше или равно чем наименьшее значение в правом поддереве. Эти нелистовые вершины используются для направления функции поиска к нужному поддереву и, в конечном итоге, к нужному листу.
См. также
Ссылки
- Визуализатор 2-3 дерева
- 2-3 Trees Complete Description
- B-Tree animation (Java Applet)
- 2-3 Tree in Python
 Дерево (структура данных) |
|
|---|---|
| Двоичное дерево поиска · Дерево (теория графов) · Древовидная структура | |
| Двоичные деревья | Двоичное дерево · T-дерево |
| Самобалансирующиеся двоичные деревья | АА-дерево · АВЛ-дерево · Красно-чёрное дерево · Расширяющееся дерево · Дерево со штрафами · Декартово дерево · Дерево Фибоначчи |
| B-деревья | B-дерево · 2-3-дерево · B+ дерево · B*-дерево · UB-дерево · 2-3-4 дерево · (a,b)-дерево · Танцующее дерево |
| Префиксные деревья | Суффиксное дерево · Radix tree · Ternary search tree |
| Двоичное разбиение пространства | k-мерное дерево · VP-дерево |
| Недвоичные деревья | Дерево квадрантов · Октодерево · Sparse Voxel Octree · Экспоненциальное дерево · PQ-дерево |
| Разбиение пространства | R-дерево · R+-дерево · R*-дерево · X-дерево · M-дерево · Дерево Фенвика · Дерево отрезков |
| Другие деревья | Куча · TTH · Finger tree · Metric tree · Cover tree · BK-tree · Doubly-chained tree · iDistance · Link-cut tree |
| Алгоритмы | Поиск в ширину · Поиск в глубину · DSW-алгоритм · Алгоритм связующего дерева |