286
правок
Изменения
Нет описания правки
++pos
'''for''' i = leaf.key_num '''downto''' pos + 1
leaf.key[i] = leaf.key[i-1] '''for''' i = leaf.key_num + 1 '''downto''' pos + 2 leaf.pointers[i] = leaf.pointer[i-1]
leaf.key[pos] = key
leaf.pointers[pos + 1] = value
++leaf.key_num
'''if''' leaf.key_num == 2*t <span style="color:#008000"> // t {{---}} степень дерева</span> split(T, leaf) <span style="color:#008000"> // Разбиваем узел</span>
'''return true'''
new_node.pointers[i] = node.pointers[i + t - 1]
new_node.child[i] = node.child[i + t - 1]
node.key_num = t - 1
++pos
'''for''' i = parent.key_num '''downto''' pos + 1
parent.key[i] = parent.key[i-1]
'''for''' i = parent.key_num + 1 '''downto''' pos + 2
parent.child[i] = parent.child[i-1]
parent.key[pos] = mid_key
parent.child[pos + 1] = new_node
++parent.key_num
'''if''' parent.key_num == 2*t
split(T, parent)
'''return'''
'''for''' i = pos '''to''' tec.key_num - 1
tec.key[i] = tec.key[i + 1] tec.pointers[i] = tec.pointer[i+1]
'''for''' i = pos + 1 '''to''' tec.key_num
tec.pointerschild[i] = tec.pointerchild[i+1]
--tec.key_num
left_sibling = tec.left
'''if''' left_sibling <tex>\neq</tex> null '''and''' left_sibling.key_num <tex>\small{\geqslant}</tex> t - 1
--left_sibling.key_num
++tec.key_num
'''for''' i = 1 '''to''' tec.key_num - 1
tec.key[i] = tec.key[i - 1]
tec.pointers[i] = tec.pointer[i - 1]
tec.child[i] = tec.child[i - 1]
tec.child[tec.key_num] = tec.child[tec.key_num - 1]
tec.key[0] = left_sibling.key[left_sibling.key_num]
tec.pointers[0] = left_sibling.pointers[left_sibling.key_num]
tec.child[0] = left_sibling.child [left_sibling.key_num + 1]
update(tec) <span style="color:#008000"> // Обновить ключи в родителях</span>
'''else if''' right_sibling <tex>\neq</tex> null '''and''' right_sibling.key_num <tex>\small{\geqslant}</tex> t - 1
--right_sibling.key_num
++tec.key_num
tec.key[tec.key_num - 1] = right_sibling.key[0]
tec.pointers[tec.key_num - 1] = right_sibling.child[0]
tec.child[tec.key_num - 1] = right_sibling.pointers[0]
'''return true'''
