Изменения

[[Файл:2_3tree23treemain.jpgpng|right|300px|thumb400px|Пример 2-3 дерева|thumb]]‎''' 2-3 дерево ''' (англ. ''2-3 tree'') — структура данных, предложенная в 1970 году Джоном Хопкрофтом,и представляющая собой [[B-сбалансированное дерево|B-дерево]] cтепени 1поиска, такое что из каждого узла может выходить две или три ветви; при этом требуетсяи глубина всех листьев одинакова. Является частным случаем [[B-дерево#B.2B-.D0.B4.D0.B5.D1.80.D0.B5.D0.B2.D0.BE|B+ дерева]].== Свойства ==2-3 дерево {{---}} сбалансированное дерево поиска, обладающее следующими свойствами:*нелистовые вершины имеют либо <tex>2</tex>, либо <tex>3</tex> сына,*нелистовая вершина, имеющая двух сыновей, хранит максимум левого поддерева. Нелистовая вершина, имеющая трех сыновей, хранит два значения. Первое значение хранит максимум левого поддерева, второе максимум центрального поддерева,*сыновья упорядочены по значению максимума поддерева сына, чтобы *все внешние узлы находились листья лежат на одном уровнеодной глубине,*высота 2-3 дерева <tex>O(\log{n})</tex>, где <tex> n </tex> {{---}} количество элементов в дереве.  == Операции ==Введем следующие обозначения:*<tex>\mathtt{root}</tex> {{---}} корень 2-3 дерева.Каждый внутренний узел содержит либо одиндерева обладает полями:*<tex>\mathtt{parent}</tex> {{---}} родитель узла,*<tex>\mathtt{sons}</tex> {{---}} сыновья узла, *<tex>\mathtt{keys}</tex> {{---}} ключи узла, *<tex>\mathtt{length}</tex> {{---}} количество сыновей.=== Поиск ===*<tex>x</tex> {{---}} искомое значение,*<tex>t</tex> {{---}} текущая вершина в дереве.  Изначально <tex>t = \mathtt{root}</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 '''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] [[Файл:23treesearch.png|thumb|center|600px|Поиск элемента 19, оранжевые стрелки обозначают путь по дереву при поиске]] === Вставка элемента ===*<tex>x</tex> {{---}} добавляемое значение,*<tex>t</tex> {{---}} текущая вершина в листьяхдереве. Изначально <tex>t = \mathtt{root}</tex>.Если корня не существует {{---}} дерево пустое, то новый элемент и будет корнем (одновременно и листом). Иначе поступим следующим образом: Найдем сперва, где бы находился элемент, применив <tex>\mathtt{search(x)}</tex>. Далее проверим есть ли у этого узла родитель, если его нет, то в вершинах хранится вспомогательная информациядереве всего один элемент {{---}} лист. Возьмем этот лист и новый узел,необходимая и создадим для организации поиска по поддеревьямних родителя, лист и новый узел расположим в порядке возрастания. Если родитель существует, то подвесим к нему ещё одного сына.Нелистовые вершины содержат 1 или 2 ключаЕсли сыновей стало <tex>4</tex>, то разделим родителя на два узла, и повторим разделение теперь для его родителя, ведь у него тоже могло быть уже <tex>3</tex> сына, указывающие а мы разделили и у него стало на диапазон значений в их поддеревьях<tex>1</tex> сына больше. (перед разделением обновим ключи).

'''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''' <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('''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 поддерева или 2 ключа и 3 поддереваподнимаемся вверх при расщеплении родителей не более одного раза, то <tex>\mathtt{insert}</tex> работает за <tex>O(\log{n})</tex>. Примеры добавления: [[Файл:23treeinsert.png|thumb|center|Добавление элемента с ключом 6|600px]] === Удаление элемента ===* Все листовые вершины находятся на одном уровне <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{searchNode(x)}</tex> {{---}} узел, где находится <tex>x</tex>. Если у <tex>t</tex> не существует родителя, то это корень (на нижнем уровнеодновременно и единственный элемент в дереве) . Удалим его. Если <tex>p</tex> существует, и содержат 1 или у него строго больше <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> {{--3 дерево - сливаемое дерево}} родителя <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> \log_mathtt{2updateKeys} n (b)</tex> и <tex> \log_mathtt{splitParent}(np)</tex>. Теперь рекурсивно удалим <tex>p</tex>. В результате мы получаем корректное по структуре 2-3 дерево, но у нас есть нарушение в ключах в узлах, исправим их с помощью <tex>\mathtt{updateKeys()} n </tex>, где запустившись от <tex>b</tex>.[[Файл:23treedelete.png|thumb|center|Удаление элемента с ключом 2|1150px]] === Следующий и предыдущий ===*<tex>x</tex> {{---}} поисковый параметр,*<tex> n 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.keys[0]  [[Файл:23treenext.png|thumb|center|400px|Путь при поиске следующего элемента после 2]] Поэтому операции над ним выполняются === Нахождение 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>. Добавим к узлам следующие поля:*<tex>\mathtt{right}</tex> {{---}} указывает на правый лист,*<tex>\mathtt{left}</tex> {{---}} указывает на левый лист.Пусть <tex>t</tex> {{---}} добавленный узел.Изменим <tex>\mathtt{insert}</tex> следующим образом: в самом конце, после того как мы уже обновили все ключи, найдем <tex>\mathtt{next(t)}</tex> и запишем ссылку на него в <tex>\mathtt{t.right}</tex>. Аналогично с левым. Пусть <tex>t</tex> {{---}} удаляемый узел. Изменим <tex>\mathtt{delete}</tex> следующим образом: в самом начале, до удаления <tex>t</tex>, найдем следующий <tex>\mathtt{next}</tex> и запишем в <tex>\mathtt{next.left}</tex> правый лист относительно <tex>t</tex>. С левым поступим аналогично.

== Операции ==* ''' Поиск '''Для поиска В итоге, мы имеем двусвязный список в 2-3 дереве необходимо последовательно просматривать ключилистьях, хранящиеся во внутренних ячейках, спускаясь от корня к листьям. Вначале ключ искомогоэлемента сравнивается с первым ключом ячейки ичтобы нам вывести <tex>m</tex> элементов, если искомый ключ не больше первого, то осуществляется переход в левое поддерево. Иначе, сравниваем искомый ключ со вторымключом в ячейке (если второго ключа нет — поддерева всего два, то сразу переходим вовторое поддерево) нам достаточно один раз найти нужный элемент и если наш ключ не превосходит второй ключ, то осуществляется переходв среднее поддерево, а если превосходит, то идем в правое поддеревопробежаться вправо на <tex>m</tex> элементов.

Если же в узле уже содержатся два ключа, делим его на два "одноключевых" узла и вставляем средний ключ в родительский узел.Это может привести к тому, что придется делить родительский узел. Тогда таким же образом проходим до корня дерева[[Файл:23treefindm.png|thumb|Изменение ссылок при добавлении нового элемента|thumb|center|800px]]

== См. также ==* [[B-дерево]]* [[Splay-дерево]]* ''' Удаление элемента '''[[АВЛ-дерево]]При удалении ключа из узла возникают три варианта.* [[Декартово дерево]]* [[Красно-черное дерево]]

Если до удаления ключа в узле содержалось три ключа, то после удаления ничего не меняется== Источники информации ==* [http://is.ifmo.ru/vis/tree23/tree23_ru.html is.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 дерево]* Д. Иначе у него три ребенкаКнут «Искусство программирования. Тогда присваиваем узлу с одним ключом один из этих ключей, таким образом получая два узла с двумя ключамиСортировка и поиск» {{---}} стр.508-509

Если два дерева разной высоты, то при слиянии меньшее добавляем как поддерево к одной из вершин большего.Если возникает ситуация,когда у необходимого узла уже есть три ребенка, то делим его на два узла с двумя поддеревьями [[Категория:Дискретная математика и проверяем родителя.Таким образом проходим по дереву вверх до полной сбалансировки.алгоритмы]][[Категория:Структуры данных]][[Категория:Деревья поиска]]