Изменения

[[Файл: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> {{---}} текущая вершина в 2дереве. Изначально <tex>t = \mathtt{root}</tex>.Если корня не существует {{---3 }} деревопустое, то новый элемент и будет корнем (одновременно и листом).Иначе поступим следующим образом:

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

[[Файл:23treeadd3Если родитель существует, то подвесим к нему ещё одного сына.png|440px|border]] [[Файл:23treeadd4Если сыновей стало 4, то разделим родителя на два узла, и повторим разделение теперь для его родителя(перед разделением обновим ключи).png|400px|border]]

splitParent('''Node''' t): '''if''' (t.length > 3) Node a; a.sons[0] = t.sons[2] a.sons[1] = 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.sons[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 //Примечание: max легко находить, если хранить максимум //правого поддерева в каждом узле {{---}} это значение и будет max(a.sons[i])

[[Файл<tex>\mathtt{updateKeys}</tex> необходимо запускать от нового узла.Добавление элемента: insert('''int''' x):23treeadd1 Node n = Node(x) '''if''' (root == null) root = n return Node a = search(x) '''if''' (a.parent == '''null''') Node t = root root.png|490px|bordersons[0]= t root.sons[1] = n t.parent = root n.parent = root root.length = 2 сортируем сыновей у root '''else''' Node p = a.parent p.sons[[Файл:23treeadd2p.png|400px|border]length]= n p.length++ n.parent = p сортируем сыновей у p updateKeys(n) split(n) updateKeys(n) Так как мы спускаемся один раз, и поднимаемся вверх при расщеплении родителей не более одного раза, то <tex>\mathtt{insert}</tex> работает за <tex>O(\log{n})</tex>.

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

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

[[Файл:23treedel123treeinsert3.png|330px|border]] [[Файл:23treedel2.png|300px|border]] [[Файл:23treedel5.png|300px800px|border]]

3=== Удаление элемента ===*<tex>x</tex> {{---}} значение удаляемого узла,*<tex>t</tex> {{---}} текущий узел.Пусть изначально <tex>t = \mathtt{search(x) Иначе у него три ребенка. Тогда присваиваем узлу с одним ключом один из этих ключей}</tex> {{---}} узел, таким образом получая два узла с двумя ключамигде находится x.

[[Файл:23treedel3Если у <tex>t</tex> не существует родителя, то это корень.png|300px|border]] [[Файл:23treedel4Удалим его.png|320px|border]] [[Файл:23treedel6.png|300px|border]]

=== Слияние двух деревьев ===Возможно два варианта слияния двух деревьевЕсли у <tex>t</tex> существует родитель, и у него 3 сына, то просто удалим t. Обновим ключи, запустив <tex>\mathtt{updateKeys}</tex> от любого брата <tex>t</tex>.

1Если у родителя(<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]]

=== Следующий и предыдущий ===*<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; [[Файл:23treemerge1Treenext.png|400pxborder|border325px]] [[Файл:23treemerge2Treeprev.png|400pxborder|border300px]]

2) Если два дерева разной высоты=== Find ===B+ деревья, поддерживают операцию <tex>\mathtt{find}</tex>, которая позволяет находить m следующих элементов. Так как все листья отсортированы в порядке возрастания, то при слиянии меньшее добавляем как поддерево к одной из вершин большегопросто свяжем каждый лист с соседями. Если возникает ситуация*<tex>\mathtt{right}</tex> - правый лист,когда у необходимого узла *<tex>\mathtt{left}</tex> - левый лист.Доработаем добавление. Когда мы уже есть три ребенкадобавили элемент и обновили ключи, то делим его найдем для него следующий, и запишем на два узла с двумя поддеревьяминего ссылку в <tex>\mathtt{right}</tex>, переходим найдем предыдущий и запишем на него ссылку в родителя<tex>\mathtt{left}</tex>,так же и его соседям укажем ссылка на него.Таким образом будем проходим по дереву вверх пока дерево не станет корректнымДоработаем удаление. При удалении элемента, мы просто связываем его соседей за <tex>O(1)</tex>.

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