144
правки
Изменения
Нет описания правки
[[Файл:2_3tree23дерево_new.jpgjpg |right|300px|thumb|Пример 2-3 дерева]]
''' 2-3 дерево ''' — структура данных, предложенная в 1970 году Джоном Хопкрофтом,и представляющая собой [[B-дерево|B-дерево]] cтепени 1, такое что из каждого узла может выходить две или три ветви; при этом требуется, чтобы все внешние узлы находились на одном уровне. Каждый внутренний узел содержит либо один, либо два ключа.
Если до удаления ключа в узле содержалось два ключа, то после удаления ничего не меняется.
Если же у ключа после удаления остался один элемент, то проверяем количество потомков второго ребенка того узла, ребенком которого является узел с удаляемым ключом. Если у него два ребенка, то присваиваем ему оставшийся один элемент. Вершину, оставшуюся без детей, удаляем рекурсивно.
[[Файл:23treedel1.png|220px|border]] [[Файл:23treedel2.png|200px|border]]
