Самобалансирующееся двоичное дерево поиска

Пример несбалансированного дерева; следование пути от корня до узла занимает в среднем 3,27 обращений к узлу

То же дерево после балансировки по высоте; среднее усилие на пути снизилось до 3,00 обращений к узлу

В информатике самобалансирующееся двоичное дерево поиска (BST) — это любое узлов на основе двоичное дерево поиска , которое автоматически сохраняет свою высоту (максимальное количество уровней ниже корня) небольшой при вставке и удалении произвольных элементов. Эти операции, разработанные для самобалансирующегося двоичного дерева поиска, содержат меры предосторожности против безграничного увеличения высоты дерева, так что эти абстрактные структуры данных получают атрибут «самобалансирующийся».

Для бинарных деревьев со сбалансированной высотой высота определяется как логарифмическая. $O(\log n)$ в номере $n$ предметов. Это относится ко многим деревьям двоичного поиска, таким как деревья AVL и красно-черные деревья . Раскидистые деревья и тропы являются самобалансирующими, но не сбалансированными по высоте, поскольку их высота не гарантированно будет логарифмической по количеству элементов.

Самобалансирующиеся двоичные деревья поиска обеспечивают эффективную реализацию изменяемых упорядоченных списков и могут использоваться для других абстрактных структур данных, таких как ассоциативные массивы , очереди приоритетов и наборы .

Обзор

Вращение деревьев — это очень распространенная внутренняя операция в самобалансирующихся двоичных деревьях, позволяющая поддерживать идеальный или почти идеальный баланс.

Большинство операций с двоичным деревом поиска (BST) занимают время, прямо пропорциональное высоте дерева, поэтому желательно, чтобы высота была небольшой. Бинарное дерево высотой h может содержать не более 2 ⁰ +2 ¹ +···+2 ^час  = 2 ^{час +1} −1 узел. Отсюда следует, что для любого дерева с n узлами и высотой h :

$n\leq 2^{h+1}-1$

И это подразумевает:

$h\geq \lceil \log _{2}(n+1)-1\rceil \geq \lfloor \log _{2}n\rfloor$.

Другими словами, минимальная высота двоичного дерева с n узлами равна log ₂ ( n ), округленному в меньшую сторону ; то есть, $\lfloor \log _{2}n\rfloor$.

могут дать дерево высоты n Однако простейшие алгоритмы вставки элементов BST в довольно частых ситуациях . Например, когда элементы вставляются в отсортированном порядке ключей , дерево превращается в связанный список с n узлами. Разница в производительности между двумя ситуациями может быть огромной: например, когда n = 1 000 000, минимальная высота равна $\lfloor \log _{2}(1,000,000)\rfloor =19$.

Если элементы данных известны заранее, высоту можно поддерживать небольшой в среднем смысле, добавляя значения в случайном порядке, в результате чего получается случайное двоичное дерево поиска . Однако во многих ситуациях (например, в онлайн-алгоритмах ) такая рандомизация нежизнеспособна.

Самобалансирующиеся бинарные деревья решают эту проблему, выполняя преобразования дерева (например, повороты дерева ) во время вставки ключа, чтобы сохранить высоту, пропорциональную log ₂ ( n ). Хотя это и требует определенных накладных расходов , они не превышают всегда необходимых затрат на поиск и могут быть оправданы обеспечением быстрого выполнения всех операций.

Хотя возможно поддерживать BST минимальной высоты с ожидаемым $O(\log n)$ операций (поиск/вставка/удаление), дополнительные требования к пространству, необходимые для поддержания такой структуры, как правило, перевешивают уменьшение времени поиска. Для сравнения, AVL-дерево гарантированно имеет коэффициент 1,44 от оптимальной высоты, при этом в простой реализации требуется всего два дополнительных бита памяти. Поэтому большинство самобалансирующихся алгоритмов BST удерживают высоту в пределах постоянного коэффициента этой нижней границы.

В асимптотическом (« Big-O ») смысле самобалансирующаяся структура BST, содержащая n элементов, позволяет выполнять поиск, вставку и удаление элемента в $O(\log n)$ наихудшее время и упорядоченное перечисление всех элементов в $O(n)$ время. Для некоторых реализаций это границы времени для каждой операции, а для других — амортизированные границы для последовательности операций. Это время асимптотически оптимально среди всех структур данных, которые манипулируют ключом только посредством сравнения.

Реализации

Структуры данных, реализующие этот тип дерева, включают:

• 2–3 дерева
• АА-дерево
• АВЛ-дерево
• B-дерево
• Красно-черное дерево
• Дерево козла отпущения
• Дерево танго
• Треп
• Дерево со сбалансированным весом

Приложения

Самобалансирующиеся двоичные деревья поиска можно естественным образом использовать для создания и поддержания упорядоченных списков, таких как очереди с приоритетами . Их также можно использовать для ассоциативных массивов ; Пары ключ-значение просто вставляются в порядке, основанном только на ключе. В этом качестве самобалансирующиеся BST имеют ряд преимуществ и недостатков перед своим основным конкурентом — хеш-таблицами . Одним из преимуществ самобалансирующихся BST является то, что они позволяют быстро (действительно, асимптотически оптимально) перечислять элементы в ключевом порядке , чего не обеспечивают хеш-таблицы. Одним из недостатков является то, что их алгоритмы поиска усложняются, когда может быть несколько элементов с одним и тем же ключом. Самобалансирующиеся BST имеют лучшую производительность поиска в худшем случае, чем большинство хеш-таблицы ( $O(\log n)$ по сравнению с $O(n)$), но имеют худшую производительность в среднем случае ( $O(\log n)$ по сравнению с $O(1)$).

Самобалансирующиеся BST можно использовать для реализации любого алгоритма, требующего изменяемых упорядоченных списков, для достижения оптимальной асимптотической производительности в худшем случае. Например, если сортировка двоичного дерева реализована с помощью самобалансирующегося BST, мы получим очень простой для описания, но асимптотически оптимальный алгоритм. $O(n\log n)$ алгоритм сортировки. Точно так же многие алгоритмы в вычислительной геометрии используют варианты самобалансирующихся BST для решения таких проблем, как проблема пересечения отрезков прямой и проблема местоположения точки эффективного . (Однако для средней производительности самобалансирующиеся BST могут быть менее эффективными, чем другие решения. В частности, сортировка двоичного дерева, вероятно, будет медленнее, чем сортировка слиянием , быстрая сортировка или пирамидальная сортировка , из-за накладных расходов на балансировку дерева, поскольку а также шаблоны доступа к кешу .)

Самобалансирующиеся BST представляют собой гибкие структуры данных, поэтому их легко расширить для эффективной записи дополнительной информации или выполнения новых операций. Например, можно записать количество узлов в каждом поддереве, имеющем определенное свойство, что позволит подсчитать количество узлов в определенном диапазоне ключей с этим свойством в $O(\log n)$ время. Эти расширения можно использовать, например, для оптимизации запросов к базе данных или других алгоритмов обработки списков.

См. также

• Структура данных поиска
• Алгоритм Дэя – Стаута – Уоррена
• Дерево слияния
• Пропустить список
• Сортировка

Внешние ссылки

• Словарь алгоритмов и структур данных: сбалансированное по высоте двоичное дерево поиска
• GNU libavl , библиотека реализаций двоичных деревьев на C под лицензией LGPL, с документацией.