Министерство образования и науки Украины
Запорожская государственная инженерная академия
Кафедра программного обеспечения автоматизированных систем
КУРСОВАЯ РАБОТА
По дисциплине «Объектно – ориентированное программирование »
На тему: «Реализация АВЛ – деревьев через классыобъектно – ориентированного программирования»
Выполнил: ст. гр. СП – 07 – 1з Воронько О.А.
Проверил: Попивщий В.И.
Запорожье, 2009г.
ПЛАН
Введение
1. Основныетермины
2.Основные операции с АВЛ — деревьями
3. Алгоритм реализации АВЛ – деревьевчерез классы объектно – ориентированного программирования
Списоклитературы
ВВЕДЕНИЕ
Язык программирования С++ является одним из наиболеепопулярных средств объектно – ориентированного программирования, позволяющимразрабатывать программы, эффективные по объему кода и скорости выполнения. С++включает большое число операций и типов данных, средства управлениявычислительными процессами, механизмы модификации типов данных и методы ихобработки и, как следствие, является мощным языком программирования. Онпозволяет описывать процессы обработки информации, начиная с уровня отдельныхразрядов, видов и адресов памяти, переходя на основе механизмов объектно –ориентированного программирования к близким конкретным предметным областямпонятиям.
Первые программы для цифровых вычислительных машин редкопревышали объем 1 кбайт. Объемы используемых программ и программных системизмеряются не только десятками килобайтов, но и сотнями мегабайтов. Вместе стем удельная стоимость создания программ (нормированная объемом программы) допоследнего времени менялась мало. Более того, с ростом объема программыудельная стоимость ее создания могла нелинейно возрастать. Поэтому неудивительно, что одним из основных факторов, определяющих развитие технологиипрограммирования, является снижение стоимости проектирования и созданияпрограммных продуктов (ПП), или борьба со сложностью программирования.
Другими важнейшими факторами, влияющими на эволюцию методовпроектирования и создания ПП, являются:
· изменениеархитектур вычислительных средств (ВС) в интересах повышенияпроизводительности, надежности и коммуникативности;
· упрощениевзаимодействия пользователей с ВС и интеллектуализация ВС.
Действие двух последних факторов, как правило, сопряжено сростом сложности программного обеспечения ВС. Сложность представляетнеотъемлемое свойство программирования и программ, которое проявляется вовремени и стоимости создания программ, в объеме или длине текста программы,характеристиках ее логической структуры, задаваемой операторами передачиуправления (ветвления, циклы, вызовы подпрограмм и др.).
Можно выделить 5 следующих источников сложностипрограммирования:
1) решаемая задача;
2) язык программирования;
3) среда выполнения программы;
4) технологический процесс коллективной разработки и созданияПП;
5) стремление к универсальности и эффективности алгоритмов итипов данных.
От свойства сложности нельзя избавиться, но можно изменятьхарактеристики его проявления путем управления или организации.
В программировании широко используется фундаментальныйпринцип управления сложными системами, который известен человеку с глубокойдревности – devideetimpera (разделяй и властвуй,лат.) и широко им применяется при разработке и проектировании любых сложныхтехнических систем.
В настоящее время объектно – ориентированное программирование(ООП) является доминирующим стилем при создании больших программ.
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. Восстановлениесбалансированности.
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. Восстановлениесбалансированности дерева (обратный проход).
1 — ый и 2 — ый шаги необходимы, чтобы найти в дереве вершину, котораядолжна быть удалена.
3 — ий шаг представляет собой обратный проход от места, из которого взятэлемент для замены удаляемого, или от места, из которого удален элемент, если взамене не было необходимости.
Операция удаления может потребовать перебалансировки всех вершин вдольобратного пути к корню дерева, то есть порядка log(N) вершин.
Анализ операций над сбалансированным деревом.
Понятно, что в случае полного двоичного дерева мы получим сложностьT(log(n)) (на каждом шаге размер дерева поиска будет сокращаться вдвое).Рассмотрим минимальное сбалансированное дерево (худший случай). Таким будетдерево, у которого для каждой вершины высота левого и правого поддеревьевразличаются на 1. Для такого дерева можно записать следующую рекуррентнуюформулу для числа вершин (h – высота дерева):
/>
Покажем, что hNh). Для этогонеобходимо и достаточно показать, что 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 AVLTreeNode: public TreeNode
{
private:
// дополнительный член класса balanceFactor используется методами классаAVLTree и позволяет избегать «перевешивания» узлов
intbalanceFactor;
AVLTreeNode* & Left(void);
AVLTreeNode* & Right(void);
public:
// конструктор
AVLTreeNode(const T& item, AVLTreeNode *lptr =NULL,
AVLTreeNode *rptr = NULL, int balfac = 0);
//возвратить левый/правый указатель узла типа TreeNode преобразовав его к типуAVLTreeNode
AVLTreeNode*Left(void) const;
AVLTreeNode *Right(void) const;
//метод для доступа к новому полю данных
int GetBalanceFactor(void);
// методы класса AVLTree должны иметь доступ к Left и Right
friendclass AVLTree;
};
Описание:
Элемент данных balanceFactor является скрытым, так как обновлять егодолжны только выравнивающие баланс операции вставки и удаления. Доступ к полям — указателям осуществляется с помощью методов Left и Right. Новые определения дляэтих методов обязательны, поскольку они возвращают указатель на структуруAVLTreeNode.
Поскольку класс AVLTree образован на базе класса BinSTree, будемиспользовать деструктор базового класса и метод ClearList. Эти методы удаляютузлы с помощью оператора delete. В каждом случае указатель ссылается на объекттипа AVLTreeNode, а не TreeNode. Так как деструктор базового класса TreeNodeвиртуальный, при вызове delete используется динамическое связывание и удаляетсяобъект типа AVLTreeNode.
Пример:
Эта функция создает АВЛ — дерево, изображенное на рисунке 4. Каждому узлуприсваивается показатель сбалансированности.
/>
Рис. 4.
AVLTreeNode *root; // корень АВЛ — дерева
void MakeAVLCharTree(AVLTreeNode* &root)
{
AVLTreeNode *a, *b, *c, *d, *e;
e = new AVLTreeNode('E', NULL, NULL, 0);
d = new AVLTreeNode('D', NULL, NULL, 0);
c = new AVLTreeNode('C', e, NULL, -1);
b = new AVLTreeNode('B', NULL, d, 1);
a = new AVLTreeNode('A', b, c, 0);
root= a;
}
Реализация класса AVLTreeNode.
Конструктор класса AVLTreeNode вызывает конструктор базового класса иинициализирует balanceFactor.
// Конструктор инициализирует balanceFactor и базовый класс
// Начальные значения полей указателей по умолчанию, равные NULL
// инициализируют узел как лист
template
AVLTreeNode::AVLTreeNode (const T& item,
AVLTreeNode *lptr, AVLTreeNode *rptr, intbalfac):
TreeNode(item, lptr, rptr), balanceFactor(balfac)
{}
Методы Left и Right в классе AVLTreeNode упрощают доступ к полям данных.При попытке обратиться к левому сыну с помощью метода Left базового классавозвращается указатель на объект типа TreeNode. Чтобы получить указатель наузел АВЛ — дерева, требуется преобразование типов.
Например:
AVLTreeNode *p, *q;
q = p->Left(); // недопустимая операция
q = (AVLTreeNode *)p->Left(); // необходимое приведение типа
Во избежание постоянного преобразования типа указателей мы определяемметоды Left и Right для класса AVLTreeNode, возвращающие указатели на объектытипа AVLTreeNode.
template .
AVLTreeNode* AVLTreeNode::Left(void)
{
return ((AVLTreeNode *)left;
}
КлассAVLTree.
АВЛ — дерево представляет собой списковую структуру, похожую на бинарноедерево поиска, с одним дополнительным условием: дерево должно оставатьсясбалансированным по высоте после каждой операции вставки или удаления. ПосколькуАВЛ — дерево является расширенным бинарным деревом поиска, класс AVLTreeстроится на базе класса BinSTree и является его наследником.
Для выполнения АВЛ — условий следует изменить методы Insert и Delete. Крометого, в производном классе определяются конструктор копирования и перегруженныйоператор присвоения, так как мы строим дерево с большей узловой структурой.
Спецификация класса AVLTree.
Объявление:
// Значения показателя сбалансированности узла
const int leftheavy = — 1;
const int balanced = 0;
const int rightheavy = 1;
template
class AVLTree: public BinSTree
{
private:
// выделение памяти
AVLTreeNode *GetAVLTreeNode(const T& item,
AVLTreeNode *lptr, AVLTreeNode *rptr);
//используется конструктором копирования и оператором присваивания
AVLTreeNode*CopyTree(AVLTreeNode *t);
//используется методами Insert и Delete для восстановления АВЛ — условий послеопераций вставки/удаления
voidSingleRotateLeft (AVLTreeNode* &p);
void SingleRotateRight (AVLTreeNode* &p);
void DoubleRotateLeft (AVLTreeNode* &p);
void DoubleRotateRight (AVLTreeNode* &p);
void UpdateLeftTree (AVLTreeNode* &tree,
int &reviseBalanceFactor);
void UpdateRightTree (AVLTreeNode* &tree,
int &reviseBalanceFactor);
// специальные версииметодов Insert и Delete
void AVLInsert(AVLTreeNode* &tree,
AVLTreeNode* newNode, int&reviseBalanceFactor);
void AVLDelete(AVLTreeNode* &tree,
AVLTreeNode* newNode, int&reviseBalanceFactor);
public:
// конструкторы
AVLTree(void);
AVLTree(const AVLTree& tree);
// оператор присваивания
AVLTree& operator= (const AVLTree&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 avltree; // AVLTree — списокцелых чисел
BinSTree bintree; // BinSTree — список целых чисел
for (int i=1; i
{
bintree.Insert(i); // создатьдерево А
avltree.Insert(i);// создать дерево В
}
avltree.Delete(3); // удалить 3 из АВЛ — дерева
// дерево (С) есть дерево (В) без удаленного узла 3.
Распределение памяти для AVLTree.
Класс AVLTree образован от класса BinSTree и наследует большинство егоопераций. Для создания расширенных объектов типа AVLTreeNode мы разработалиотдельные методы выделения памяти и копирования.
// разместить в памяти объект типа AVLTreeNode, прервать программу есливо время выделения памяти произошла ошибка
template
AVLTreeNode *AVLTree::GetAVLTreeNode(constT& item,
AVLTreeNode *lptr, AVLTreeNode *rptr)
{
AVLTreeNode *p;
p = new AVLTreeNode (item, lptr, rptr);
if (p== NULL)
{
cerr
exit(1);
}
return p;
}
Для удаления узлов АВЛ — дерева достаточно методов базового класса. МетодDeleteTree из класса BinSTree задействует виртуальный деструктор классаTreeNode.
Метод Insert класса AVLTree.
Преимущество АВЛ — деревьев состоит в их сбалансированности, котораяподдерживается соответствующими алгоритмами вставки/удаления. Опишем методInsert для класса AVLTree. При реализации метода Insert для запоминанияэлемента используется рекурсивная функция AVLInsert. Сначала приведем кодметода Insert на С++, а затем сосредоточим внимание на рекурсивном методеAVLInsert, реализующем алгоритм Адельсона — Вельского и Ландиса.
template
void AVLTree::Insert(const T& item)
{
// объявить указатель АВЛ — дерева, используя метод базового классаGetRoot
// произвести приведение типов для указателей
AVLTreeNode *treeRoot = (AVLTreeNode *)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
void AVLTree::AVLInsert(AVLTreeNode*&tree,
AVLTreeNode* newNode, int &reviseBalanceFactor)
{
// флаг «Показатель сбалансированности был изменен»
int rebalanceCurrNode;
// встретилось пустое поддерево, пора вставлять новый узел
if (tree == NULL)
{
// вставить новый узел
tree = newNode;
// объявить новый узел сбалансированным
tree->balanceFactor = balanced;
// сообщить об изменении показателя сбалансированности
reviseBalanceFactor = 1;
}
// рекурсивно спускаться по левому поддереву, если новый узел меньшетекущего
elseif (newNode->data data)
{
AVLInsert(tree->Left(), newNode, rebalanceCurrNode);
//проверить, нужно ли корректировать balanceFactor
if (rebalanceCurrNode)
{
// вставка слева от узла, перевешивающего влево. будет нарушено
// условие сбалансированности; выполнить поворот (случай 3)
if(tree->balanceFactor == leftheavy)
UpdateLeftTree(tree, reviseBalanceFactor);
//вставка слева от сбалансированного узла.
// узел станет перевешивать влево (случай 1)
elseif (tree->balanceFactor == balanced)
{
tree->balanceFactor = leftheavy;
reviseBalanceFactor = 1;
}
// вставка слева от узла, перевешивающего вправо
//узел станет сбалансированным (случай 2)
else
{
tree->balanceFactor = balanced;
reviseBalanceFactor = 0;
}
}
Else
// перебалансировка не требуется. не опрашивать предыдущие узлы
reviseBalanceFactor = 0;
}
// иначе рекурсивно спускаться по правому поддереву
elseif (newNode->data data)
{
AVLInsert(tree->Right(), newNode, rebalanceCurrNode);
//проверить, нужно ли корректировать balanceFactor
if (rebalanceCurrNode)
{
// вставка справа от узла, перевешивающего вправо. будет нарушено
// условие сбалансированности; выполнить поворот (случай 3)
if(tree->balanceFactor == rightheavy)
UpdateRightTree(tree, reviseBalanceFactor);
//вставка справа от сбалансированного узла
// узел станет перевешивать вправо (случай 1)
elseif (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
void AVLTree::UpdateLeftTree(AVLTreeNode*&p,
int reviseBalanceFactor)
{
AVLTreeNode *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.
На приведенном рисунке прямоугольниками обозначены поддеревья. Рядом споддеревьями указана их высота. Поддеревья помечены арабскими цифрами.Кружочками обозначены вершины. Цифра рядом с вершиной — показательсбалансированности в данной вершине. Буква внутри кружка — условное обозначениевершины. Как видно из рисунка после малого левого вращения показательсбалансированности вершины, в которой было нарушение баланса, становится равнымнулю.
Малое правое вращение.
В случае, когда показатель сбалансированности вершины, в которойпроизошло нарушение баланса, равен 2, а показатель сбалансированности корняправого поддерева равен 1, восстановить сбалансированность в вершине можно спомощью преобразования, называемого малым правым вращением. Это вращениесимметрично малому левому и схематично изображено на рисунке 10:
/>
Рис. 10.
Большое левое вращение.
Несколько сложнее случай, когда показатель сбалансированности в вершине,в которой произошло нарушение баланса равен -2, а показатель сбалансированностив корне левого поддерева равен 1 или 0. В этом случае применяетсяпреобразование, называемое большим левым вращением. Как видно из рисунка11 здесь во вращении участвуют три вершины, а не две как в случае малыхвращений.
/>
Рис. 11.
Большое правое вращение.
Большое правое вращение применяется, когда показатель сбалансированностивершины, в которой произошло нарушение баланса, равен 2, а показательсбалансированности корня правого поддерева равен -1 или 0. Большое правоевращение симметрично большому левому и схематично изображено на рисунке 12:
/>
Рис. 12.
Повороты необходимы, когда родительский узел P становится разбалансированным.Одинарный поворот вправо (single right rotation) происходит тогда, когдародительский узел P и его левый сын LC начинают перевешивать влево послевставки узла в позицию X. В результате такого поворота LC замещает своегородителя, который становится правым сыном. Бывшее правое поддерево узла LC (ST)присоединяется к P в качестве левого поддерева. Это сохраняет упорядоченность,так как узлы в ST больше или равны узлу LC, но меньше узла P. Поворотуравновешивает как родителя, так и его левого сына (рис. 13).
// выполнить поворот по часовой стрелке вокруг узла p
// сделать lc новой точкой вращения
template
void AVLTree::SingleRotateRight(AVLTreeNode* &p)
{
// левое, перевешивающее поддерево узла p
AVLTreeNode *lc;
// назначить lc левым поддеревом
lc = p->Left();
// скорректировать показатель сбалансированности для родительского узлаи его левого сына
p->balanceFactor= balanced;
lc->balanceFactor = balanced;
//правое поддерево узла lc в любом случае должно оставаться справа от lc,выполнить это условие, сделав st левым поддеревом узла p
p->Left() = lc->Right();
// переместить p в правое поддерево узла lc
// сделать lc новой точкой вращения
lc->Right() = p;
p =lc;
}
/>
Рис. 13
/>
Рис. 14.
Попытка вставить узел 5 в изображенное на рисунке 14 АВЛ — деревонарушает АВЛ — условие для узла 30. Одновременно левое поддерево узла 15 (LC)становится перегруженным.
Для переупорядочения узлов вызывается процедура SingleRotateRight. Врезультате родительский узел (30) становится сбалансированным, а узел 10перевешивающим влево. Двойной поворот вправо (double right rotation) нужентогда, когда родительский узел (P) становится перевешивающим влево, а его левыйсын (LC) перевешивающим вправо. NP – корень правого перевешивающего поддереваузла LC. Тогда в результате поворота узел NP замещает родительский узел. Нарисунках 15 и 16 показаны случаи вставки нового узла в качестве сына узла NP. Вобоих случаях NP становится родительским узлом, а бывший родитель P становитсяправым сыном NP.
На рисунке 15 мы видим сдвиг узла X1, после того как он был вставлен влевое поддерево узла NP. На рисунке 16 изображено перемещение узла X2 после еговставки в правое поддерево NP.
/>
Рис. 15.
/>
Рис. 16
// двойной поворот вправо вокруг узла p
template
void AVLTree::DoubleRotateRight(AVLTreeNode* &p)
{
// два поддерева, подлежащих повороту
AVLTreeNode *lc, *np;
// узел lc
lc = p->Left(); // левый сын узла p
np = lc->Right(); // правый сын узла lc
// обновить показатели сбалансированности в узлах p, lc и np
if(np->balanceFactor == rightheavy)
{
p->balanceFactor = balanced;
lc->balanceFactor = rightheavy;
}
else
{
p->balanceFactor = rightheavy;
lc->balanceFactor = balanced;
}
np->balanceFactor = balanced;
//перед тем как заменить родительский узел p, следует отсоединить его от старыхдетей и присоединить к новым
lc->Right()= np->Left();
np->Left() = lc;
p->Left() = np->Right();
np->Right() = p;
p =np;
}
Двойной поворот иллюстрируется на дереве, изображенном на рисунке 17.Попытка вставить узел 25 разбалансирует корневой узел 50. В этом случае узел 20(LC) приобретает слишком высокое правое поддерево и требуется двойной поворот.
Новым родительским узлом (NP) становится узел 40. Старый родительскийузел становится его правым сыном и присоединяет к себе узел 45, который такжепереходит с левой стороны дерева.
/>
Рис. 17.
Оценка сбалансированных АВЛ — деревьев.
Обоснованность применения АВЛ — деревьев неоднозначна, поскольку онитребуют дополнительных затрат на поддержание сбалансированности при вставке илиудалении узлов. Если в дереве постоянно происходят вставки и удаленияэлементов, эти операции могут значительно снизить быстродействие.
С другой стороны, если ваши данные превращают бинарное дерево поиска ввырожденное, вы теряете поисковую эффективность и вынуждены использовать АВЛ — дерево.В большинстве случаев в программах используются алгоритмы, когда сначалазаполняется список, а потом производится поиск по этому списку с небольшимколичеством изменений. Поэтому на практике использование АВЛ — деревьевпредпочтительно.
Для АВЛ — дерева не существует наихудшего случая, так как оно являетсяпочти полным бинарным деревом. Сложность операции поиска составляет O(log2n).Опыт показывает, что повороты требуются примерно в половине случаев вставок иудалений. Сложность балансировки обусловливает применение АВЛ — деревьев толькотам, где поиск является доминирующей операцией.
Оценка производительности АВЛ – деревьев.
Эта программа сравнивает сбалансированное и обычное бинарные деревьяпоиска, каждое из которых содержит N случайных чисел. Исходные данные для этихдеревьев берутся из единого массива. Для каждого элемента массиваосуществляется его поиск в обоих деревьях. Длины поисковых путей суммируются, азатем подсчитывается средняя длина поиска по каждому дереву. Программапрогоняется на 1000- и на 10000-элементном массивах.
Обратите внимание, что на случайных данных поисковые характеристики АВЛ — дерева несколько лучше. В самом худшем случае вырожденное дерево поиска,содержащее 1000 элементов, имеет среднюю глубину 500, в то время как средняяглубина АВЛ — дерева всегда равна 9.
#include
#include «bstree.h»
#include «avltree.h»
#include «random.h»
// загрузить из массива числа в бинарное поисковое дерево и АВЛ – дерево
void SetupLists(BinSTree &Tree1,AVLTree &Tree2, int A[], int n)
{
int i;
RandomNumber rnd;
// запомнить случайное число в массиве А, а также вставить его вбинарное дерево поиска и в АВЛ — дерево
for(i=0; i
{
A[i] = rnd.Random(1000);
Tree1.Insert(A[i]);
Tree2.Insert(A[i]);
}
// поиск элемента item в дереве t
// при этом накапливается суммарная длина поиска
template
void PathLength(TreeNode *t, long &totallength,int item)
{
// возврат, если элемент найден или отсутствует в списке
if (t== NULL || t->data == item)
return;
else
{
// перейти на следующий уровень, увеличить суммарную длину пути поиска
totallength++;
if (item data)
PathLength(t->Left(), totallength, item);
else
PathLength(t->Right(), totallength, item);
}
void main(void);
{
// переменные для деревьев и массива
BinSTreebinTree;
AVLTree avlTree;
int*A;
// суммарные длины поисковых путей элементов массива в бинарном деревепоиска и в АВЛ — дереве
longtotalLengthBintree = 0, totalLengthAVLTree = 0;
int n, i;
cout
cin >> n;
// загрузить случайными числами массив и оба дерева
SetupLists(binTree,avlTree, A, n);
for (i=0; i
{
PathLength(binTree.GetRoot(), totalLengthBintree, A[i]);
PathLength((TreeNode *)avlTree.getRoot(),
totalLengthAVLTree,A[i]);
}
cout
cout
}
Прогон 1:Сколько узлов на дереве? 1000
Средняя длина поиска для бинарного дерева = 10.256.
Средняя длина поиска для сбалансированного дерева = 7.901.
Прогон 2: Сколько узлов на дереве? 10000
Средняя длина поиска для бинарного дерева = 12.2822.
Средняя длина поиска для сбалансированного дерева = 8.5632.
Итераторы АВЛ — деревьев.
Сканирование узлов дерева более сложно, чем сканирование массивов ипоследовательных списков, так как дерево является нелинейной структурой исуществует несколько способов прохождения дерева. Проблема каждого из нихсостоит в том, что до завершения рекурсивного процесса из него невозможновыйти. Нельзя остановить сканирование, проверить содержимое узла, выполнитькакие-нибудь операции с данными, а затем вновь продолжить сканирование соследующего узла дерева.
Используя же итератор, клиент получает средство сканирования узловдерева, как если бы они представляли собой линейный список, без обременительныхдеталей алгоритмов прохождения, лежащих в основе процесса. Наш класс используеткласс Stack и наследуется от базового класса итератора. Поэтому сначала опишемкласс Stack и базовый класс итератора.
Спецификация класса Stack.
Объявление:
#include
#include
const int MaxStackSize = 50;
class Stack
{
private:
DataType stacklist[MaxStackSize];
int top;
public:
// конструктор; инициализирует вершину
Stack(void);
// операции модификации стека
void Push(const DataType& item);
DataType Pop(void);
void ClearStack(void);
// доступ к стеку
DataTypePeek(void) const;
// методы проверки состояния стека
int StackEmpty(void) const;
int StackFull(void) const; // для реализации, основанной на массиве
};
Описание:
Данные в стеке имеют тип DataType, который должен определяться сиспользованием оператора typedef. Пользователь должен проверять, полный листек, перед попыткой поместить в него элемент и проверять, не пустой ли стек,перед извлечением данных из него. Если предусловия для операции push или pop неудовлетворяются, печатается сообщение об ошибке и программа завершается. StackEmptyвозвращает TRUE, если стек пустой, и FALSE — в противном случае. ИспользуйтеStackEmpty, чтобы определить, может ли выполняться операция Pop.
StackFull возвращает TRUE, если стек полный, и FALSE — в противномслучае. Используйте StackFull, чтобы определить, может ли выполняться операцияPush. ClearStack делает стек пустым, устанавливая top = -1. Этот методпозволяет использовать стек для других целей.
Реализация класса Stack.
Конструктор Stack присваивает индексу top значение -1, что эквивалентноусловию пустого стека.
//инициализация вершины стека
Stack::Stack (void): top(-l)
{ }
Операции стека.
Две основные операции стека вставляют (Push) и удаляют (Pop) элемент изстека. Класс содержит функцию Peek, позволяющую получать данные элемента,находящегося в вершине стека, не удаляя в действительности этот элемент. Припомещении элемента в стек, top увеличивается на 1, и новый элемент вставляетсяв конец массива stacklist. Попытка добавить элемент в полный стек приведет ксообщению об ошибке и завершению программы.
// поместить элементв стек
void Stack::Push (const DataTypes item)
{
// если стек полный, завершить выполнение программы
if(top == MaxStackSize-1)
{
cerr
exit(l);
}
// увеличить индекс top и копировать item в массив stacklist
top++;
stacklist[top] = item;
}
Операция Pop извлекает элемент из стека, копируя сначала значение извершины стека в локальную переменную temp и затем увеличивая top на 1.Переменная temp становится возвращаемым значением. Попытка извлечь элемент изпустого стека приводит к сообщению об ошибке и завершению программы.
// взять элемент из стека
DataType Stack::Pop (void)
DataType temp;
// стек пуст, завершить программу
if (top == -1)
{
cerr
exit(1);
}
// считать элемент в вершине стека
temp = stacklist[top];
// уменьшить top и возвратить значение из вершины стека
top--;
return temp;
}
Операция Peek в основном дублирует определение Pop с единственным важнымисключением. Индекс top не уменьшается, оставляя стек нетронутым.
// возвратить данные в вершине стека
DataType Stack::Peek (void) const
{
// если стек пуст, завершить программу
if (top == -1)
{
cerr
exit(l);
}
return stacklist[top];
}
Условия тестирования стека.
Во время своего выполнения операции стека завершают программу припопытках клиента обращаться к стеку неправильно; например, когда мы пытаемсявыполнить операцию Peek над пустым стеком. Для защиты целостности стека класспредусматривает операции тестирования состояния стека. Функция StackEmptyпроверяет, является ли top равным -1. Если — да, стек пуст и возвращаемоезначение — TRUE; иначе возвращаемое значение — FALSE.
// тестирование стека на наличие в нем данных
int Stack::StackEmpty(void) const
{
returntop == -1;
}
Функция StackFull проверяет, равен ли top значению MaxStackSize — 1. Еслитак, то стек заполнен и возвращаемым значением будет TRUE; иначе, возвращаемоезначение — FALSE.
// проверка, не переполнен ли стек
int Stack::StackFuli(void) const
{
return top == MaxStackSize-1;
}
Метод ClearStack переустанавливает вершину стека на-1. Это восстанавливает начальное условие, определенное конструктором.
// удалить все элементы из стека
void Stack::ClearStack(void)
{
top = -1;
}
Стековые операции Push и Pop используют прямой доступ к вершине стека ине зависят от количества элементов в списке.
Абстрактный базовый класс Iterator.
Класс Iterator позволяет абстрагироваться от тонкостей реализацииалгоритма перебора, что дает независимость от деталей реализации базовогокласса. Мы определяем абстрактный класс Iterator как шаблон для итераторовсписков общего вида.
Спецификация класса Iterator.
Объявление:
template
class Iterator
{
protected:
// Флаг, показывающий, достиг ли итератор конца списка должен поддерживатьсяпроизводными классами
int iterationComplete;
public:
// конструктор
Iterator(void);
// обязательные методы итератора
virtual void Next(void) = 0;
virtual void Reset(void) = 0;
// методы для выборки/модификации данных
virtual T& Data(void) = 0;
// проверка конца списка
virtual int EndOfList(void) const;
};
Обсуждение:
Итератор является средством прохождения списка. Его основные методы:Reset (установка на первый элемент списка), Next (переход на следующийэлемент), EndOfList (определение конца списка). Функция Data осуществляетдоступ к данным текущего элемента списка.
Итератор симметричного метода прохождения.
Симметричное прохождение бинарного дерева поиска, в процессе которогоузлы посещаются в порядке возрастания их значений, является полезныминструментом.
Объявление:
// итератор симметричного прохождения бинарного дерева использует базовыйкласс Iterator
template
class InorderIterator: public Iterator
{
private:
// поддерживать стек адресов узлов
Stack * > S;
// корень дерева и текущий узел
TreeNode *root, *current;
// сканирование левого поддерева используется функцией Next
TreeNode*GoFarLeft(TreeNode *t);
public:
// конструктор
InorderIterator(TreeNode *tree);
//реализации базовых операций прохождения
virtual void Next(void);
virtualvoid Reset(void);
virtual T& Data(void);
//назначение итератору нового дерева
void SetTree(TreeNode *tree);
};
Описание:
Класс InorderIterator построен по общему для всех итераторов образцу.Метод EndOfList определен в базовом классе Iterator. Конструктор инициализируетбазовый класс и с помощью GoFarLeft находит начальный узел сканирования.
Пример:
TreeNode *root; // бинарное дерево
InorderIterator treeiter(root); // присоединить итератор
// распечатать начальный узел сканирования для смешанного прохождения этосамый левый узел дерева
cout
// сканирование узлов и печать их значений
for (treeiter.Reset(); !treeiter.EndOfList();treeiter.Next())
cout
РеализацияклассаInorderIterator.
Итерационный симметричный метод прохождения эмулирует рекурсивноесканирование с помощью стека адресов узлов. Начиная с корня, осуществляетсяспуск вдоль левых поддеревьев. По пути указатель каждого пройденного узлазапоминается в стеке. Процесс останавливается на узле с нулевым левымуказателем, который становится первым посещаемым узлом в симметричномсканировании. Спуск от узла t и запоминание адресов узлов в стеке выполняетметод GoFarLeft. Вызовом этого метода с t=root ищется первый посещаемый узел(рис. 18).
// вернуть адрес крайнего узла на левой ветви узла t
// запомнить в стеке адреса всех пройденных узлов
template
TreeNode*InorderIterator::GoFArLeft(TreeNode *t)
{
// если t=NULL, вернуть NULL
if (t == NULL)
returnNULL;
// пока не встретится узел с нулевым левым указателем, спускаться полевым ветвям, запоминая в стеке S адреса пройденных узлов. Возвратить указательна этот узел
while (t->Left()!= NULL)
{
S.Push(t);
t =t->Left();
}
return t;
}
/>
Рис. 18.
После инициализации базового класса конструктор присваивает элементуданных root адрес корня бинарного дерева поиска. Узел для начала симметричногосканирования получается в результате вызова функции GoFarLeft с root в качествепараметра. Это значение запоминается в переменной сurrent.
// инициализировать флаг iterationComplete. Базовый класс сбрасывает его,но
// дерево может быть пустым. начальный узлел сканирования — крайний слеваузел.
template
InorderIterator::InorderIterator(TreeNode*tree):
Iterator(), root(tree)
{
iterationComplete = (root == NULL);
current= GoFarLeft(root);
}
Метод Reset по существу является таким же, как и конструктор, заисключением того, что он очищает стек. Перед первым обращением к Next указательcurrent уже указывает на первый узел симметричного сканирования. Метод Nextработает по следующему алгоритму. Если правая ветвь узла не пуста, перейти кего правому сыну и осуществить спуск по левым ветвям до узла с нулевым левымуказателем, попутно запоминая в стеке адреса пройденных узлов.
Если правая ветвь узла пуста, то сканирование его левой ветви, самогоузла и его правой ветви завершено. Адрес следующего узла, подлежащегообработке, находится в стеке. Если стек не пуст, удалить следующий узел. Еслиже стек пуст, то все узлы обработаны и сканирование завершено. Итерационноепрохождение дерева, состоящего из пяти узлов, изображено на рисунке 19.
/>
Рис. 19.
template
void InorderIterator::Next(void)
{
// ошибка, если все узлы уже посещались
if(iterationComplete)
{
cerr
exit(1);
}
// current — текущий обрабатываемый узел
// если есть правое поддерево, спуститься до конца по его левой ветви,попутно запоминая в стеке адреса пройденных узлов
if(current->Right() != NULL)
current = GoFarLeft(current->Right());
//правого поддерева нет, но в стеке есть другие узлы, подлежащие обработке.
// Вытолкнуть из стека новый текущий адрес, продвинуться вверх по дереву
elseif (!S.StackEmpty())
current = S.Pop();
//нет ни правого поддерева, ни узлов в стеке. Сканирование завершено
else
iterationComplete = 1;
}
Алгоритм TreeSort.
Когда объект типа InorderIterator осуществляет прохождение дерева поиска,узлы проходятся в сортированном порядке и, следовательно, можно построить ещеодин алгоритм сортировки, называемый TreeSort. Этот алгоритм предполагает, чтоэлементы изначально хранятся в массиве. Поисковое дерево служит фильтром, кудаэлементы массива копируются в соответствии с алгоритмом вставки в бинарноедерево поиска. Осуществляя симметричное прохождение этого дерева и записываяэлементы снова в массив, мы получаем в результате отсортированный список. Нарисунке 20 показана сортировка 8 — элементного массива.
#include «bstree.h»
#include «treeiter.h»
// использование бинарного дерева поиска для сортировки массива
template
void TreeSort(T arr[], int n)
{
// бинарное дерево поиска, в которое копируется массив
BinSTreesortTree;
int i;
//вставить каждый элемент массива в поисковое дерево
for(i=0; i
sortTree.Insert(arr[i]);
//объявить итератор симметричного прохождения для sortTree
InorderIteratortreeSortIter(sortTree.GetRoot());
//выполнить симметричное прохождение дерева
// скопировать каждый элемент снова в массив
i = 0;
while (!treeSortIter.EndOfList())
{
arr[i++] = treeSortIter.Data();
treeSortIter.Next();
}
}
/>
Рис. 20.
3. Алгоритм реализацииАВЛ – деревьев через классы объектно – ориентированного программирования.
Программасоздана на объектно – ориентированном языке программирования C++в среде быстрой разработки (RAD) Bolrand C++Builder 6.0, имеет графический интерфейс.
/>
Текстпрограммы.
#pragma once
template class AvlTree
{
public:
KEY key;
VALUE value;
int balance;
AvlTree* left;
AvlTree* right;
bool empty;//заполнены ключ и значение или нет
AvlTree()
{
empty=true;
left = NULL;
right = NULL;
balance = 0;
}
AvlTree(KEY Key,VALUE Value)
{
empty=false;
key = Key;
value = Value;
left = NULL;
right = NULL;
balance = 0;
}
int add(KEY Key, VALUE Value)//добавление узла,возвращает изменился баланс(1) или нет (0)
{ //при добавлении в правую ветку баланс узлаувеличиваю на результат добавления
if (empty) //влевую уменьшаю
{ //послекаждого вызова add(...) вызываю TurnAround();
key = Key; //деревоперестраивается пока потомок текущего узла в нужном направлении не будет NULL
value = Value; //потомв этого потомка записываем новые значения
empty=false;
return 0;
}
if (Key == key)
throw CString(L«Уже есть»);
int a = balance;
if (Key > key)
{
if (right != NULL)
{
balance +=right->add(Key, Value);
TurnAround();
}
else
{
right = newAvlTree(Key, Value);
balance++;
}
}
else
{
if (left != NULL)
{
balance -=left->add(Key, Value);
TurnAround();
}
else
{
left = newAvlTree(Key, Value);
balance--;
}
}
if (balance != a)
{
return 1;
}
else
{
return 0;
}
}
void TurnAround() //нормализация дерева, еслибаланс не равномерный смещаю(поворачиваю) узел так,
{ //чтобыколичество потомков справа и слева не отличалось больше, чем на 1
if (balance == 2)
{
if (right->balance>= 0)
{
KEY tKey =key;
VALUEtValue = value;
key =right->key;
value =right->value;
right->key= tKey;
right->value= tValue;
AvlTree*tNode=right->right;
right->right= right->left;
right->left= left;
left =right;
right =tNode;
balance =left->balance — 1;
left->balance= 1 — left->balance;
}
else
{
KEY tKey =key;
VALUEtValue = value;
key =right->left->key;
value =right->left->value;
right->left->key= tKey;
right->left->value= tValue;
AvlTree* tNode = right->left->right;
right->left->right= right->left->left;
right->left->left= left;
left =right->left;
right->left= tNode;
balance =0;
right->balance= (left->balance == -1)? (1): (0);
left->balance= (left->balance == 1)? (-1): (0);
}
}
else
{
if (balance == -2)
{
if(left->balance
{
KEYtKey = key;
VALUEtValue = value;
key= left->key;
value= left->value;
left->key= tKey;
left->value= tValue;
AvlTree* tNode = left->left;
left->left= left->right;
left->right= right;
right= left;
left= tNode;
balance= 1 + right->balance;
right->balance= -1 — right->balance;
}
else
{
KEYtKey = key;
VALUEtValue = value;
key= left->right->key;
value= left->right->value;
left->right->key= tKey;
left->right->value= tValue;
AvlTree* tNode = left->right->left;
left->right->left= left->right->right;
left->right->right= right;
right= left->right;
left->right= tNode;
balance= 0;
left->balance= (right->balance == 1)? (-1): (0);
right->balance= (right->balance == -1)? (1): (0);
}
}
}
}
typename AvlTree*getNode(KEY Key)//поиск узла по ключу
{
AvlTree*node=this;
while (true)
{
if (node == NULL)
throwCString(L«Не найдено»);
if (node->key ==Key)
returnnode;
if (node->key
{
node =node->right;
}
else
{
node =node->left;
}
}
}
int remove(KEYKey,AvlTree*parent=NULL) //удаление узла, перемещаюсь по дереву, по ключу
{ //припрохождении узла опять меняю баланс в зависимости от направления и поворачиваюего TurnAround()
int a = balance; //как дошел до нужного узла перемещаю его, пока оба его потомка не будут NULL
if (key == Key) //и удаляю
{
if (right == NULL && left == NULL)
{
if(parent->left->key==this->key)
{
parent->left=NULL;
}
else
{
parent->right=NULL;
}
return 1;
}
else
{
if (balance >= 0)
{
if (right != NULL)
{
AvlTree* tNode = right;
while (tNode->left != NULL)
{
tNode = tNode->left;
}
KEY tKey = key;
VALUE tValue = value;
key = tNode->key;
value = tNode->value;
tNode->key = tKey;
tNode->value = tValue;
balance -= right->remove(Key,this);
}
}
else
{
if (left != NULL)
{
AvlTree* tNode = left;
while (tNode->right != NULL)
{
tNode = tNode->right;
}
KEY tKey = key;
VALUE tValue = value;
key = tNode->key;
value = tNode->value;
tNode->key = tKey;
tNode->value = tValue;
balance += left->remove(Key,this);
}
}
}
}
else
{
if (Key > key)
{
if (right!=NULL)
{
balance -= right->remove(Key,this);
TurnAround();
}
else
{
throw CString(«Не найдено»);
}
}
else
{
if (left!=NULL)
{
balance += left->remove(Key,this);
TurnAround();
}
else
{
throw CString(«Не найдено»);
}
}
}
if (balance != a)
{
return (balance == 0)? (1): (0);
}
else
{
return 0;
}
}
~AvlTree()
{
}
};
СПИСОК ЛИТЕРАТУРЫ
1. Каррано Ф.М., Причард Дж.Дж. К26Абстракция данных и решение задач на С++ — I -. Стены и зеркала, 3-е издание.: Пер.с англ. — М.:Издательский дом «Вильяме», 2003. — 848 с: ил. — Парал. тит. англ.
2. Ж.-Л. Лорьер. Системыискусственного интеллекта. – М.: Мир, 1991.
3. Бабэ Б. Просто и ясно о Borland С++: пер. с англ. – СПб.: Питер,1997. – 464 с.
4. Ирэ П. Объектно – ориентированноепрограммирование с использованием С++: пер. с англ. К.: НИПФ ДиаСофтЛтд, 1995.– 480 с.
5. Программирование. Учебник под ред.Свердлика А.Н., МО СССР, 1992. – 608 с.
6. Сван Т. Программирование для Windows в Borland С++: пер. с англ. – М.: БИНОМ. – 480 с.
7. Шамис В.А. Borland С++ Builder. Программирование на С++ без проблем.– М.: Нолидж, 1997. – 266 с.
8. Шилдт Г. Теория и практика С++:пер. с англ. – СПб.: BHV –Санкт – Петербург, 1996. – 416 с.
9. www.rsdn.ru/article/alg/bintree/avl.xml.