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

hh

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 ;: НЗ

© ©

HI

на

тзн?

Правило3: НЗ >Н2 и H3j: HI © ©