1632
правки
Изменения
м
Если у родителя <tex>\mathtt{t}</tex> <tex>2</tex> сына, то найдем у любого соседнего листа его родителя, обозначим его за <tex>p</tex>. Обозначим отца соседнего листа за <tex>p</tex>.Рассмотрим возможные случаи:
*<tex>p</tex> не существует, тогда мы удаляем одного из сыновей корня, тогда другой сын становится новым корнем,
*у <tex>\mathtt{t.parent}</tex> оказалось <tex>2</tex> сына, у <tex>p</tex> оказалось 2 сына. Подвесим <tex>b</tex> к <tex>p</tex> и удалим <tex>t</tex>, но у отца <tex>\mathtt{t.parent}</tex> не изменим количество детей. Так у отца <tex>\mathtt{t.parent}</tex> оказалось тоже два сына,повторяем для него такие же рассуждения.
*у <tex>\mathtt{t.parent}</tex> оказалось <tex>2</tex> сына, у <tex>p</tex> оказалось 2 сына. Подвесим <tex>b</tex> к <tex>p</tex> и удалим <tex>t</tex>, а у отца уменьшим количество детей. Так как у <tex>p</tex> оказалось четыре сына, то необходимо его расщепить. Теперь у отца <tex>\mathtt{t.parent}</tex> оказалось два сына и все узлы 2-3 дерева корректны.
*у <tex>\mathtt{t.parent}</tex> оказалось <tex>3</tex> сына, у <tex>p</tex> оказалось 2 сына. Подвесим <tex>b</tex> к <tex>p</tex> и удалим <tex>t</tex>, а у отца уменьшим количество детей. Так как у <tex>p</tex> оказалось три сына, а у отца <tex>\mathtt{t.parent}</tex> все ещё больше одного сына, то все узлы 2-3 дерева корректны.
*у <tex>\mathtt{t.parent}</tex> оказалось <tex>3</tex> сына, у <tex>p</tex> оказалось 3 сына. Подвесим <tex>b</tex> к <tex>p</tex> и удалим <tex>t</tex>, а у отца уменьшим количество детей. Так как у <tex>p</tex> оказалось четыре сына, то расщепим его, теперь у отца <tex>\mathtt{t.parent}</tex> вновь три сына и все узлы 2-3 дерева корректны.
'''return''' t '''return''' t.keys[0];
rollbackEdits.php mass rollback
=== Удаление элемента ===
*<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>\mathtt{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>.parentТак как у <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>np</tex> и прицепим его к <tex>p</tex>. Восстановим порядок в сыновьях <tex>p</tex>. Теперь у <tex>p</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>\mathtt{t}</tex> два сына(ниже мы никогда не уменьшаем количество детей у :*Если <tex>\mathtt{t.parent}np</tex>):*Если p не существует, то оказывается, что мы сейчас удаляем какого-то из сыновей корня (для определенности далее левого, с правым аналогично). Тогда теперь правый сын становится корнем. На этом удаление заканчивается.
*Если 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>.
В результате мы получаем корректное по структуре 2-3 дерево, но у нас есть нарушение в ключах в узлах, исправим их с помощью <tex>\mathtt{updateKeys()}</tex>, запустившись от <tex>b</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]
* [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
