Изменения

Если у <tex>t</tex> существует родитель, и у него строго больше <tex>2</tex> сыновей, то просто удалим <tex>t</tex>, а у <tex>\mathtt{t.parent}p</tex> уменьшим количество детей.

Если у родителя <tex>\mathtt{t}</tex> <tex>2</tex> два сына, то найдем у любого соседнего листа его родителя, обозначим его за <tex>p</tex>. Обозначим отца соседнего листа за <tex>pnp</tex>.Рассмотрим возможные случаи:*<tex>pnp</tex> не существует, тогда мы удаляем одного из сыновей корня, тогда другой сын становится новым корнем,*у <tex>\mathtt{t.parent}p</tex> оказалось <tex>2</tex> сына, у <tex>pnp</tex> оказалось <tex>2 </tex> сына. Подвесим <tex>b</tex> к <tex>pnp</tex> и удалим <tex>t</tex>, но у отца <tex>\mathtt{t.parent}p</tex> не изменим количество детей. Так у отца <tex>\mathtt{t.parent}p</tex> оказалось тоже два сына,повторяем для него такие же рассуждения.*у <tex>\mathtt{t.parent}p</tex> оказалось <tex>2</tex> сына, у <tex>pnp</tex> оказалось 2 <tex>3</tex> сына. Подвесим <tex>b</tex> к <tex>pnp</tex> и удалим <tex>t</tex>, а у отца уменьшим количество детей. Так как у <tex>pnp</tex> оказалось четыре сына, то необходимо его расщепить. Теперь у отца <tex>\mathtt{t.parent}p</tex> оказалось два сына и все узлы 2-3 дерева корректны.*у <tex>\mathtt{t.parent}p</tex> оказалось <tex>3</tex> сына, у <tex>pnp</tex> оказалось <tex>2 </tex> сына. Подвесим <tex>b</tex> к <tex>pnp</tex> и удалим <tex>t</tex>, а у отца уменьшим количество детей. Так как у <tex>pnp</tex> оказалось три сына, а у отца <tex>\mathtt{t.parent}p</tex> все ещё больше одного сына, то все узлы 2-3 дерева корректны.*у <tex>\mathtt{t.parent}p</tex> оказалось <tex>3</tex> сына, у <tex>pnp</tex> оказалось <tex>3 </tex> сына. Подвесим <tex>b</tex> к <tex>pnp</tex> и удалим <tex>t</tex>, а у отца уменьшим количество детей. Так как у <tex>pnp</tex> оказалось четыре сына, то расщепим его, теперь у отца <tex>\mathtt{t.parent}p</tex> вновь три сына и все узлы 2-3 дерева корректны.

Обобщим алгоритм при удалении когда у родителя <tex>\mathtt{t}</tex> два сына(ниже мы никогда не уменьшаем количество детей у <tex>\mathtt{t.parent}p</tex>):*Если p <tex>np</tex> не существует, то оказывается, что мы сейчас удаляем какого-то из сыновей корня (для определенности далее левого, с правым аналогично). Тогда теперь правый сын становится корнем. На этом удаление заканчивается.

*Если p <tex>np</tex> существует, то удалим <tex>t</tex>, а его брата (<tex>b</tex>) перецепим к <tex>pnp</tex>. Теперь у <tex>pnp</tex> могло оказаться <tex>4</tex> сына, поэтому повторим аналогичные действия из <tex>\mathtt{insert}</tex>: вызовем <tex>\mathtt{updateKeys}(b)</tex> и <tex>\mathtt{splitParent}(pnp)</tex>. Теперь рекурсивно удалим <tex>\mathtt{t.parent}p</tex>.