143
правки
Изменения
Нет описания правки
*сыновья упорядочены по значению максимума поддерева сына,
*все листья лежат на одной глубине,
*Высота 2-3 дерева <tex>O(\log{n})</tex>, где <tex> n </tex> {{- --}} количество элементов в дереве.
== Операции ==
'''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])
=== Find ===
B+ деревья, поддерживают операцию <tex>\mathtt{find}</tex>, которая позволяет находить m следующих элементов. Так как все листья отсортированы в порядке возрастания, то просто свяжем каждый лист с соседями.
*<tex>\mathtt{right}</tex> {{--- }} правый лист,*<tex>\mathtt{left}</tex> {{--- }} левый лист.
Доработаем добавление. Когда мы уже добавили элемент и обновили ключи, найдем для него следующий, и запишем на него ссылку в <tex>\mathtt{right}</tex>, найдем предыдущий и запишем на него ссылку в <tex>\mathtt{left}</tex>,так же и его соседям укажем ссылка на него.
[[Файл:23treefind.png|border]]
== См. также ==
* [[B-дерево]]
* [[Splay-дерево]]
* [[АВЛ-дерево]]
* [[Декартово дерево]]
* [[Красно-черное дерево]]
== Источники информации ==
* Д. Кнут «Искусство программирования. Сортировка и поиск», часть 6.2.4
[[Категория:Дискретная математика и алгоритмы]]
[[Категория:Структуры данных]]
[[Категория:Деревья поиска]]
