143
правки
Изменения
→Удаление элемента
Если у <tex>t</tex> не существует родителя, то это корень (одновременно и единственный элемент в дереве). Удалим его.
Если у <tex>tp</tex> существует родитель, и у него строго больше <tex>2</tex> сыновей, то просто удалим <tex>t</tex>, а у <tex>p</tex> уменьшим количество детей.
Если у родителя <tex>t</tex> два сына, рассмотрим возможные случаи (сперва везде удаляем <tex>t</tex>):
*<tex>np</tex> не существует, тогда мы удаляем одного из сыновей корня, тогда следовательно, другой сын становится новым корнем,
*у <tex>gp</tex> оказалось <tex>2</tex> сына, у <tex>np</tex> оказалось <tex>2</tex> сына. Подвесим <tex>b</tex> к <tex>np</tex> и удалим <tex>p</tex>. Так как у <tex>gp</tex> {{---}} родителя <tex>p</tex>, оказалось тоже два сына,повторяем для <tex>p</tex> такие же рассуждения.
*у <tex>gp</tex> оказалось <tex>2</tex> сына, у <tex>np</tex> оказалось <tex>3</tex> сына. Подвесим <tex>b</tex> к <tex>np</tex> и удалим <tex>p</tex>, а у <tex>gp</tex> уменьшим количество детей. Так как у <tex>np</tex> оказалось четыре сына, то необходимо его расщепить. Теперь у<tex>gp</tex> оказалось снова два сына и все узлы 2-3 дерева корректны.
