2-3 дерево — различия между версиями
(→Удаление элемента) |
м (rollbackEdits.php mass rollback) |
||
(не показано 48 промежуточных версий 8 участников) | |||
Строка 6: | Строка 6: | ||
*сыновья упорядочены по значению максимума поддерева сына, | *сыновья упорядочены по значению максимума поддерева сына, | ||
*все листья лежат на одной глубине, | *все листья лежат на одной глубине, | ||
− | * | + | *высота 2-3 дерева <tex>O(\log{n})</tex>, где <tex> n </tex> {{---}} количество элементов в дереве. |
== Операции == | == Операции == | ||
Строка 25: | Строка 25: | ||
*у текущей вершины три сына. Если второе значение меньше <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>. | *у текущей вершины три сына. Если второе значение меньше <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>. | ||
− | ''' | + | '''T''' search('''T''' x): |
Node t = root | Node t = root | ||
'''while''' (t не является листом) | '''while''' (t не является листом) | ||
Строка 31: | Строка 31: | ||
'''if''' (t.keys[0] < x) | '''if''' (t.keys[0] < x) | ||
t = t.sons[1] | t = t.sons[1] | ||
− | '''else''' t = t.sons[0] | + | '''else''' |
− | '''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 | + | '''return''' t.keys[0] |
− | |||
− | [[Файл:23treesearch.png|thumb|center|600px|Поиск элемента | + | [[Файл:23treesearch.png|thumb|center|600px|Поиск элемента 19, оранжевые стрелки обозначают путь по дереву при поиске]] |
=== Вставка элемента === | === Вставка элемента === | ||
Строка 51: | Строка 50: | ||
Найдем сперва, где бы находился элемент, применив <tex>\mathtt{search(x)}</tex>. Далее проверим есть ли у этого узла родитель, если его нет, то в дереве всего один элемент {{---}} лист. Возьмем этот лист и новый узел, и создадим для них родителя, лист и новый узел расположим в порядке возрастания. | Найдем сперва, где бы находился элемент, применив <tex>\mathtt{search(x)}</tex>. Далее проверим есть ли у этого узла родитель, если его нет, то в дереве всего один элемент {{---}} лист. Возьмем этот лист и новый узел, и создадим для них родителя, лист и новый узел расположим в порядке возрастания. | ||
− | Если родитель существует, то подвесим к нему ещё одного сына. Если сыновей стало <tex>4</tex>, то разделим родителя на два узла, и повторим разделение теперь для его родителя (перед разделением обновим ключи). | + | Если родитель существует, то подвесим к нему ещё одного сына. Если сыновей стало <tex>4</tex>, то разделим родителя на два узла, и повторим разделение теперь для его родителя, ведь у него тоже могло быть уже <tex>3</tex> сына, а мы разделили и у него стало на <tex>1</tex> сына больше. (перед разделением обновим ключи). |
− | splitParent('''Node''' t): | + | '''function''' splitParent('''Node''' t): |
'''if''' (t.length > 3) | '''if''' (t.length > 3) | ||
− | + | Node a = Node(sons = {t.sons[2], t.sons[3]}, keys = {t.keys[2]}, parent = t.parent, length = 2) | |
− | + | t.sons[2].parent = a | |
− | + | t.sons[3].parent = a | |
− | + | 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>, то ничего не делаем. Далее необходимо восстановить ключи на пути от новой вершины до корня: | Если сыновей стало <tex>3</tex>, то ничего не делаем. Далее необходимо восстановить ключи на пути от новой вершины до корня: | ||
− | updateKeys('''Node''' t): | + | '''function''' updateKeys('''Node''' t): |
Node a = t.parent | Node a = t.parent | ||
− | '''while''' (a != | + | '''while''' (a != ''null'') |
'''for''' i = 0 .. a.length - 1 | '''for''' i = 0 .. a.length - 1 | ||
− | a.keys[i] = max(a.sons[i]) //max {{---}} возвращает максимальное значение в поддереве. | + | a.keys[i] = max(a.sons[i]) <font color=green>// max {{---}} возвращает максимальное значение в поддереве.</font> |
− | a = a.parent //Примечание: max легко находить, если хранить максимум | + | a = a.parent <font color=green>// Примечание: max легко находить, если хранить максимум </font> |
− | //правого поддерева в каждом узле {{---}} это значение и будет max(a.sons[i]) | + | <font color=green>// правого поддерева в каждом узле {{---}} это значение и будет max(a.sons[i])</font> |
<tex>\mathtt{updateKeys}</tex> необходимо запускать от нового узла. | <tex>\mathtt{updateKeys}</tex> необходимо запускать от нового узла. | ||
Добавление элемента: | Добавление элемента: | ||
− | insert(''' | + | '''function''' insert('''T''' x): |
− | + | Node n = Node(x) | |
− | + | '''if''' (root == ''null'') | |
− | + | root = n | |
− | + | '''return''' | |
− | + | Node a = searchNode(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) | updateKeys(n) | ||
− | |||
− | |||
Так как мы спускаемся один раз, и поднимаемся вверх при расщеплении родителей не более одного раза, то <tex>\mathtt{insert}</tex> работает за <tex>O(\log{n})</tex>. | Так как мы спускаемся один раз, и поднимаемся вверх при расщеплении родителей не более одного раза, то <tex>\mathtt{insert}</tex> работает за <tex>O(\log{n})</tex>. | ||
Строка 120: | Строка 115: | ||
=== Удаление элемента === | === Удаление элемента === | ||
*<tex>x</tex> {{---}} значение удаляемого узла, | *<tex>x</tex> {{---}} значение удаляемого узла, | ||
− | *<tex>t</tex> {{---}} текущий узел. | + | *<tex>t</tex> {{---}} текущий узел, |
− | Пусть изначально <tex>t = \mathtt{ | + | *<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{searchNode(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>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>p</tex>, а у <tex>gp</tex> уменьшим количество детей. Так как у <tex>np</tex> оказалось три сына, а у <tex>gp</tex> все ещё больше одного сына, то все узлы 2-3 дерева корректны. | ||
− | |||
− | |||
− | *Если | + | Обобщим алгоритм при удалении когда у родителя <tex>t</tex> два сына: |
+ | *Если <tex>np</tex> не существует, то оказывается, что мы сейчас удаляем какого-то из сыновей корня (для определенности далее левого, с правым аналогично). Тогда теперь правый сын становится корнем. На этом удаление заканчивается. | ||
− | *Если | + | *Если <tex>np</tex> существует, то удалим <tex>t</tex>, а его брата (<tex>b</tex>) перецепим к <tex>np</tex>. Теперь у <tex>np</tex> могло оказаться <tex>4</tex> сына, поэтому повторим аналогичные действия из <tex>\mathtt{insert}</tex>: вызовем <tex>\mathtt{updateKeys}(b)</tex> и <tex>\mathtt{splitParent}(np)</tex>. Теперь рекурсивно удалим <tex>p</tex>. |
− | + | В результате мы получаем корректное по структуре 2-3 дерево, но у нас есть нарушение в ключах в узлах, исправим их с помощью <tex>\mathtt{updateKeys()}</tex>, запустившись от <tex>b</tex>. | |
[[Файл:23treedelete.png|thumb|center|Удаление элемента с ключом 2|1150px]] | [[Файл:23treedelete.png|thumb|center|Удаление элемента с ключом 2|1150px]] | ||
Строка 139: | Строка 145: | ||
*<tex>x</tex> {{---}} поисковый параметр, | *<tex>x</tex> {{---}} поисковый параметр, | ||
*<tex>t</tex> {{---}} текущий узел. | *<tex>t</tex> {{---}} текущий узел. | ||
− | В силу того, что наши узлы отсортированы по максимуму в поддереве, то следующий объект это соседний лист справа. Попасть туда можно следующим образом: | + | В силу того, что наши узлы отсортированы по максимуму в поддереве, то следующий объект {{---}} это соседний лист справа. Попасть туда можно следующим образом: |
будем подниматься вверх, пока у нас не появится первой возможности свернуть направо вниз. Как только мы свернули направо вниз, будем идти всегда влево. Таким образом, мы окажемся в соседнем листе. Если мы не смогли ни разу свернуть направо вниз, и пришли в корень, то следующего объекта не существует. Случай с предыдущим симметричен. | будем подниматься вверх, пока у нас не появится первой возможности свернуть направо вниз. Как только мы свернули направо вниз, будем идти всегда влево. Таким образом, мы окажемся в соседнем листе. Если мы не смогли ни разу свернуть направо вниз, и пришли в корень, то следующего объекта не существует. Случай с предыдущим симметричен. | ||
− | + | '''T''' next('''T''' x): | |
− | + | Node t = searchNode(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 | ||
− | + | '''return''' t.keys[0] | |
Строка 158: | Строка 164: | ||
=== Нахождение m следующих элементов === | === Нахождение m следующих элементов === | ||
− | B+ деревья, поддерживают операцию <tex>\mathtt{find}</tex>, которая позволяет находить m следующих элементов. Наивная реализация выглядит следующим образом: будем вызывать <tex>m</tex> раз поиск следующего элемента, такое решение работает за <tex>O(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 элементов. Нам необходимо связать листья, для этого модифицируем | По построению, все листья у нас отсортированы в порядке возрастания, воспользуемся этим для нахождения m элементов. Нам необходимо связать листья, для этого модифицируем | ||
<tex>\mathtt{insert}</tex> и <tex>\mathtt{delete}</tex>. Добавим к узлам следующие поля: | <tex>\mathtt{insert}</tex> и <tex>\mathtt{delete}</tex>. Добавим к узлам следующие поля: | ||
Строка 185: | Строка 191: | ||
* [http://rain.ifmo.ru/cat/view.php/vis/trees/2-3-2002 rain.ifmo.ru {{---}} Визуализатор 2-3 дерева] | * [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 дерево] | * [http://ru.wikipedia.org/wiki/2-3-дерево Википедия {{---}} 2-3 дерево] | ||
− | * Д. Кнут «Искусство программирования. Сортировка и поиск» {{---}} стр. 508 - 509 | + | * Д. Кнут «Искусство программирования. Сортировка и поиск» {{---}} стр. 508-509 |
Текущая версия на 19:39, 4 сентября 2022
Свойства
2-3 дерево — сбалансированное дерево поиска, обладающее следующими свойствами:
- нелистовые вершины имеют либо , либо сына,
- нелистовая вершина, имеющая двух сыновей, хранит максимум левого поддерева. Нелистовая вершина, имеющая трех сыновей, хранит два значения. Первое значение хранит максимум левого поддерева, второе максимум центрального поддерева,
- сыновья упорядочены по значению максимума поддерева сына,
- все листья лежат на одной глубине,
- высота 2-3 дерева , где — количество элементов в дереве.
Операции
Введем следующие обозначения:
- — корень 2-3 дерева.
Каждый узел дерева обладает полями:
- — родитель узла,
- — сыновья узла,
- — ключи узла,
- — количество сыновей.
Поиск
- — искомое значение,
- — текущая вершина в дереве.
Изначально
. Будем просматривать ключи в узлах, пока узел не является листом. Рассмотрим два случая:- у текущей вершины два сына. Если её значение меньше , то , иначе .
- у текущей вершины три сына. Если второе значение меньше , то . Если первое значение меньше , то , иначе .
T search(T x): Node t = root while (t не является листом) if (t.length == 2) 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.keys[0]
Вставка элемента
- — добавляемое значение,
- — текущая вершина в дереве. Изначально .
Если корня не существует — дерево пустое, то новый элемент и будет корнем (одновременно и листом). Иначе поступим следующим образом:
Найдем сперва, где бы находился элемент, применив
. Далее проверим есть ли у этого узла родитель, если его нет, то в дереве всего один элемент — лист. Возьмем этот лист и новый узел, и создадим для них родителя, лист и новый узел расположим в порядке возрастания.Если родитель существует, то подвесим к нему ещё одного сына. Если сыновей стало
, то разделим родителя на два узла, и повторим разделение теперь для его родителя, ведь у него тоже могло быть уже сына, а мы разделили и у него стало на сына больше. (перед разделением обновим ключи).function splitParent(Node t): if (t.length > 3) Node a = Node(sons = {t.sons[2], t.sons[3]}, keys = {t.keys[2]}, parent = t.parent, length = 2) t.sons[2].parent = a t.sons[3].parent = a 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 // мы расщепили корень, надо подвесить его к общему родителю, который будет новым корнем Node t = root root.sons[0] = t root.sons[1] = a t.parent = root a.parent = root root.length = 2 сортируем сыновей у root
Если сыновей стало
, то ничего не делаем. Далее необходимо восстановить ключи на пути от новой вершины до корня:function updateKeys(Node t): Node a = t.parent while (a != null) for i = 0 .. a.length - 1 a.keys[i] = max(a.sons[i]) // max — возвращает максимальное значение в поддереве. a = a.parent // Примечание: max легко находить, если хранить максимум // правого поддерева в каждом узле — это значение и будет max(a.sons[i])
необходимо запускать от нового узла. Добавление элемента:
function insert(T x): Node n = Node(x) if (root == null) root = n return Node a = searchNode(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)
Так как мы спускаемся один раз, и поднимаемся вверх при расщеплении родителей не более одного раза, то
работает за .Примеры добавления:
Удаление элемента
- — значение удаляемого узла,
- — текущий узел,
- — брат ,
- — отец ,
- — соседний брат ,
- — отец .
Пусть изначально
— узел, где находится .Если у
не существует родителя, то это корень (одновременно и единственный элемент в дереве). Удалим его.Если
существует, и у него строго больше сыновей, то просто удалим , а у уменьшим количество детей.Если у родителя
два сына, рассмотрим возможные случаи (сперва везде удаляем ):- не существует, тогда мы удаляем одного из сыновей корня, следовательно, другой сын становится новым корнем,
- у оказалось сына, у оказалось сына. Подвесим к и удалим . Так как у — родителя , оказалось тоже два сына, повторяем для такие же рассуждения,
- у оказалось или сына, у оказалось сына. Просто заберем ближайшего к нам сына у и прицепим его к . Восстановим порядок в сыновьях . Теперь у оказалось снова два сына и все узлы 2-3 дерева корректны,
- у оказалось сына, у оказалось сына. Подвесим к и удалим , а у уменьшим количество детей. Так как у оказалось три сына, а у все ещё больше одного сына, то все узлы 2-3 дерева корректны.
Обобщим алгоритм при удалении когда у родителя
два сына:- Если не существует, то оказывается, что мы сейчас удаляем какого-то из сыновей корня (для определенности далее левого, с правым аналогично). Тогда теперь правый сын становится корнем. На этом удаление заканчивается.
- Если существует, то удалим , а его брата ( ) перецепим к . Теперь у могло оказаться сына, поэтому повторим аналогичные действия из : вызовем и . Теперь рекурсивно удалим .
В результате мы получаем корректное по структуре 2-3 дерево, но у нас есть нарушение в ключах в узлах, исправим их с помощью
, запустившись от .Следующий и предыдущий
- — поисковый параметр,
- — текущий узел.
В силу того, что наши узлы отсортированы по максимуму в поддереве, то следующий объект — это соседний лист справа. Попасть туда можно следующим образом: будем подниматься вверх, пока у нас не появится первой возможности свернуть направо вниз. Как только мы свернули направо вниз, будем идти всегда влево. Таким образом, мы окажемся в соседнем листе. Если мы не смогли ни разу свернуть направо вниз, и пришли в корень, то следующего объекта не существует. Случай с предыдущим симметричен.
T next(T x): Node t = searchNode(x) if (t.keys[0] > x) //x не было в дереве, и мы нашли следующий сразу 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+ деревья, поддерживают операцию
, которая позволяет находить m следующих элементов. Наивная реализация выглядит следующим образом: будем вызывать раз поиск следующего элемента, такое решение работает за . Но 2-3 деревья, позволяют находить m следующих элементов за , что значительно ускоряет поиск при больших . По построению, все листья у нас отсортированы в порядке возрастания, воспользуемся этим для нахождения m элементов. Нам необходимо связать листья, для этого модифицируем и . Добавим к узлам следующие поля:- — указывает на правый лист,
- — указывает на левый лист.
Пусть
— добавленный узел. Изменим следующим образом: в самом конце, после того как мы уже обновили все ключи, найдем и запишем ссылку на него в . Аналогично с левым.Пусть
— удаляемый узел. Изменим следующим образом: в самом начале, до удаления , найдем следующий и запишем в правый лист относительно . С левым поступим аналогично.В итоге, мы имеем двусвязный список в листьях, и чтобы нам вывести
элементов, нам достаточно один раз найти нужный элемент и пробежаться вправо на элементов.
См. также
Источники информации
- is.ifmo.ru — Визуализатор 2-3 дерева
- rain.ifmo.ru — Визуализатор 2-3 дерева
- Википедия — 2-3 дерево
- Д. Кнут «Искусство программирования. Сортировка и поиск» — стр. 508-509