В информатике самобалансирующееся двоичное дерево поиска (BST) — это любое двоичное дерево поиска на основе узлов , которое автоматически сохраняет свою высоту (максимальное число уровней ниже корня) небольшой при произвольных вставках и удалениях элементов. [1] Эти операции, разработанные для самобалансирующегося двоичного дерева поиска, содержат меры предосторожности против безграничного увеличения высоты дерева, так что эти абстрактные структуры данных получают атрибут «самобалансирующиеся».
Для сбалансированных по высоте бинарных деревьев высота определяется как логарифмическая по количеству элементов. Это касается многих бинарных деревьев поиска, таких как деревья AVL и красно-черные деревья . Расходящиеся деревья и древовидные деревья являются самобалансирующимися, но не сбалансированными по высоте, поскольку их высота не гарантированно логарифмическая по количеству элементов.
Самобалансирующиеся двоичные деревья поиска обеспечивают эффективную реализацию изменяемыми упорядоченными списками и могут использоваться для других абстрактных структур данных, таких как ассоциативные массивы , приоритетные очереди и наборы .
Большинство операций на бинарном дереве поиска (BST) занимают время, прямо пропорциональное высоте дерева, поэтому желательно, чтобы высота была небольшой. Бинарное дерево высотой h может содержать не более 2 0 +2 1 +···+2 h = 2 h +1 −1 узлов. Из этого следует, что для любого дерева с n узлами и высотой h :
И это подразумевает:
Другими словами, минимальная высота двоичного дерева с n узлами равна log 2 ( n ), округленному вниз ; то есть . [1]
Однако простейшие алгоритмы для вставки элементов BST могут давать дерево высотой n в довольно распространенных ситуациях. Например, когда элементы вставляются в порядке сортировки ключей , дерево вырождается в связанный список с n узлами. Разница в производительности между двумя ситуациями может быть огромной: например, когда n = 1 000 000, минимальная высота составляет .
Если элементы данных известны заранее, высоту можно поддерживать небольшой, в среднем смысле, добавляя значения в случайном порядке, что приводит к случайному бинарному дереву поиска . Однако существует множество ситуаций (например, онлайн-алгоритмы ), где эта рандомизация нежизнеспособна.
Самобалансирующиеся бинарные деревья решают эту проблему, выполняя преобразования на дереве (например, повороты дерева ) во время вставки ключа, чтобы сохранить высоту пропорциональной log 2 ( n ). Хотя определенные накладные расходы присутствуют, они не превышают всегда необходимую стоимость поиска и могут быть оправданы, гарантируя быстрое выполнение всех операций.
Хотя можно поддерживать BST с минимальной высотой с ожидаемым временем операций (поиск/вставка/удаление), дополнительные требования к пространству, необходимые для поддержания такой структуры, как правило, перевешивают уменьшение времени поиска. Для сравнения, AVL-дерево гарантированно будет находиться в пределах 1,44 от оптимальной высоты, требуя при этом всего два дополнительных бита памяти в наивной реализации. [1] Поэтому большинство самобалансирующихся алгоритмов BST поддерживают высоту в пределах постоянного множителя этой нижней границы.
В асимптотическом (« большом О ») смысле самобалансирующаяся структура BST, содержащая n элементов, позволяет выполнять поиск, вставку и удаление элемента в худшем случае и упорядоченное перечисление всех элементов во времени. Для некоторых реализаций это временные ограничения на операцию, в то время как для других это амортизированные ограничения на последовательность операций. Эти времена являются асимптотически оптимальными среди всех структур данных, которые манипулируют ключом только посредством сравнений.
Структуры данных, реализующие этот тип дерева, включают:
Самобалансирующиеся бинарные деревья поиска могут использоваться естественным образом для построения и поддержания упорядоченных списков, таких как очереди приоритетов . Их также можно использовать для ассоциативных массивов ; пары ключ-значение просто вставляются с упорядочением, основанным только на ключе. В этом качестве самобалансирующиеся BST имеют ряд преимуществ и недостатков по сравнению со своим основным конкурентом, хэш-таблицами . Одним из преимуществ самобалансирующихся BST является то, что они позволяют быстро (действительно, асимптотически оптимально) перечислять элементы в ключевом порядке , чего не обеспечивают хэш-таблицы. Одним из недостатков является то, что их алгоритмы поиска становятся более сложными, когда может быть несколько элементов с одним и тем же ключом. Самобалансирующиеся BST имеют лучшую производительность поиска в худшем случае, чем большинство [2] хэш-таблиц ( по сравнению с ), но имеют худшую производительность в среднем случае ( по сравнению с ).
Самобалансирующиеся BST могут использоваться для реализации любого алгоритма, требующего изменяемых упорядоченных списков, для достижения оптимальной асимптотической производительности в худшем случае. Например, если двоичная сортировка дерева реализована с самобалансирующимся BST, мы имеем очень простой в описании, но асимптотически оптимальный алгоритм сортировки. Аналогично, многие алгоритмы в вычислительной геометрии используют вариации самобалансирующихся BST для эффективного решения таких задач, как проблема пересечения отрезков линии и проблема расположения точек . (Однако для производительности в среднем случае самобалансирующиеся BST могут быть менее эффективными, чем другие решения. В частности, двоичная сортировка дерева, вероятно, будет медленнее, чем сортировка слиянием , быстрая сортировка или пирамидальная сортировка , из-за накладных расходов на балансировку дерева, а также шаблонов доступа к кэшу .)
Самобалансирующиеся BST-деревья являются гибкими структурами данных, поскольку их легко расширить для эффективной записи дополнительной информации или выполнения новых операций. Например, можно записать количество узлов в каждом поддереве, имеющем определенное свойство, что позволяет со временем подсчитать количество узлов в определенном диапазоне ключей с этим свойством . Такие расширения можно использовать, например, для оптимизации запросов к базе данных или других алгоритмов обработки списков.
