Изменения

Перейти к: навигация, поиск

2-3 дерево

654 байта убрано, 19:39, 4 сентября 2022
м
rollbackEdits.php mass rollback
*сыновья упорядочены по значению максимума поддерева сына,
*все листья лежат на одной глубине,
*Высота высота 2-3 дерева <tex>O(\log{n})</tex>, где <tex> n </tex> {{---}} количество элементов в дереве.
== Операции ==
*у текущей вершины три сына. Если второе значение меньше <tex>x</tex>, то <tex>t = \mathtt{t.sons[2]}</tex>. Если первое значение меньше <tex>x</tex>, то <tex>t = \mathtt{t.sons[1]}</tex>, иначе <tex>t = \mathtt{t.sons[0]}</tex>.
Node '''T''' search('''T''' x):
Node t = root
'''while''' (t не является листом)
'''if''' (t.keys[0] < x)
t = t.sons[1]
'''else''' t = t.sons[0] '''else''' '''if''' (t.keys[1] < x) t = t.sons[2] '''else''' '''if''' (t.keys[0] < x) t = t.sons[1] '''else''' t = t.sons[0] '''return''' tПример поиска в 2-3 дереве, так как элемент <tex>6</tex> существует, то был возвращен корректный узел, так как элемента <tex>10</tex> нет, возвращается некорректный узел. На основе этого можно сделать метод <tex>\mathtt{exist}</tex>, проверяющий наличии элемента в дереве.keys[0]
[[Файл:23treesearch.png|thumb|center|600px|Поиск элемента 219, оранжевые стрелки обозначают путь по дереву при поиске]]
=== Вставка элемента ===
Найдем сперва, где бы находился элемент, применив <tex>\mathtt{search(x)}</tex>. Далее проверим есть ли у этого узла родитель, если его нет, то в дереве всего один элемент {{---}} лист. Возьмем этот лист и новый узел, и создадим для них родителя, лист и новый узел расположим в порядке возрастания.
Если родитель существует, то подвесим к нему ещё одного сына. Если сыновей стало <tex>4</tex>, то разделим родителя на два узла, и повторим разделение теперь для его родителя , ведь у него тоже могло быть уже <tex>3</tex> сына, а мы разделили и у него стало на <tex>1</tex> сына больше. (перед разделением обновим ключи).
'''function''' splitParent('''Node''' t):
'''if''' (t.length > 3)
Node a; a.= Node(sons[0] = {t.sons[2] a, t.sons[13] }, keys = {t.sonskeys[32]}, parent = t.parent, length = 2) t.sons[2].parent = a t.sons[3].parent = a a.keys[0] = t.keys[2] a.length = 2 t.length = 2 t.sons[2] = '''null''' t.sons[3] = '''null''' '''if''' (t.parent != '''null''') t.parent[t.length] = a t.length++ сортируем сыновей у t.parent splitParent(t.parent) '''else''' <font color=green>//мы расщепили корень, надо подвесить его к общему родителю, который будет новым корнем</font> Node t = root root.sons[0] = t root.sons[1] = a t.parent = root a.parent = root root.length = 2 сортируем сыновей у root
Если сыновей стало <tex>3</tex>, то ничего не делаем. Далее необходимо восстановить ключи на пути от новой вершины до корня:
'''function''' updateKeys('''Node''' t):
Node a = t.parent
'''while''' (a != '''null''')
'''for''' i = 0 .. a.length - 1
a.keys[i] = max(a.sons[i]) <font color=green>//max {{---}} возвращает максимальное значение в поддереве.</font> a = a.parent <font color=green>//Примечание: max легко находить, если хранить максимум </font> <font color=green>//правого поддерева в каждом узле {{---}} это значение и будет max(a.sons[i])</font>
<tex>\mathtt{updateKeys}</tex> необходимо запускать от нового узла.
Добавление элемента:
'''function''' insert('''intT''' x): Node n = Node(x) '''if''' (root == ''null'') root = n '''return''' Node a = searchsearchNode(x) '''if''' (a.parent == '''null''') Node t = root root.sons[0] = t root.sons[1] = n t.parent = root n.parent = root root.length = 2 сортируем сыновей у root '''else''' Node p = a.parent p.sons[p.length] = n p.length++ n.parent = p сортируем сыновей у p updateKeys(n) split(n)
updateKeys(n)
split(n)
updateKeys(n)
Так как мы спускаемся один раз, и поднимаемся вверх при расщеплении родителей не более одного раза, то <tex>\mathtt{insert}</tex> работает за <tex>O(\log{n})</tex>.
=== Удаление элемента ===
*<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>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>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>tp</tex>, а у <tex>\mathtt{t.parent}gp</tex> уменьшим количество детей. Так как у <tex>np</tex> оказалось три сына, а у <tex>gp</tex> все ещё больше одного сына, то все узлы 2-3 дерева корректны.
Если у родителя <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 дерева корректны.
Обобщим алгоритм при удалении когда у родителя <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> {{---}} текущий узел.
В силу того, что наши узлы отсортированы по максимуму в поддереве, то следующий объект {{---}} это соседний лист справа. Попасть туда можно следующим образом:
будем подниматься вверх, пока у нас не появится первой возможности свернуть направо вниз. Как только мы свернули направо вниз, будем идти всегда влево. Таким образом, мы окажемся в соседнем листе. Если мы не смогли ни разу свернуть направо вниз, и пришли в корень, то следующего объекта не существует. Случай с предыдущим симметричен.
Node '''T''' next('''int xT'''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]
=== Нахождение m следующих элементов ===
B+ деревья, поддерживают операцию <tex>\mathtt{find}</tex>, которая позволяет находить m следующих элементов. Наивная реализация выглядит следующим образом: будем вызывать <tex>m</tex> раз поиск следующего элемента, такое решение работает за <tex>O(m * \log{n})</tex>. Но 2-3 деревья, позволяют находить m следующих элементов за <tex>O(m + \log{n})</tex>, что значительно ускоряет поиск при больших <tex>m</tex>.
По построению, все листья у нас отсортированы в порядке возрастания, воспользуемся этим для нахождения m элементов. Нам необходимо связать листья, для этого модифицируем
<tex>\mathtt{insert}</tex> и <tex>\mathtt{delete}</tex>. Добавим к узлам следующие поля:
* [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
1632
правки

Навигация