Interested Article - 2-3-дерево

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


Свойства

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

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

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

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

  • для 2-вершины:
  • для 3-вершины:

См. также

Ссылки

Источник —

Same as 2-3-дерево