144
правки
Изменения
→Операции
второе поддерево) и если наш ключ не превосходит второй ключ, то осуществляется переход
в среднее поддерево, а если превосходит, то идем в правое поддерево.
* ''' Вставка элемента '''
Чтобы поместить новый ключ в узел, в котором содержится ровно один ключ, необходимо просто добавить его как второй ключ к узлу.
Если же в узле уже содержатся два ключа, делим его на два "одноключевых" узла и вставляем средний ключ в родительский узел.Это может привести к тому, что придется делить родительский узел. Если Тогда таким же родительский узел - корень образом проходим до корня дерева - разбиваем на два поддерева и добавляем вершину.
* ''' Удаление элемента '''
Если до удаления ключа в узле содержалось три ключа, то после удаления ничего не меняется.
Если же у ключа после удаления остался один элемент, то проверяем количество потомков второго ребенка того узла, ребенком которого является узел с удаляемым ключом. Если у него два ребенка, то присваиваем ему оставшийся один элемент. Иначе у него три ребенка. Тогда присваиваем узлу с одним ключом один из этих ключей, таким образом получая два узла с двумя ключами.
* ''' Слияние двух деревьев (merge()) '''
Возможно два варианта слияния двух деревьев.
Если два дерева одной высоты, то слияние представляет собой добавление общей вершины.
Если два дерева разной высоты, то при слиянии меньшее добавляем как поддерево к одной из вершин большего.Если возникает ситуация,когда у необходимого узла уже есть три ребенка, то делим его на два узла с двумя поддеревьями и проверяем родителя.Таким образом проходим по дереву вверх до полной сбалансировки.
