Изменения
→Свойства
=== Удаление элемента ===
*<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{searchsearchNode(x)}</tex> {{---}} узел, где находится <tex>x</tex>.
Если у <tex>t</tex> не существует родителя, то это корень (одновременно и единственный элемент в дереве). Удалим его.
Если у <tex>tp</tex> существует родитель, и у него строго больше <tex>2</tex> сыновей, то просто удалим <tex>t</tex>, а у <tex>p</tex> уменьшим количество детей.
Если у родителя <tex>t</tex> два сына, то найдем у любого соседнего листа его родителя, обозначим его за рассмотрим возможные случаи (сперва везде удаляем <tex>npt</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>p</tex> такие же рассуждения.,*у <tex>pgp</tex> оказалось <tex>2</tex> или <tex>3</tex> сына, у <tex>np</tex> оказалось <tex>3</tex> сына. Подвесим <tex>b</tex> Просто заберем ближайшего к нам сына у <tex>np</tex> и удалим прицепим его к <tex>tp</tex>, а у отца уменьшим количество детей. Так как у Восстановим порядок в сыновьях <tex>npp</tex> оказалось четыре сына, то необходимо его расщепить. Теперь у отца <tex>p</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>p</tex> оказалось <tex>3</tex> сына, у <tex>np</tex> оказалось <tex>3</tex> сына. Подвесим <tex>b</tex> к <tex>np</tex> и удалим <tex>t</tex>, а у отца уменьшим количество детей. Так как у <tex>np</tex> оказалось четыре сына, то расщепим его, теперь у отца <tex>p</tex> вновь три сына и все узлы 2-3 дерева корректны.
Обобщим алгоритм при удалении когда у родителя <tex>\mathtt{t}</tex> два сына(ниже мы никогда не уменьшаем количество детей у <tex>p</tex>):
*Если <tex>np</tex> не существует, то оказывается, что мы сейчас удаляем какого-то из сыновей корня (для определенности далее левого, с правым аналогично). Тогда теперь правый сын становится корнем. На этом удаление заканчивается.
*<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
'''if ''' (можно свернуть направо вниз)
в t помещаем вершину, в которую свернули
'''while''' (пока t {{---}} не лист)
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
