Изменения

[[Файл:23дерево_new.jpg‎ |right|300px|thumb|Пример 2-3 дерева]]‎''' 2-3 дерево ''' — структура данных, представляющая собой сбалансированное дерево поиска, такое что из каждого узла может выходить две или три ветви и глубина всех листьев одинакова. 2-3 дерево можно обобщить до Является частным случаем [[B-дерево#B.2B-.D0.B4.D0.B5.D1.80.D0.B5.D0.B2.D0.BE|B+-дерева]], когда нелистовые вершины могут иметь только 2 или 3 сыновей.  == Структура Свойства ==:*Все данные хранятся в листьях, в вершинах хранится вспомогательная информация2-3 дерево {{---}} сбалансированное дерево поиска,необходимая для организации поиска по поддеревьям. обладающее следующими свойствами:*Сыновья упорядочены по значению максимума поддерева сына. :*Нелистовые нелистовые вершины содержат 1 или имеют либо 2 ключа, указывающие на диапазон значений в их поддеревьях. либо 3 сына,:*Если нелистовая вершина имеет , имеющая двух сыновей, то вершина хранит минимум правого максимум левого поддерева; если . Нелистовая вершина, имеющая трехсыновей, то первый ключ равен минимуму среднего хранит два значения. Первое значение хранит максимум левого поддерева, а второй ключ равен минимуму правого второе максимум центрального поддерева. ,:*2-3 деревья сбалансированысыновья упорядочены по значению максимума поддерева сына, то есть каждое левое, правое, и центральное поддерево одинаковой высоты*все листья лежат на одной глубине, и таким образом содержат равное (или почти равное) число данных. :*Высота 2-3 дерева <tex>O(\log{n})</tex>, где <tex> n </tex> - количество элементов в дереве, поэтому операции поиска, добавления, удаления, слияния выполняются за время <tex>O(\log{n})</tex>.

Для поиска *<tex>x</tex> {{---}} искомое значение,*<tex>t</tex> {{---}} текущая вершина в 2-3 дереве необходимо последовательно . Изначально <tex>t = \mathtt{root}</tex>.Будем просматривать ключив узлах, пока узел не является листом. Рассмотрим два случая:хранящиеся во внутренних ячейках1)у текущей вершины два сына. Если её значение меньше <tex>x</tex>, то <tex>t = \mathtt{t.sons[1]}</tex>, спускаясь от корня к листьяминаче <tex>t = \mathtt{t.sons[0]}</tex>. Вначале ключ искомогоэлемента сравнивается с первым ключом ячейки и2)у текущей вершины три сына. Если второе значение меньше <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''' search('''int''' 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Пример поиска в 2-3 дереве, так как элемент 6 существует, то был возвращен корректный узел, так как элемента 10 нет — поддерева всего два, то сразу переходим вовозвращается некорректный узел. На основе этого можно сделать метод <tex>\mathtt{exist}</tex>, проверяющий наличии элемента в дереве. [[Файл:23treesearch.png|border]] === Вставка элемента ===второе поддерево) и если наш ключ не превосходит второй ключ*<tex>x</tex> {{---}} добавляемое значение, то осуществляется переход*<tex>t</tex> {{---}} текущая вершина в среднее поддерево, а если превосходитдереве. Изначально <tex>t = \mathtt{root}</tex>.Если корня не существует {{---}} дерево пустое, то идем в правое поддеревоновый элемент и будет корнем (одновременно и листом). Иначе поступим следующим образом:

=== Вставка элемента === Есть два варианта вставки Найдем сперва, где бы находился элемент, применив search(x). Далее проверим есть ли у этого узла родитель, если его нет, то в 2дереве всего один элемент {{-3 дерево--}} лист. Возьмем этот лист и новый узел, и создадим для них родителя, лист и новый узел расположим в порядке возрастания.

1) Чтобы поместить новый ключ в узелЕсли родитель существует, то подвесим к нему ещё одного сына. Если сыновей стало 4, в котором содержится ровно один ключто разделим родителя на два узла, необходимо просто добавить и повторим разделение теперь для его как второй ключ к узлуродителя (перед разделением обновим ключи).

splitParent('''Node''' t): '''if''' (t.length > 3) Node a; a.sons[0] = t.sons[2] a.sons[Файл:23treeadd31] = t.sons[3] 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''' //мы расщепили корень, надо подвесить его к общему родителю, который будет новым корнем Node t = root root.png|440px|bordersons[0]= t root.sons[1] = a t.parent = root a.parent = root root.length = 2 сортируем сыновей у rootЕсли сыновей стало 3, то ничего не делаем. Далее необходимо восстановить ключи на пути от новой вершины до корня: 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 //Примечание:23treeadd4max легко находить, если хранить максимум //правого поддерева в каждом узле {{---}} это значение и будет max(a.png|400px|border]sons[i] )

<tex>\mathtt{updateKeys}</tex> необходимо запускать от нового узла.Добавление элемента: insert('''int''' x): Node n = Node(x) '''if''' (root == null) root = n return Node a = search(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) Так как мы спускаемся один раз, делим его на два "одноключевых" узла и вставляем средний ключ в родительский узел.Это может привести к томуподнимаемся вверх при расщеплении родителей не более одного раза, что придется делить родительский узел. Тогда таким же образом проходим до корня деревато <tex>\mathtt{insert}</tex> работает за <tex>O(\log{n})</tex>.

