48
правок
Изменения
Нет описания правки
Есть два варианта вставки в 2-3 дерево.
1)Чтобы поместить новый ключ в узел, в котором содержится ровно один ключ, необходимо просто добавить его как второй ключ к узлу.
[[Файл:23treeadd3.png|440px|border]] [[Файл:23treeadd4.png|400px|border]]
2)Если же в узле уже содержатся два ключа, делим его на два "одноключевых" узла и вставляем средний ключ в родительский узел.Это может привести к тому, что придется делить родительский узел. Тогда таким же образом проходим до корня дерева.
[[Файл:23treeadd1.png|490px|border]] [[Файл:23treeadd2.png|400px|border]]
При удалении ключа из узла возникают три варианта.
1)Если после удаления ключа в узле содержится два ключа, то после удаления ничего не меняется.
2)Если же у ключа после удаления остался один элемент, то проверяем количество потомков второго ребенка того узла, ребенком которого является узел с удаляемым ключом. Если у него два ребенка, то присваиваем ему оставшийся один элемент. Вершину, оставшуюся без детей, удаляем рекурсивно.
[[Файл:23treedel1.png|440px330px|border]] [[Файл:23treedel2.png|400px300px|border]] [[Файл:23treedel5.png|300px|border]]
3)Иначе у него три ребенка. Тогда присваиваем узлу с одним ключом один из этих ключей, таким образом получая два узла с двумя ключами.
[[Файл:23treedel3.png|400px300px|border]] [[Файл:23treedel4.png|430px320px|border]] [[Файл:23treedel6.png|300px|border]]
=== Слияние двух деревьев ===
