2-3-дерево

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

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


Свойства[править | править исходный текст]

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

Нелистовые вершины[править | править исходный текст]

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

См. также[править | править исходный текст]

Ссылки[править | править исходный текст]