144
правки
Изменения
Нет описания правки
Чтобы поместить новый ключ в узел, в котором содержится ровно один ключ, необходимо просто добавить его как второй ключ к узлу.
[[Файл:23treeadd3.png|220px|border]] [[Файл:23treeadd4.png|200px|border]]
Если же в узле уже содержатся два ключа, делим его на два "одноключевых" узла и вставляем средний ключ в родительский узел.Это может привести к тому, что придется делить родительский узел. Тогда таким же образом проходим до корня дерева.
[[Файл:23treeadd1.png|245px|border]] [[Файл:23treeadd2.png|200px|border]]
* ''' Удаление элемента '''
При удалении ключа из узла возникают три варианта.
Если до удаления ключа в узле содержалось три два ключа, то после удаления ничего не меняется. Если же у ключа после удаления остался один элемент, то проверяем количество потомков второго ребенка того узла, ребенком которого является узел с удаляемым ключом. Если у него два ребенка, то присваиваем ему оставшийся один элемент. [[Файл:23treedel1.png|220px|border]] [[Файл:23treedel2.png|200px|border]] Иначе у него три ребенка. Тогда присваиваем узлу с одним ключом один из этих ключей, таким образом получая два узла с двумя ключами. [[Файл:23treedel3.png|200px|border]] [[Файл:23treedel4.png|215px|border]]
* ''' Слияние двух деревьев (merge()) '''
