143
правки
Изменения
→Вставка элемента
Найдем сперва, где бы находился элемент, применив search(x). Далее проверим есть ли у этого узла родитель, если его нет, то в дереве всего один элемент - лист. Возьмем этот лист и новый узел, и создадим для них родителя, лист и новый узел расположим в порядке возрастания.
Если родитель существует, то подвесим к нему ещё одного сына. Если сыновей стало 4, то разделим родителя на два узла, и повторим разделение теперь для его родителя(перед разделением обновим ключи).
splitParent('''Node''' t):
<tex>\mathtt{updateKeys}</tex> необходимо запускать от нового узла.
insert('''int''' x):
Node n = Node(x)
split(n)
updateKeys(n)
Так как мы спускаемся один раз, и поднимаемся вверх при расщеплении родителей не более одного раза, то <tex>\mathtt{insert}</tex> работает за <tex>O(\log{n})</tex>Примеры добавления:
[[Файл:23treeinsert.png|border]]
[[Файл:23treeinsert2.png|1150px|border]]
=== Удаление элемента ===
