Изменения
Нет описания правки
Если у <tex>t</tex> не существует родителя, то это корень (одновременно и единственный элемент в дереве). Удалим его.
Если у <tex>p</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>3</tex> сына, у <tex>np</tex> оказалось <tex>3</tex> сына. Подвесим <tex>b</tex> Просто заберем ближайшего к нам сына у <tex>np</tex> и удалим прицепим его к <tex>p</tex>, а у <tex>gp</tex> уменьшим количество детей. Так как у Восстановим порядок в сыновьях <tex>npp</tex> оказалось четыре сына, то необходимо его расщепить. Теперь у<tex>gpp</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 дерева корректны.
*<tex>x</tex> {{---}} поисковый параметр,
*<tex>t</tex> {{---}} текущий узел.
В силу того, что наши узлы отсортированы по максимуму в поддереве, то следующий объект {{---}} это соседний лист справа. Попасть туда можно следующим образом:
будем подниматься вверх, пока у нас не появится первой возможности свернуть направо вниз. Как только мы свернули направо вниз, будем идти всегда влево. Таким образом, мы окажемся в соседнем листе. Если мы не смогли ни разу свернуть направо вниз, и пришли в корень, то следующего объекта не существует. Случай с предыдущим симметричен.
'''T''' next('''T''' x): Node t = searchsearchNode(x)
'''if''' (t.keys[0] > x) <font color=green> //x не было в дереве, и мы нашли следующий сразу</font>
'''return''' t.keys[0]
'''while''' (t != ''null'')
t = t.parent
t = t.sons[0]
'''return''' t
'''return''' t.keys[0];
* [http://rain.ifmo.ru/cat/view.php/vis/trees/2-3-2002 rain.ifmo.ru {{---}} Визуализатор 2-3 дерева]
* [http://ru.wikipedia.org/wiki/2-3-дерево Википедия {{---}} 2-3 дерево]
* Д. Кнут «Искусство программирования. Сортировка и поиск» {{---}} стр. 508 - 509
