143
правки
Изменения
→Удаление элемента
*<tex>np</tex> {{---}} соседний брат <tex>p</tex>,
*<tex>gp</tex> {{---}} отец <tex>p</tex>.
Пусть изначально <tex>t = \mathtt{searchsearchNode(x)}</tex> {{---}} узел, где находится <tex>x</tex>.
Если у <tex>t</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 дерева корректны.
*у <tex>gp</tex> оказалось <tex>3</tex> сына, у <tex>np</tex> оказалось <tex>2</tex> сына. Подвесим <tex>b</tex> к <tex>np</tex> и удалим <tex>p</tex>, а у <tex>gp</tex> уменьшим количество детей. Так как у <tex>np</tex> оказалось три сына, а у <tex>gp</tex> все ещё больше одного сына, то все узлы 2-3 дерева корректны.
