Изменения
Нет описания правки
''' 2-3 дерево ''' — структура данных, предложенная в 1970 году Джоном Хопкрофтом,и представляющая собой [[B-дерево|B-дерево]] cтепени 1, такое что из каждого узла может выходить две или три ветви; при этом требуется, чтобы все внешние узлы находились на одном уровне. Каждый внутренний узел содержит либо один, либо два ключа.
==Значения ==
Все данные хранятся в листьях, в вершинах хранится вспомогательная информация,необходимая для организации поиска по поддеревьям.Нелистовые вершины содержат 1 или 2 ключа, указывающие на диапазон значений в их поддеревьях.
== Структура ==
Информация в таких деревьях хранится в листьях, а остальные вершины содержат вспомогательную информацию для организации поиска.2-3 деревья сбалансированы, то есть каждое левое, правое, и центральное поддерево одинаковой высоты, и таким образом содержат равное (или почти равное) число данных.
== Свойства ==
* Все нелистовые вершины содержат одно поле один ключ и 2 поддерева или 2 поля ключа и 3 поддерева.* Все листовые вершины находятся на одном уровне (на нижнем уровне) и содержат 1 или 2 поляключа.
* Все данные отсортированы
* 2-3 дерево - сливаемое дерево
== Операции ==
* Слияние двух деревьев (merge())Т.к. вся информация в 2-3 деревьях хранится в листьях, а в вершинах хранится вспомогательная информация, то слияние двух деревьев представляет собой добавление общей вершины. * Вставка элемента:
Есть два варианта вставки в 2-3 дерево.
