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