В информатике , самобалансировка (или высота сбалансировано ) бинарное дерево поиска является любым узел - бинарным дерево поиска , которая автоматически сохраняет свою высоту (максимальное число уровней ниже корня) малых в условиях произвольных вставок элементов и удалений. [1]
Эти структуры обеспечивают эффективные реализации изменяемых упорядоченных списков и могут использоваться для других абстрактных структур данных, таких как ассоциативные массивы , очереди и наборы приоритетов .
Красно-черное дерево , которое является типом самобалансирующегося бинарного дерева поиска, было названо симметричным бинарное B-дерево [2] и было переименовано , но все - таки можно спутать с родовым понятием самобалансирующегося бинарного дерева поиска , так как из инициалы.
Обзор
Большинство операций с двоичным деревом поиска (BST) занимают время, прямо пропорциональное высоте дерева, поэтому желательно, чтобы высота оставалась небольшой. Бинарное дерево с высотой h может содержать не более 2 0 +2 1 + ... + 2 h = 2 h +1 −1 узлов. Отсюда следует, что для любого дерева с n узлами и высотой h :
А это подразумевает:
.
Другими словами, минимальная высота двоичного дерева с n узлами равна log 2 ( n ) с округлением в меньшую сторону ; это,. [1]
Однако простейшие алгоритмы вставки элементов BST могут дать дерево с высотой n в довольно распространенных ситуациях. Например, когда элементы вставляются в отсортированном ключевом порядке, дерево вырождается в связанный список с n узлами. Разница в производительности между двумя ситуациями может быть огромной: например, при n = 1000000 минимальная высота составляет.
Если элементы данных известны заранее, высоту можно сохранить небольшой, в среднем смысле, путем добавления значений в случайном порядке, что приведет к случайному двоичному дереву поиска . Однако во многих ситуациях (например, в онлайн-алгоритмах ) такая рандомизация нецелесообразна.
Самобалансирующиеся двоичные деревья решают эту проблему, выполняя преобразования дерева (например, вращения дерева ) во время вставки ключей, чтобы сохранить высоту, пропорциональную log 2 ( n ). Хотя это связано с определенными накладными расходами , в конечном итоге это может быть оправдано за счет обеспечения быстрого выполнения последующих операций.
Хотя возможно поддерживать BST с минимальной высотой с ожидаемым время операций (поиск / вставка / удаление), дополнительные требования к пространству, необходимые для поддержания такой структуры, имеют тенденцию перевешивать уменьшение времени поиска. Для сравнения: дерево AVL гарантированно находится в пределах 1,44 раз от оптимальной высоты, при этом для наивной реализации требуется только два дополнительных бита памяти. [1] Следовательно, большинство самобалансирующихся алгоритмов BST удерживают высоту в пределах постоянного множителя этой нижней границы.
В асимптотическом (« Big-O ») смысле самобалансирующаяся структура BST, содержащая n элементов, позволяет выполнять поиск, вставку и удаление элемента за время O (log n ) наихудшего случая и упорядоченное перечисление всех элементов в O ( n ) раз. Для некоторых реализаций это временные границы для каждой операции, в то время как для других они являются амортизированными границами для последовательности операций. Это время является асимптотически оптимальным среди всех структур данных, которые управляют ключом только посредством сравнений.
Реализации
Структуры данных, реализующие этот тип дерева, включают:
- 2–3 дерева
- Дерево AA
- Дерево AVL
- B-дерево
- Красно-черное дерево
- Козел отпущения
- Splay tree
- Танго дерево
- Treap
- Балансированное дерево
Приложения
Самобалансирующиеся деревья двоичного поиска могут использоваться естественным образом для создания и поддержки упорядоченных списков, таких как очереди приоритетов . Их также можно использовать для ассоциативных массивов ; Пары ключ-значение просто вставляются с упорядочением на основе одного ключа. В этом качестве самобалансирующиеся BST имеют ряд преимуществ и недостатков по сравнению с их основным конкурентом, хеш-таблицами . Одним из преимуществ самобалансирующихся BST является то, что они позволяют быстро (действительно, асимптотически оптимально) перечислять элементы в ключевом порядке., которые хеш-таблицы не предоставляют. Одним из недостатков является то, что их алгоритмы поиска усложняются, когда может быть несколько элементов с одним и тем же ключом. Самобалансирующиеся BST имеют лучшую производительность поиска в худшем случае, чем хэш-таблицы (O (log n) по сравнению с O (n)), но имеют худшую производительность в среднем случае (O (log n) по сравнению с O (1)).
Самобалансирующиеся BST могут использоваться для реализации любого алгоритма, требующего изменяемых упорядоченных списков, для достижения оптимальной асимптотической производительности в худшем случае. Например, если сортировка двоичного дерева реализована с помощью самоуравновешенного BST, у нас есть очень простой для описания, но асимптотически оптимальный алгоритм сортировки O ( n log n ). Точно так же многие алгоритмы вычислительной геометрии используют вариации самобалансирующихся BST для решения таких проблем, как проблема пересечения отрезков линии и определение местоположения точки.проблема эффективно. (Для среднего случая производительность, однако, самоуравновешенная BSTs может быть менее эффективной , чем другие решения. Бинарное дерево рода, в частности, скорее всего, будут медленнее , чем сортировка слияния , быстрая сортировки или пирамидальная сортировки , из - за дерево балансировки накладных расходов , как а также шаблоны доступа к кешу .)
Самобалансирующиеся BST - это гибкие структуры данных, которые легко расширять для эффективной записи дополнительной информации или выполнения новых операций. Например, можно записать количество узлов в каждом поддереве, имеющем определенное свойство, что позволяет подсчитать количество узлов в определенном ключевом диапазоне с этим свойством за время O (log n ). Эти расширения можно использовать, например, для оптимизации запросов к базе данных или других алгоритмов обработки списков.
См. Также
- Структура данных поиска
- Алгоритм Дэй – Стаута – Уоррена
- Дерево слияния
- Пропустить список
- Сортировка
Ссылки
- ^ a b c Дональд Кнут . Искусство программирования , Том 3: Сортировка и поиск , второе издание. Аддисон-Уэсли, 1998. ISBN 0-201-89685-0 . Раздел 6.2.3: Сбалансированные деревья, стр. 458–481.
- ^ Пол Э. Блэк , «красно-черное дерево», в Словаре алгоритмов и структур данных [онлайн], Вреда Питерс и Пол Э. Блэк, ред. 13 апреля 2015 г. (по состоянию на 3 октября 2016 г.) Доступно по адресу : https://xlinux.nist.gov/dads/HTML/redblack.html
Внешние ссылки
- Словарь алгоритмов и структур данных: сбалансированное по высоте двоичное дерево поиска
- GNU libavl , библиотека реализаций двоичного дерева на C под лицензией LGPL, с документацией
