WikiSort.ru - Программирование

2-3 дерево — структура данных, являющаяся B-деревом степени 1^{[уточнить]}, каждый узел (страница) которого имеет либо два потомка и одно поле, либо три потомка и два поля. Листовые вершины являются исключением — у них нет детей (но может быть одно или два поля). 2-3 деревья сбалансированы, то есть каждое левое, правое и центральное поддерево имеет одну и ту же высоту, и, таким образом, содержат равные (или почти равные) объемы данных.

• 
  2-вершина
• 
  3-вершина

Свойства

• Все нелистовые вершины содержат одно поле и 2 поддерева или 2 поля и 3 поддерева.
• Все листовые вершины находятся на одном уровне (на нижнем уровне) и содержат 1 или 2 поля.
• Все данные отсортированы (по принципу двоичного дерева поиска).
• Поле в 2-вершине, как и в двоичном дереве поиска, делит пространство возможных значений на два диапазона: ${\displaystyle (-\infty ,a)}$ и ${\displaystyle [a,+\infty )}$
• Поля в 3-вершине делят пространство возможных значений на три диапазона: ${\displaystyle (-\infty ,a)}$ , ${\displaystyle [a,b)}$ и ${\displaystyle [b,+\infty )}$

Нелистовые вершины

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

Например, для иллюстрации выше справедливы следующие неравенства:

• для 2-вершины: ${\displaystyle p<a\leq q}$
• для 3-вершины: ${\displaystyle p<a\leq q<b\leq r}$

См. также

• B-дерево
• Список структур данных (деревья)

Ссылки

• B-Tree animation (Java Applet)
• B-Tree Visualization

Это заготовка статьи о программировании. Вы можете помочь проекту, дополнив её.