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

Self-balancing binary search tree
Пример неуравновешенный дерево; следование пути от корня к узлу занимает в среднем 3,27 обращений к узлу
То же дерево после уравновешивания по высоте; среднее усилие на пути уменьшилось до 3,00 обращений к узлам

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

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

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

Обзор

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

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

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

.

Другими словами, минимальная высота двоичного дерева с п узлы журнал2(п), округлено в меньшую сторону; это, .[1]

Однако простейшие алгоритмы вставки элементов BST могут дать дерево с высотой п в довольно распространенных ситуациях. Например, когда элементы вставляются в отсортированные ключ порядок, дерево вырождается в связанный список с участием п узлы. Разница в производительности между двумя ситуациями может быть огромной: например, когда п = 1000000, минимальная высота .

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

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

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

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

Реализации

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

Приложения

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

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

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

Смотрите также

использованная литература

  1. ^ а б c Дональд Кнут. Искусство программирования, Том 3: Сортировка и поиск, Второе издание. Аддисон-Уэсли, 1998. ISBN 0-201-89685-0. Раздел 6.2.3: Сбалансированные деревья, стр. 458–481.
  2. ^ Пол Э. Блэк, «красно-черное дерево», в Словаре алгоритмов и структур данных [онлайн], Вреда Питерс и Пол Э. Блэк, ред. 13 апреля 2015 г. (доступ 3 октября 2016 г.) Доступно с: https://xlinux.nist.gov/dads/HTML/redblack.html

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