2-3 дерево

Материал из Википедии — свободной энциклопедии

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

Содержание 1 Свойства 2 Нелистовые вершины 3 См. также 4 Ссылки

[править] Свойства

• Все нелистовые вершины содержат одно поле и 2 поддерева или 2 поля и 3 поддерева.
• Все листовые вершины находятся на одном уровне (на нижнем уровне) и содержат 1 или 2 поля.
• Все данные отсортированы.

[править] Нелистовые вершины

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

[править] См. также

• B-дерево

[править] Ссылки

• Визуализатор 2-3 дерева
• 2-3 Trees Complete Description
• B-Tree animation (Java Applet)

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