Реализация АВЛ–деревьев через классы объектно–ориентированного программирования
Министерство образования и науки Украины
Запорожская государственная инженерная академия
Кафедра программного обеспечения автоматизированных систем
КУРСОВАЯ РАБОТА
По дисциплине «Объектно – ориентированное программирование »
На тему: «Реализация АВЛ – деревьев через классы объектно – ориентированного программирования»
Выполнил: ст. гр. СП – 07 – 1з Воронько О.А.
Проверил: Попивщий В.И.
Запорожье, 2009г.
ПЛАН
Введение
1. Основные термины
2. Основные операции с АВЛ - деревьями
3. Алгоритм реализации АВЛ – деревьев через классы объектно – ориентированного программирования
Список литературы
ВВЕДЕНИЕ
Язык программирования С++ является одним из наиболее популярных средств объектно – ориентированного программирования, позволяющим разрабатывать программы, эффективные по объему кода и скорости выполнения. С++ включает большое число операций и типов данных, средства управления вычислительными процессами, механизмы модификации типов данных и методы их обработки и, как следствие, является мощным языком программирования. Он позволяет описывать процессы обработки информации, начиная с уровня отдельных разрядов, видов и адресов памяти, переходя на основе механизмов объектно – ориентированного программирования к близким конкретным предметным областям понятиям.
Первые программы для цифровых вычислительных машин редко превышали объем 1 кбайт. Объемы используемых программ и программных систем измеряются не только десятками килобайтов, но и сотнями мегабайтов. Вместе с тем удельная стоимость создания программ (нормированная объемом программы) до последнего времени менялась мало. Более того, с ростом объема программы удельная стоимость ее создания могла нелинейно возрастать. Поэтому не удивительно, что одним из основных факторов, определяющих развитие технологии программирования, является снижение стоимости проектирования и создания программных продуктов (ПП), или борьба со сложностью программирования.
Другими важнейшими факторами, влияющими на эволюцию методов проектирования и создания ПП, являются:
изменение архитектур вычислительных средств (ВС) в интересах повышения производительности, надежности и коммуникативности;
упрощение взаимодействия пользователей с ВС и интеллектуализация ВС.
Действие двух последних факторов, как правило, сопряжено с ростом сложности программного обеспечения ВС. Сложность представляет неотъемлемое свойство программирования и программ, которое проявляется во времени и стоимости создания программ, в объеме или длине текста программы, характеристиках ее логической структуры, задаваемой операторами передачи управления (ветвления, циклы, вызовы подпрограмм и др.).
Можно выделить 5 следующих источников сложности программирования:
1) решаемая задача;
2) язык программирования;
3) среда выполнения программы;
4) технологический процесс коллективной разработки и создания ПП;
5) стремление к универсальности и эффективности алгоритмов и типов данных.
От свойства сложности нельзя избавиться, но можно изменять характеристики его проявления путем управления или организации.
В программировании широко используется фундаментальный принцип управления сложными системами, который известен человеку с глубокой древности – devide et impera (разделяй и властвуй, лат.) и широко им применяется при разработке и проектировании любых сложных технических систем.
В настоящее время объектно – ориентированное программирование (ООП) является доминирующим стилем при создании больших программ.
1. ОСНОВНЫЕ ТЕРМИНЫ
Так исторически сложилось, что у этих деревьев есть два альтернативных названия: АВЛ - деревья и сбалансированные деревья. АВЛ произошло от фамилий изобретателей.
Идеально сбалансированным называется дерево, у которого для каждой вершины выполняется требование: число вершин в левом и правом поддеревьях различается не более, чем на 1. Однако идеальную сбалансированность довольно трудно поддерживать.
В некоторых случаях при добавлении/удалении может потребоваться значительная перестройка дерева, не гарантирующая логарифмической сложности. Поэтому Г.М. Адельсон - Вельский и Е.М. Ландис ввели менее строгое определение сбалансированности и доказали, что при таком определении можно написать программы добавления/удаления, имеющие логарифмическую сложность и сохраняющие дерево сбалансированным.
Дерево считается сбалансированным по АВЛ (в дальнейшем просто «сбалансированным»), если для каждой вершины выполняется требование: высота левого и правого поддеревьев различаются не более, чем на 1. Не всякое сбалансированное дерево идеально сбалансировано, но всякое идеально сбалансированное дерево сбалансировано.
Бинарные деревья поиска предназначены для быстрого доступа к данным. В идеале разумно сбалансированное дерево имеет высоту порядка O(log2n). Однако при некотором стечении обстоятельств дерево может оказаться вырожденным. Тогда высота его будет O(n), и доступ к данным существенно замедлится. Рассмотрим модифицированный класс деревьев, обладающих всеми преимуществами бинарных деревьев поиска и никогда не вырождающихся. Они называются сбалансированными или АВЛ - деревьями. Под сбалансированностью будем понимать то, что для каждого узла дерева высоты обоих его поддеревьев различаются не более чем на 1.
Строго говоря, этот критерий нужно называть АВЛ - сбалансированностью в отличие от идеальной сбалансированности, когда для каждого узла дерева количества узлов в левом и правом поддеревьях различаются не более чем на 1. Здесь мы всегда будем иметь в виду АВЛ - сбалансированность.
Новые методы вставки и удаления в классе АВЛ - деревьев гарантируют, что все узлы останутся сбалансированными по высоте. На рисунках 1 и 2 показаны эквивалентные представления массива АВЛ - деревом и бинарным деревом поиска. Рисунок 1 представляет простой пятиэлементный массив А (A[5] = {1,2,3,4,5}), отсортированный по возрастанию. Рисунок 2 представляет массив B (B[8] = {20, 30, 80, 40, 10, 60, 50, 70}).
Бинарное дерево поиска имеет высоту 5, в то время как высота АВЛ - дерева равна 2. В общем случае высота сбалансированного дерева не превышает O(log2n). Таким образом, АВЛ - дерево является мощной структурой хранения, обеспечивающей быстрый доступ к данным.
Для этого используем подход, при котором поисковое дерево строится отдельно от своих узлов. Сначала разрабатываем класс AVLTreeNode, а затем используем объекты этого типа для конструирования класса AVLTree. Предметом пристального внимания будут методы Insert и Delete.
Они требуют тщательного проектирования, поскольку должны гарантировать, что все узлы нового дерева останутся сбалансированными по высоте.
2. ОСНОВНЫЕ ОПЕРАЦИИ С АВЛ - ДЕРЕВЬЯМИ
Восстановление сбалансированности.
Пусть имеется дерево, сбалансированное всюду, кроме корня, а в корне показатель сбалансированности по модулю равен 2 - м. Такое дерево можно сбалансировать с помощью одного из четырех вращений. При этом высота дерева может уменьшиться на 1. Для восстановления баланса после удаления/добавления вершины надо пройти путь от места удаления/добавления до корня дерева, проводя при необходимости перебалансировку и изменение показателя сбалансированности вершин вдоль пути к корню.
Добавление элемента в сбалансированное дерево.
Алгоритм вставки нового элемента в сбалансированное дерево будет состоять из следующих трех основных шагов:
Поиск по дереву.
Вставка элемента в место, где закончился поиск, если элемент отсутствует.
Восстановление сбалансированности.
1 - ый и 2 - ый шаги необходимы для того, чтобы убедиться в отсутствии элемента в дереве, а также найти такое место вставки, чтобы после вставки дерево осталось упорядоченным.
3 - ий шаг представляет собой обратный проход по пути поиска: от места добавления к корню дерева. По мере продвижения по этому пути корректируются показатели сбалансированности проходимых вершин и производится балансировка там, где это необходимо. Добавление элемента в дерево никогда не требует более одного поворота.
Эффективность сортировки вставкой в АВЛ - дерево.
Ожидаемое число сравнений, необходимых для вставки узла в бинарное дерево поиска, равно O(log2n). Поскольку в дерево вставляется n элементов, средняя эффективность должна быть O(n log2n). Однако в худшем случае, когда исходный список отсортирован в обратном порядке, она составит O(n2). Соответствующее дерево поиска вырождается в связанный список. Покажем, что худший случай требует O(n2) сравнений. Первая вставка требует 0 сравнений. Вторая вставка - двух сравнений (одно с корнем и одно для определения того, в какое поддерево следует вставлять данное значение). Третья вставка требует трех сравнений, 4 - я четырех,..., n - я вставка требует n сравнений. Тогда общее число сравнений равно:
0 + 2 + 3 + ... + n = (1 + 2 + 3 + ... + n) - 1 = n(n + 1) / 2 - 1 = O(n2)
Для каждого узла дерева память должна выделяться динамически, поэтому худший случай не лучше, чем сортировка обменом.
Когда n случайных значений повторно вставляются в бинарное дерево поиска, можно ожидать, что дерево будет относительно сбалансированным. Наилучшим случаем является законченное бинарное дерево. Для этого случая можно оценить верхнюю границу, рассмотрев полное дерево глубиной d. На i-ом уровне (1≤i≤d) имеется 2i узлов. Поскольку для помещения узла на уровень i требуется i+1 сравнение, сортировка на полном дереве требует (i+1) * 2i сравнений для вставки всех элементов на уровень i.
Если вспомнить, что n = 2(d+1) - 1, то верхняя граница меры эффективности выражается следующим неравенством:

