143
правки
Изменения
→Вставка элемента
'''function''' splitParent('''Node''' t):
'''if''' (t.length > 3)
Node a; a.= Node(sons[0] = {t.sons[2] a, t.sons[13] }, keys = {t.sonskeys[32]}, parent = t.parent, a.length = 2)
t.sons[2].parent = a
t.sons[3].parent = a
t.length = 2
t.sons[2] = '''null'''
сортируем сыновей у t.parent
splitParent(t.parent)
'''else''' <font color=green>//мы расщепили корень, надо подвесить его к общему родителю, который будет новым корнем</font>
Node t = root
root.sons[0] = t
'''while''' (a != '''null''')
'''for''' i = 0 .. a.length - 1
a.keys[i] = max(a.sons[i]) <font color=green>//max {{---}} возвращает максимальное значение в поддереве.</font> a = a.parent <font color=green>//Примечание: max легко находить, если хранить максимум </font> <font color=green>//правого поддерева в каждом узле {{---}} это значение и будет max(a.sons[i])</font>
<tex>\mathtt{updateKeys}</tex> необходимо запускать от нового узла.