[[ФайлПримеры добавления:23treeadd1.png|490px|border]] [[Файл:23treeadd2.png|400px|border]]

=== Удаление элемента ===При удалении ключа из узла возникают три варианта[[Файл:23treeinsert.png|border|600px]]

1) Если после удаления ключа в узле содержится два ключа, то после удаления ничего не меняется[[Файл:23treeinsert2.png|800px|border]]

2) Если же у ключа после удаления остался один элемент, то проверяем количество потомков второго ребенка того узла, ребенком которого является узел с удаляемым ключом. Если у него два ребенка, то присваиваем ему оставшийся один элемент. Вершину, оставшуюся без детей, удаляем рекурсивно[[Файл:23treeinsert3. png|800px|border]]

[[Файл:23treedel1=== Удаление элемента ===*<tex>x</tex> {{---}} значение удаляемого узла,*<tex>t</tex> {{---}} текущий узел.png|330px|border]] [[Файл:23treedel2Пусть изначально <tex>t = \mathtt{search(x)}</tex> {{---}} узел, где находится x.png|300px|border]] [[Файл:23treedel5.png|300px|border]]

3) Иначе Если у него три ребенка<tex>t</tex> не существует родителя, то это корень. Тогда присваиваем узлу с одним ключом один из этих ключей, таким образом получая два узла с двумя ключамиУдалим его.

[[Файл:23treedel3Если у <tex>t</tex> существует родитель, и у него 3 сына, то просто удалим t.png|300px|border]] [[Файл:23treedel4Обновим ключи, запустив <tex>\mathtt{updateKeys}</tex> от любого брата <tex>t</tex>.png|320px|border]] [[Файл:23treedel6.png|300px|border]]

=== Слияние двух деревьев ===Если у родителя(<tex>\mathtt{t.parent}</tex>) 2 сына, то удалим <tex>t</tex>, а его брата(<tex>b</tex> перецепим к родителю соседнего листа(обозначим его за <tex>p</tex>). Вызовем <tex>updateKey(b)</tex> и <tex>splitParent(p)</tex>, так как у <tex>p</tex> могло оказаться 4 сына. Удалим теперь и <tex>\mathtt{t.parent}</tex>. После возврата из рекурсии обновим все ключи с помощью <tex>\mathtt{updateKeys()}</tex>, запустившись от <tex>b</tex>.Возможно два варианта слияния двух деревьев[[Файл:Treedelete.png|border|1150px]]

1) === Следующий и предыдущий ===*<tex>x</tex> {{---}} поисковый параметр,*<tex>t</tex> {{---}} текущий узел.В силу того, что наши узлы отсортированы по максимуму в поддереве, то следующий объект это соседний лист справа. Попасть туда можно следующим образом:будем подниматься вверх, пока у нас не появится первой возможности свернуть направо вниз. Как только мы свернули направо вниз, будем идти всегда влево. Таким образом, мы окажемся в соседнем листе. Если два дерева одной высотымы не смогли ни разу свернуть направо вниз, и пришли в корень, то слияние представляет собой добавление общей вершиныследующего объекта не существует. Случай с предыдущим симметричен. Node next('''int x''') Node t = search(x) '''if''' (t.keys[0] > x) //x не было в дереве, и мы нашли следующий сразу '''return''' t '''while''' (t != '''null''') t = t.parent if (можно свернуть направо вниз) в t помещаем вершину, в которую свернули '''while''' (пока t {{---}} не лист) t = t.sons[0] '''return''' t '''return''' t; [[Файл:Treenext.png|border|325px]] [[Файл:Treeprev.png|border|300px]]

[[Файл:23treemerge1=== Find ===B+ деревья, поддерживают операцию <tex>\mathtt{find}</tex>, которая позволяет находить m следующих элементов.png|400px|border]] [[Файл:23treemerge2Так как все листья отсортированы в порядке возрастания, то просто свяжем каждый лист с соседями.*<tex>\mathtt{right}</tex> - правый лист,*<tex>\mathtt{left}</tex> - левый лист.Доработаем добавление. Когда мы уже добавили элемент и обновили ключи, найдем для него следующий, и запишем на него ссылку в <tex>\mathtt{right}</tex>, найдем предыдущий и запишем на него ссылку в <tex>\mathtt{left}</tex>,так же и его соседям укажем ссылка на него.png|400px|border]]

2) Если два дерева разной высоты, то при слиянии меньшее добавляем как поддерево к одной из вершин большегоДоработаем удаление. Если возникает ситуация,когда у необходимого узла уже есть три ребенкаПри удалении элемента, то делим мы просто связываем его на два узла с двумя поддеревьями, переходим в родителя.Таким образом будем проходим по дереву вверх пока дерево не станет корректнымсоседей за <tex>O(1)</tex>.

[[Файл:23treemerge323treefind.png|400px|border]] [[Файл:23treemerge4.png|400px|border]]

== Cсылки Источники информации ==* [http://is.ifmo.ru/vis/tree23/tree23_ru.html is.ifmo.ru {{- --}} Визуализатор 2-3 дерева — 1]* [http://rain.ifmo.ru/cat/view.php/vis/trees/2-3-2002 rain.ifmo.ru {{--- }} Визуализатор 2-3 дерева — 2]* [http://ru.wikipedia.org/wiki/2-3-дерево Википедия — {{---}} 2-3 дерево]