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