Изменения
→Удаление элемента
*<tex>x</tex> {{---}} значение удаляемого узла,
*<tex>t</tex> {{---}} текущий узел.
*<tex>b</tex> {{---}} любой брат <tex>t</tex>.
Пусть изначально <tex>t = \mathtt{search(x)}</tex> {{---}} узел, где находится <tex>x</tex>.
Если у <tex>t</tex> не существует родителя, то это корень. Удалим его.
Если у <tex>t</tex> существует родитель, и у него <tex>3</tex> сына, то просто удалим <tex>t</tex>. Обновим ключи, запустив <tex>\mathtt{updateKeys}</tex> от любого брата <tex>tb</tex>.
Если у родителя <tex>\mathtt{t.parent}</tex> <tex>2</tex> сына, то найдем у любого соседнего листа его родителя, обозначим его за <tex>p</tex>.
*Если p не существует, то оказывается, что мы сейчас удаляем какого-то из сыновей корня (для определенности далее левого, с правым аналогично). Тогда теперь правый сын становится корнем. На этом удаление заканчивается.
*Если p существует, то удалим <tex>t</tex>, а его брата(<tex>b</tex> ) перецепим к <tex>p</tex>). Теперь у <tex>p</tex> могло оказаться <tex>4</tex> сына, поэтому повторим аналогичные действия из <tex>\mathtt{insert}</tex>: вызовем <tex>\mathtt{updateKeys}(b)</tex> и <tex>\mathtt{splitParent}(p)</tex>. Теперь рекурсивно удалим <tex>\mathtt{t.parent}</tex>.
[[Файл:23treedelete.png|thumb|center|Удаление элемента с ключом 2|1150px]]