Таким образом, эффективность алгоритма в лучшем случае составит O(n log2n).
Удаление элемента из сбалансированного дерева.
Алгоритм удаления элемента из сбалансированного дерева будет выглядеть так:
Поиск по дереву.
Удаление элемента из дерева.
Восстановление сбалансированности дерева (обратный проход).
1 - ый и 2 - ый шаги необходимы, чтобы найти в дереве вершину, которая должна быть удалена.
3 - ий шаг представляет собой обратный проход от места, из которого взят элемент для замены удаляемого, или от места, из которого удален элемент, если в замене не было необходимости.
Операция удаления может потребовать перебалансировки всех вершин вдоль обратного пути к корню дерева, то есть порядка log(N) вершин.
Анализ операций над сбалансированным деревом.
Понятно, что в случае полного двоичного дерева мы получим сложность T(log(n)) (на каждом шаге размер дерева поиска будет сокращаться вдвое). Рассмотрим минимальное сбалансированное дерево (худший случай). Таким будет дерево, у которого для каждой вершины высота левого и правого поддеревьев различаются на 1. Для такого дерева можно записать следующую рекуррентную формулу для числа вершин (h – высота дерева):

Покажем, что h<log2(Nh). Для этого необходимо и достаточно показать, что 2h>Nh. Докажем последнее методом математической индукции.а) h=0: 20>N0=0; б) h=1: 21>N1=1; в) h>1: Пусть 2h-2>Nh-2 и 2h-1>Nh-1. Тогда 2h-2+2h-1>Nh-2+ Nh-1. И далее получаем 2h>1+2h-2+2h-1>1+Nh-2+ Nh-1=Nh, что и требовалось доказать.
Таким образом алгоритмы поиска/добавления/удаления элементов в сбалансированном дереве имеют сложность T(log(n)). Г.М. Адельсон -Вельский и Е.М. Ландис доказали теорему, согласно которой высота сбалансированного дерева никогда не превысит высоту идеально сбалансированного дерева более, чем на 45%.
Основные узлы АВЛ - деревьев.
АВЛ - деревья имеют структуру, похожую на бинарные деревья поиска. Все операции идентичны описанным для бинарных деревьев, за исключением методов Insert и Delete, которые должны постоянно отслеживать соотношение высот левого и правого поддеревьев узла. Для сохранения этой информации расширяем определение объекта TreeNode, включив поле balanceFactor (показатель сбалансированности), которое содержит разность высот правого и левого поддеревьев.
Left data balanceFactor right
AVLTreeNode
balanceFactor = height(right subtree) - height(left subtree)
Если balanceFactor отрицателен, то узел «перевешивает влево», так как высота левого поддерева больше, чем высота правого поддерева. При положительном balanceFactor узел «перевешивает вправо». Сбалансированный по высоте узел имеет balanceFactor = 0.
В АВЛ - дереве показатель сбалансированности должен быть в диапазоне [-1, 1]. На рисунке 3 изображены АВЛ - деревья с пометками -1, 0 и +1 на каждом узле, показывающими относительный размер левого и правого поддеревьев.
-1: Высота левого поддерева на 1 больше высоты правого поддерева.
0: Высоты обоих поддеревьев одинаковы.
+1: Высота правого поддерева на 1 больше высоты левого поддерева.

