Структуры данных и модели вычислений
АВЛ-деревья
АВЛ-балансировка по определению требует, чтобы для каждого узла высота его правого поддерева отличалась от высоты левого не более чем на единицу.
Пусть— минимальное число узлов в АВЛ-дереве высоты . Тогда,,, при .
Теорема.
Для любоговыполняется неравенство, где — положительный корень уравнения .
Доказательство.
Непосредственно проверяется базис индукции,. Предположим теперь, что при выполняется неравенство , и докажем его при . Действительно, . Докажем последнее в этой цепочке неравенство.
Пусть, тогда и, следовательно,. Получили противоречие .
Следствие.
Для любого АВЛ-дерева высоты с узлами выполняется соотношение, что обеспечивает "логарифмическую трудоемкость" выполнения основных операций с АВЛ-деревом.
Идея балансировки двоичных деревьев поиска принадлежит\linebreak Г.М.Адельсону-Вельскому и Е.М.Ландису, предложившим в 1962 г. класс сбалансированных деревьев, называемых с тех пор АВЛ-деревьями. Баланс поддерживается с помощью процедуры вращения. Для его восстановления в дереве с узлами после добавления или удаления узла может потребоватьсявращений.
Еще один класс деревьев поиска, называемых--деревьями, был предложен Дж. Хопкрофтом в 1970 г. Здесь баланс поддерживается за счет изменения степеней узлов. Обобщение--деревьев предложили Д.Байер и Е.Мак-Крейт. Их деревья называются Б-деревьями, которые мы рассмотрим в следующем разделе.
Красно-черные деревья предложил Д.Байер, назвав их симметричными двоичными Б-деревьями. Л.Гибас подробно изучил их свойства и предложил использовать для наглядности красный и черный цвета Посмотрите [7].
Из многих других вариаций на тему сбалансированных деревьев наиболее интересны расширяющиеся деревья, которые придумали Д.Слеатор и Р.Тарьян. Эти деревья являются саморегулирующимися. Хорошее описание расширяющихся деревьев дал Тарьян. Расширяющиеся деревья поддерживают баланс без использования дополнительных полей (типа цвета). Вместо этого расширяющие операции, включающие вращения, выполняются при каждом обращении к дереву. Учетная стоимость в расчете на одну операцию с деревом для расширяющихся деревьев составляет.
