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

Эта статья требует дополнительных ссылок для проверки . Пожалуйста, помогите улучшить эту статью , добавив цитаты из надежных источников . Материал, не полученный от источника, может быть оспорен и удален. Поиск источников:  «Самобалансирующееся двоичное дерево поиска»  -  новости  · газеты  · книги  · ученый  · JSTOR ( ноябрь 2010 г. ) ( Узнайте, как и когда удалить это сообщение-шаблон )

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

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

В информатике , самобалансировка (или высота сбалансировано ) бинарное дерево поиска является любым узел - бинарным дерево поиска , которая автоматически сохраняет свою высоту (максимальное число уровней ниже корня) малых в условиях произвольных вставок элементов и удалений. ^[1]

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

Красно-черное дерево , которое является типом самобалансирующегося бинарного дерева поиска, было названо симметричным бинарное B-дерево ^[2] и было переименовано , но все - таки можно спутать с родовым понятием самобалансирующегося бинарного дерева поиска , так как из инициалы.

Обзор [ править ]

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

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

${\ Displaystyle п \ Leq 2 ^ {ч + 1} -1}$

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

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

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

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

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

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

Хотя возможно поддерживать BST с минимальной высотой с ожидаемыми временными операциями (поиск / вставка / удаление), дополнительные требования к пространству, необходимые для поддержания такой структуры, как правило, перевешивают уменьшение времени поиска. Для сравнения: дерево AVL гарантированно находится в пределах 1,44 раз от оптимальной высоты, при этом в наивной реализации требуется только два дополнительных бита памяти. ^[1] Следовательно, большинство самобалансирующихся алгоритмов BST поддерживают высоту в пределах постоянного коэффициента этой нижней границы.${\ Displaystyle О (\ журнал п)}$

В асимптотическом смысле (« 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 ). Эти расширения можно использовать, например, для оптимизации запросов к базе данных или других алгоритмов обработки списков.

См. Также [ править ]

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

Ссылки [ править ]

Внешние ссылки [ править ]

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