Рис. 1.

Рис. 2.
Используя свойства наследования, можно образовать класс AVLTreeNode на базе класса TreeNode. Объект типа AVLTreeNode наследует поля из класса TreeNode и добавляет к ним поле balanceFactor. Данные - члены left и right класса TreeNode являются защищенными, поэтому AVLTreeNode или другие производные классы имеют к ним доступ.

Рис. 3.
Спецификация класса AVLTreeNode.
Объявление:
// наследник класса TreeNode
template <class T>
class AVLTreeNode: public TreeNode<T>
{
private:
// дополнительный член класса balanceFactor используется методами класса AVLTree и позволяет избегать "перевешивания" узлов
int balanceFactor;
AVLTreeNode<T>* & Left(void);
AVLTreeNode<T>* & Right(void);
public:
// конструктор
AVLTreeNode(const T& item, AVLTreeNode<T> *lptr = NULL,
AVLTreeNode<T> *rptr = NULL, int balfac = 0);
// возвратить левый/правый указатель узла типа TreeNode преобразовав его к типу AVLTreeNode
AVLTreeNode<T> *Left(void) const;
AVLTreeNode<T> *Right(void) const;
// метод для доступа к новому полю данных
int GetBalanceFactor(void);
// методы класса AVLTree должны иметь доступ к Left и Right
friend class AVLTree<T>;
};
Описание:
Элемент данных balanceFactor является скрытым, так как обновлять его должны только выравнивающие баланс операции вставки и удаления. Доступ к полям - указателям осуществляется с помощью методов Left и Right. Новые определения для этих методов обязательны, поскольку они возвращают указатель на структуру AVLTreeNode.
Поскольку класс AVLTree образован на базе класса BinSTree, будем использовать деструктор базового класса и метод ClearList. Эти методы удаляют узлы с помощью оператора delete. В каждом случае указатель ссылается на объект типа AVLTreeNode, а не TreeNode. Так как деструктор базового класса TreeNode виртуальный, при вызове delete используется динамическое связывание и удаляется объект типа AVLTreeNode.
Пример:
Эта функция создает АВЛ - дерево, изображенное на рисунке 4. Каждому узлу присваивается показатель сбалансированности.

