AVL-дерево - приближенно сбалансированное дерево

AVL-дерево - это бинарное дерево, которое обладает следующими свойствами.

1. Его левое и правое поддеревья отличаются по высоте не больше чем на 1.

2. Оба поддерева являются AVL-деревьями.

Это определение допускает возможность формирования немного несбалансированных деревьев. Можно показать, что высота AVL-дереэа всегда грубо пропорциональна log п, где л — количество узлов в дереве (даже в худшем случае). Это позволяет гарантировать эффективность операций In, add и del, пропорциональную логарифму количества элементов.

Операции с AVL-словарями аналогичны операциям с бинарными словарями, если не считать некоторых дополнений, позволяющих поддерживать приблизительную сбалансированность дерева. Если дерево выходит из состояния приблизительной сбалансированности после вставки или удаления элемента, то некоторый дополнительный механизм снова восстанавливает требуемую степень сбалансированности. Для эффективной реализации этого механизма необходимо сопровождать определенную информацию о сбалансированности дерева. По сути требуется знать только разницу между высотами поддеревьев дерева, которая может быть равна -1, 0 или +1. Но для упрощения выполняемых операций желательно сопровождать информацию о полной высоте деревьев, а не только о разнице высот.

Определим отношение вставки следующим образом: addavli Tree, X, NewTree)

где и Tree, и MewTree — AVL-словари, такие, что дерево NewTree представляет собой дерево Tree со вставленным элементом X AVL-деревья будут представлены с помощью термов в следующей форме: t(Left, a. Right) /Height

Глава 10. Усовершенствованные методы представления деревьев 221

где А — корень, Left и Right — поддеревья, a Height — высота дерева. Пустое дерево представлено в виде nil/0. Теперь рассмотрим операцию вставки элемента X в непустой AVL-словарь, как показано ниже. Tree = t(L, A, Ю/Н

Начнем описание с изучения только того варианта, в котором X больше А. После этого вставим X в дерево К и получим следующее отношение: addsvl(R, X, t(R1, В, R2)/НЬ)

На рис. 10.6 показаны следующие компоненты, из которых должно быть создано дерево NewTree:

L, A, R1, В, R2

[ h + 2

h-1 возможные addavi(R,X,t(ni,B,R2J/Hb)

h ) значения

h+ 1 высоты Ft

A^eA^sA

h h-Z h-2

h-1 h-1

h h

h+1 h+l

Рис. 10.6. Решение задачи вставки элемента в AVL-depeaor a) AVL-дерево перед вставкой X, X > А; 6),WL дерево после вставки X в дерево ■: в) компоненты, из которых должно быть сформировано новое дерево

Каковыми могут быть значения высоты L, R, R1 и R2? Деревья L и В могут отличаться по высоте не больше чем на 1. На рис. 10.6 показано, какими могут быть значения высоты деревьев R1 и R2. Поскольку в дерево R вставлен только один элемент, X, то не более чем одно из поддеревьев (? 1 или R2) может иметь высоту h+ 1.

В том случае, если X меньше А, ситуация является аналогичной, за исключением того, что левое и правое поддеревья меняются местами. Поэтому в любом случае необходимо сформировать дерево NewTre< из трех деревьев (назовем их Tree!, Tree2 и ТгееЗ) и двух отдельных элементов, А и В. Теперь рассмотрим вопрос о том, как объединить эти пять компонентов, чтобы сформировать дерево NewTree, представляющее собой AVL-словарь. Порядок компонентов в дереве NewTree слева направо должен быть следующим; Treel, А, 1гее2, В, ТгееЗ

Необходимо рассмотреть следующие варианты.

1. Среднее дерево, Тгее2, является более высоким, чем оба других дерева.

2. Дерево Treel является, по меньшей мере, таким же высоким, как деревья Тгее2 и ТгееЗ.

3. Дерево ТгееЗ является, по меньшей мере, таким же высоким, как деревья Тгее2 и Treel.

222 Часть I. Язык Prolog

На рис. 10.7 показано, как можно сформировать дерево NewTree в каждом из этих вариантов. В варианте 1 среднее дерево (Тгее2) необходимо разделить на части и включить их в дерево NewTree. Три правила, которые приведены на рис. 10.7, можно легко перевести на язык Prolog в виде следующего отношения: combine[ Treel, A, Tree2_r В, ТгееЗ, NewTree)

Правит ГН2>Н1 иН2>НЗ

Правило 2. HI;: Н2 и Н1;: НЗ

на

тз н?