Рис. 4.
AVLTreeNode<char> *root; // корень АВЛ - дерева
void MakeAVLCharTree(AVLTreeNode<char>* &root)
{
AVLTreeNode<char> *a, *b, *c, *d, *e;
e = new AVLTreeNode<char>('E', NULL, NULL, 0);
d = new AVLTreeNode<char>('D', NULL, NULL, 0);
c = new AVLTreeNode<char>('C', e, NULL, -1);
b = new AVLTreeNode<char>('B', NULL, d, 1);
a = new AVLTreeNode<char>('A', b, c, 0);
root = a;
}
Реализация класса AVLTreeNode.
Конструктор класса AVLTreeNode вызывает конструктор базового класса и инициализирует balanceFactor.
// Конструктор инициализирует balanceFactor и базовый класс
// Начальные значения полей указателей по умолчанию, равные NULL
// инициализируют узел как лист
template <class T>
AVLTreeNode<T>::AVLTreeNode (const T& item,
AVLTreeNode<T> *lptr, AVLTreeNode<T> *rptr, int balfac):
TreeNode<T>(item, lptr, rptr), balanceFactor(balfac)
{}
Методы Left и Right в классе AVLTreeNode упрощают доступ к полям данных. При попытке обратиться к левому сыну с помощью метода Left базового класса возвращается указатель на объект типа TreeNode. Чтобы получить указатель на узел АВЛ - дерева, требуется преобразование типов.
Например:
AVLTreeNode<T> *p, *q;
q = p->Left(); // недопустимая операция
q = (AVLTreeNode<T> *)p->Left(); // необходимое приведение типа
Во избежание постоянного преобразования типа указателей мы определяем методы Left и Right для класса AVLTreeNode, возвращающие указатели на объекты типа AVLTreeNode.
template <class T>.
AVLTreeNode<T>* AVLTreeNode::Left(void)
{
return ((AVLTreeNode<T> *)left;
}
Класс AVLTree.
АВЛ - дерево представляет собой списковую структуру, похожую на бинарное дерево поиска, с одним дополнительным условием: дерево должно оставаться сбалансированным по высоте после каждой операции вставки или удаления. Поскольку АВЛ - дерево является расширенным бинарным деревом поиска, класс AVLTree строится на базе класса BinSTree и является его наследником.
Для выполнения АВЛ - условий следует изменить методы Insert и Delete. Кроме того, в производном классе определяются конструктор копирования и перегруженный оператор присвоения, так как мы строим дерево с большей узловой структурой.
Спецификация класса AVLTree.
Объявление:
// Значения показателя сбалансированности узла
const int leftheavy = - 1;
const int balanced = 0;
const int rightheavy = 1;
template <class T>
class AVLTree: public BinSTree<T>
{
private:
// выделение памяти
AVLTreeNode<T> *GetAVLTreeNode(const T& item,
AVLTreeNode<T> *lptr, AVLTreeNode<T> *rptr);
// используется конструктором копирования и оператором присваивания
AVLTreeNode<T> *CopyTree(AVLTreeNode<T> *t);
// используется методами Insert и Delete для восстановления АВЛ - условий после операций вставки/удаления
void SingleRotateLeft (AVLTreeNode<T>* &p);
void SingleRotateRight (AVLTreeNode<T>* &p);
void DoubleRotateLeft (AVLTreeNode<T>* &p);
void DoubleRotateRight (AVLTreeNode<T>* &p);
void UpdateLeftTree (AVLTreeNode<T>* &tree,
int &reviseBalanceFactor);
void UpdateRightTree (AVLTreeNode<T>* &tree,
int &reviseBalanceFactor);
// специальные версии методов Insert и Delete
void AVLInsert(AVLTreeNode<T>* &tree,
AVLTreeNode<T>* newNode, int &reviseBalanceFactor);
void AVLDelete(AVLTreeNode<T>* &tree,
AVLTreeNode<T>* newNode, int &reviseBalanceFactor);
public:
// конструкторы
AVLTree(void);
AVLTree(const AVLTree<T>& tree);
// оператор присваивания
AVLTree<T>& operator= (const AVLTree<T>& tree);
// стандартные методы обработки списков
virtual void Insert(const T& item);
virtual void Delete(const T& item);
};
Описание:
Константы leftheavy, balanced и rightheavy используются в операциях вставки/удаления для описания показателя сбалансированности узла. Метод GetAVLTreeNode управляет выделением памяти для экземпляра класса. По умолчанию balanceFactor нового узла равен нулю.


Рис. 5.
В этом классе заново определяется функция CopyTree для использования с конструктором копирования и перегруженным оператором присвоения. Несмотря на то, что алгоритм идентичен алгоритму для функции CopyTree класса BinSTree, новая версия корректно создает расширенные объекты типа AVLTreeNode при построении нового дерева.
Функции AVLInsert и AVLDelete реализуют методы Insert и Delete, соответственно. Они используют скрытые методы наподобие SingleRotateLeft. Открытые методы Insert и Delete объявлены виртуальными и подменяют соответствующие функции базового класса. Остальные операции наследуются от класса BinSTree.
Пример:
Код, приведенный ниже, создает деревья, приведенные на рисунке 5. После удаления из АВЛ - дерева (В) элемента 3 АВЛ - дерево принимает вид, изображенный на рисунке 5 (С). Цифра после двоеточия означает фактор сбалансированности.
AVLTree<int> avltree; // AVLTree - список целых чисел
BinSTree<int> bintree; // BinSTree - список целых чисел
for (int i=1; i<=5; i++)
{
bintree.Insert(i); // создать дерево А
avltree.Insert(i); // создать дерево В
}
avltree.Delete(3); // удалить 3 из АВЛ - дерева
// дерево (С) есть дерево (В) без удаленного узла 3.
Распределение памяти для AVLTree.
Класс AVLTree образован от класса BinSTree и наследует большинство его операций. Для создания расширенных объектов типа AVLTreeNode мы разработали отдельные методы выделения памяти и копирования.
// разместить в памяти объект типа AVLTreeNode, прервать программу если во время выделения памяти произошла ошибка
template <class T>
AVLTreeNode<T> *AVLTree<T>::GetAVLTreeNode(const T& item,
AVLTreeNode<T> *lptr, AVLTreeNode<T> *rptr)
{
AVLTreeNode<T> *p;
p = new AVLTreeNode<T> (item, lptr, rptr);
if (p == NULL)
{
cerr << "Ошибка выделения памяти!" << endl;
exit(1);
}
return p;
}
Для удаления узлов АВЛ - дерева достаточно методов базового класса. Метод DeleteTree из класса BinSTree задействует виртуальный деструктор класса TreeNode.
Метод Insert класса AVLTree.
Преимущество АВЛ - деревьев состоит в их сбалансированности, которая поддерживается соответствующими алгоритмами вставки/удаления. Опишем метод Insert для класса AVLTree. При реализации метода Insert для запоминания элемента используется рекурсивная функция AVLInsert. Сначала приведем код метода Insert на С++, а затем сосредоточим внимание на рекурсивном методе AVLInsert, реализующем алгоритм Адельсона - Вельского и Ландиса.
template <class T>
void AVLTree<T>::Insert(const T& item)
{
// объявить указатель АВЛ - дерева, используя метод базового класса GetRoot
// произвести приведение типов для указателей
AVLTreeNode<T> *treeRoot = (AVLTreeNode<T> *)GetRoot(),
*newNode;
// флаг, используемый функцией AVLInsert для перебалансировки узлов
int reviseBalanceFactor = 0;
// создать новый узел АВЛ - дерева с нулевыми полями указателей
newNode = GetAVLTreeNode(item, NULL, NULL);
// вызвать рекурсивную процедуру для фактической вставки элемента
AVLInsert(treeRoot, newNode, reviseBalancefactor);
// присвоить новые значения элементам данных базового класса
root = treeRoot;
current = newNode;
size++;
}
Ядром алгоритма вставки является рекурсивный метод AVLInsert. Как и его аналог в классе BinSTree, этот метод осуществляет прохождение левого поддерева, если item меньше данного узла, и правого поддерева, если item больше или равен данному узлу. При сканировании левого или правого поддерева некоторого узла анализируется флаг revisebalanceFactor, который является признаком изменения любого параметра balanceFactor в поддереве. Если он установлен, то нужно проверить, сохранилась ли АВЛ - сбалансированность всего дерева.
Если в результате вставки нового узла она оказалась нарушенной, то мы обязаны восстановить равновесие.
Алгоритм АВЛ – вставки
Процесс вставки почти такой же, что и для бинарного дерева поиска. Осуществляется рекурсивный спуск по левым и правым сыновьям, пока не встретится пустое поддерево, а затем производится пробная вставка нового узла в этом месте. В течение этого процесса мы посещаем каждый узел на пути поиска от корневого к новому элементу. Поскольку процесс рекурсивный, обработка узлов ведется в обратном порядке. При этом показатель сбалансированности родительского узла можно скорректировать после изучения эффекта от добавления нового элемента в одно из поддеревьев. Необходимость корректировки определяется для каждого узла, входящего в поисковый маршрут. Есть три возможных ситуации. В двух первых случаях узел сохраняет сбалансированность и реорганизация поддеревьев не требуется. Нужно лишь скорректировать показатель сбалансированности данного узла. В третьем случае разбалансировка дерева требует одинарного или двойного поворотов узлов.
Случай 1. Узел на поисковом маршруте изначально является сбалансированным (balanceFactor = 0). После вставки в поддерево нового элемента узел стал перевешивать влево или вправо в зависимости от того, в какое поддерево была произведена вставка.
Если элемент вставлен в левое поддерево, показателю сбалансированности присваивается -1, а если в правое, то 1. Например, на пути 40 - 50 - 60 каждый узел сбалансирован. После вставки узла 55 показатели сбалансированности изменяются (рис. 6).

Рис. 6.
Случай 2. Одно из поддеревьев узла перевешивает, и новый узел вставляется в более легкое поддерево. Узел становится сбалансированным. Сравните, например, состояния дерева до и после вставки узла 55 (рис. 7).
Случай 3. Одно из поддеревьев узла перевешивает, и новый узел помещается в более тяжелое поддерево. Тем самым нарушается условие сбалансированности, так как balanceFactor выходит за пределы -1..1. Чтобы восстановить равновесие, нужно выполнить поворот.

Рис. 7.
Рассмотрим пример:
Предположим, что дерево разбалансировалось слева и мы восстанавливаем равновесие, вызывая одну из функций поворота вправо. Разбалансировка справа влечет за собой симметричные действия. Сказанное иллюстрируется рисунком 8.
Метод AVLInsert.
Продвигаясь вдоль некоторого пути для вставки нового узла, рекурсивный метод AVLInsert распознает все три указанных выше случая корректировки. При нарушении условия сбалансированности восстановление равновесия осуществляется с помощью функций UpdateLeftTree и UpdateRightTree.
template <class T>
void AVLTree<T>::AVLInsert(AVLTreeNode<T>* &tree,
AVLTreeNode<T>* newNode, int &reviseBalanceFactor)
{
// флаг "Показатель сбалансированности был изменен"
int rebalanceCurrNode;
// встретилось пустое поддерево, пора вставлять новый узел
if (tree == NULL)
{
// вставить новый узел
tree = newNode;
// объявить новый узел сбалансированным
tree->balanceFactor = balanced;
// сообщить об изменении показателя сбалансированности
reviseBalanceFactor = 1;
}
// рекурсивно спускаться по левому поддереву, если новый узел меньше текущего
else if (newNode->data < tree->data)
{
AVLInsert(tree->Left(), newNode, rebalanceCurrNode);
// проверить, нужно ли корректировать balanceFactor
if (rebalanceCurrNode)
{
// вставка слева от узла, перевешивающего влево. будет нарушено
// условие сбалансированности; выполнить поворот (случай 3)
if (tree->balanceFactor == leftheavy)
UpdateLeftTree(tree, reviseBalanceFactor);
// вставка слева от сбалансированного узла.
// узел станет перевешивать влево (случай 1)
else if (tree->balanceFactor == balanced)
{
tree->balanceFactor = leftheavy;
reviseBalanceFactor = 1;
}
// вставка слева от узла, перевешивающего вправо
// узел станет сбалансированным (случай 2)
else
{
tree->balanceFactor = balanced;
reviseBalanceFactor = 0;
}
}
Else
// перебалансировка не требуется. не опрашивать предыдущие узлы
reviseBalanceFactor = 0;
}
// иначе рекурсивно спускаться по правому поддереву
else if (newNode->data < tree->data)
{
AVLInsert(tree->Right(), newNode, rebalanceCurrNode);
// проверить, нужно ли корректировать balanceFactor
if (rebalanceCurrNode)
{
// вставка справа от узла, перевешивающего вправо. будет нарушено
// условие сбалансированности; выполнить поворот (случай 3)
if (tree->balanceFactor == rightheavy)
UpdateRightTree(tree, reviseBalanceFactor);
// вставка справа от сбалансированного узла
// узел станет перевешивать вправо (случай 1)
else if (tree->balanceFactor == balanced)
{
tree->balanceFactor = rightheavy;
reviseBalanceFactor = 1;
}
// вставка справа от узла, перевешивающего влево
// узел станет сбалансированным (случай 2)
else
{
tree->balanceFactor = balanced;
reviseBalanceFactor = 0;
}
}
else
// перебалансировка не требуется. не опрашивать предыдущие узлы
reviseBalanceFactor = 0;
}

Рис. 8.
Метод AVLInsert распознает случай 3, когда нарушается АВЛ - условие. Для выполнения перебалансировки используются методы UpdateLeftTree и UpdateRightTree. Они выполняют одинарный или двойной поворот для уравновешивания узла, а затем сбрасывают флаг reviseBalanceFactor. Перед тем, как обсудить специфические детали поворотов, приведем код функции UpdateLeftTree.
template <class T>
void AVLTree<T>::UpdateLeftTree(AVLTreeNode<T>* &p,
int reviseBalanceFactor)
{
AVLTreeNode<T> *lc;
lc = p->Left();
// перевешивает левое поддерево?
if (lc->balanceFactor == leftheavy)
{
SingleRotateRight(p); // однократный поворот
reviseBalanceFactor = 0;
}
// перевешивает правое поддерево?
else if (lc->balanceFactor == rightheavy)
{
// выполнить двойной поворот
DoubleRotateRight(p);
// теперь корень уравновешен
reviseBalanceFactor = 0;
}
Вращения (Повороты) АВЛ - деревьев.
При операциях добавления и удаления может произойти нарушение сбалансированности дерева. В этом случае потребуются некоторые преобразования, не нарушающие упорядоченности дерева и способствующие лучшей сбалансированности.
Рассмотрим такие преобразования.
В каждой вершине дерева помимо значения элемента будем хранить показатель сбалансированности в данной вершине. Показатель сбалансированности - разница между высотами правого и левого поддеревьев.
PTree = ^TTree;
TTree = record
Item: T; {элемент дерева}
Left, Right: PTree; {указатели на поддеревья}
Balance: ShortInt; {показатель сбалансированности}
end;
В сбалансированном дереве показатели сбалансированности всех вершин лежат в пределах от -1 до 1. При операциях добавления/удаления могут появляться вершины с показателями сбалансированности -2 и 2.
Малое левое вращение.
Пусть показатель сбалансированности вершины, в которой произошло нарушение баланса, равен -2, а показатель сбалансированности корня левого поддерева равен -1. Тогда восстановить сбалансированность такого поддерева можно следующим преобразованием, называемым малым левым вращением (рис. 9.):

Рис. 9.
На приведенном рисунке прямоугольниками обозначены поддеревья. Рядом с поддеревьями указана их высота. Поддеревья помечены арабскими цифрами. Кружочками обозначены вершины. Цифра рядом с вершиной - показатель сбалансированности в данной вершине. Буква внутри кружка - условное обозначение вершины.