Лекция 17. AVL-деревья (1107992)
Текст из файла
Лекции по курсу “Алгоритмы и алгоритмические языки”, 1 курс, 1 поток, 2010/2011 уч.годЛекция 17 AVL-деревья17.1. АВЛ -деревья.17.1.1. В АВЛ-деревьях (Адельсон-Вельский, Ландис) оценка сложности не лучше, чем всовершенном дереве, но не хуже, чем в деревьях Фибоначчи для всех операций: поиск,исключение, занесение. АВЛ-деревом (подравненным деревом) называется такоедвоичное дерево, когда для любой его вершины высоты левого и правого поддереваотличаются не более, чем на 1.-11-1-1-100000100Рис. 1. Пример АВЛ-дерева.17.1.2 Пример АВЛ-дерева показан на рисунке 1. В узлах дерева записаны значенияпоказателя сбалансированности (balance Factor), определяемого по формуле:balance Factor = height(right subtree) – height(left subtree)Показатель баланса может иметь одно из трех значений–1: Высота левого поддерева на 1 больше высоты правого поддерева.0: Высоты обоих поддеревьев одинаковы.+1: Высота правого поддерева на 1 больше высоты левого поддерева.У совершенного дерева все узлы имеют показатель баланса 0, т.е.
это самое «хорошее»АВЛ-дерево, а у дерева Фибоначчи все узлы имеют показатель баланса +1 (либо –1),т.е. это самое «плохое» АВЛ-дерево.Числа Леонарда (количество узлов в дереве Фибоначчи):N0 = 0; N1 = 1; Nh = N(h-1) +1 + N(h-2)17.1.3. Типичная структура узла АВЛ-дерева:typedef int KeyType;struct AvlNode;typedef struct AvlNode *Position;typedef struct AvlNode *AvlTree;struct AvlNode {KeyTypeKey;//ключAvlTreeLeft;//левое поддеревоAvlTreeRight;//правое поддеревоIntBalance;//показатель баланса1(с) Кафедра системного программирования ф-та ВМК МГУ, 2010Лекции по курсу “Алгоритмы и алгоритмические языки”, 1 курс, 1 поток, 2010/2011 уч.годIntHight;//высота поддерева};17.1.4 Базовые операции над АВЛ-деревьями.AvlTree MakeEmpty(AvlTree T);//удалить деревоPosition Find(KeyType X, AvlTree T);//поиск по ключуPosition FindMin(AvlTree T);//минимальный ключPosition FindMax(AvlTree T);//максимальный ключAvlTree Insert(KeyType X, AvlTree T); //вставить узелAvlTree Delete(KeyType X, AvlTree T); //исключить узел17.2.
Реализация простейших базовых операций:17.2.1. Удалить дерево:AvlTree MakeEmpty(AvlTree T){if(T != NULL) {MakeEmpty(T->Left);MakeEmpty(T->Right);free(T);}return NULL;}17.2.2. Поиск по ключу:Position Search(KeyType X, AvlTree T){if(T == NULL) return NULL;if(X < T->Element) return Find(X, T->Left);elseif(X > T->Element) return Find(X, T->Right);else return T;}17.2.3.
Минимальный и максимальный ключи:Position FindMin(AvlTree T){if(T == NULL) return NULL;elseif(T->Left == NULL) return T;else return FindMin(T->Left);}Position FindMax(AvlTree T){if(T != NULL)while(T->Right != NULL)T = T->Right;return T;}17.3. Включение узла в АВЛ-дерево17.3.1. Поддержка балансировки АВЛ-дерева при выполнении операции включенияключей. Пусть рассматриваемое дерево состоит из корневой вершины r и левого (L) и2(с) Кафедра системного программирования ф-та ВМК МГУ, 2010Лекции по курсу “Алгоритмы и алгоритмические языки”, 1 курс, 1 поток, 2010/2011 уч.годправого (R) поддеревьев.
Будем обозначать через hl высоту L, а через hr - высоту R.Для определенности будем считать, что новый ключ включается в поддерево L. Есливысота L не изменяется, то не изменяются и соотношения между высотой L и R, исвойства АВЛ-дерева сохраняются. Если же при включении в поддерево L высотаэтого поддерева увеличивается на 1, то возможны следующие три случая:• если hl = hr, то после добавления вершины L и R станут разной высоты, носвойство сбалансированности сохранится;• если hl < hr, то после добавления новой вершины L и R станут равной высоты, т.е.сбалансированность общего дерева даже улучшится;• если hl > hr, то после включения ключа критерий сбалансированностинарушится, и потребуется перестройка дерева.Рассмотрим две разные ситуации: (1) новая вершина добавляется к поддереву L, (2)новая вершина добавляется к поддереву R.
Правила восстановления балансировкипоказаны на рисунках 2 и 3.(a) Исходное состояние ситуации (1): в результате добавления поддерево с корнем вузле B разбалансировалось: разность высот его левого и правого поддеревьев сталаравной –2 .(b) Преобразование, разрешающее ситуацию (1) (Случай RR – однократный поворот):Делаем узел A корневым узлом поддерева, в результате правое поддерева с корнам вузле B «опускается» и разность высот становится равной –1 . Это преобразованиеподобно применению ассоциативного закона: (αβ)γ = α(βγ).3(с) Кафедра системного программирования ф-та ВМК МГУ, 2010Лекции по курсу “Алгоритмы и алгоритмические языки”, 1 курс, 1 поток, 2010/2011 уч.годРис. 2.
Случай RR (симметричный случай LL: α(βγ) = (αβ)γ).(a) Исходное состояние ситуации (2): в результате добавления элемента в левоеподдерево узла B поддерево с корнем в узле C разбалансировалось: разность высот еголевого и правого поддеревьев стала равной 2.(b) Преобразование, разрешающее ситуацию (2) (Случай LR – двукратный поворот).Нужно вытянуть узел B на самый верх, чтобы его поддеревья поднялись.
Для этогосначала делаем левый поворот, меняя местами поддеревья с корневыми узлами A и B, апотом – правый поворот, меняя местами поддеревья с корневыми узлами B и C.Рис. 3. Случай LR (симметричный случай RL).В обоих случаях в дереве требуется изменить несколько ссылок (соответствующиефункции приводятся ниже). Кроме того, новые деревья имеют высоту h + 2, т.е. точноравную высоте, которая была до вставки. Следовательно, остаток поддерева корневымузлом A (если таковой имеется) всегда остается сбалансированным.На рисунках 4 и 5 представлены примеры, иллюстрирующие балансирование АВЛдерева в обоих рассмотренных случаях.4(с) Кафедра системного программирования ф-та ВМК МГУ, 2010Лекции по курсу “Алгоритмы и алгоритмические языки”, 1 курс, 1 поток, 2010/2011 уч.год(b)(a)Рис.
4. Пример балансировки АВЛ-дерева. (Случай RR – однократный поворот)(b)(a)Рис. 5. Пример балансировки АВЛ-дерева. (Случай LR – двукратный поворот)Рисунки хорошо проясняют суть преобразования.Есть простой признак того, когда следует применить один поворот LL, а когда – дваповорота RR и RL.
Если height(r→l) ≤ height(r→r), то следует выполнить LL.17.4. Построение АВЛ-дерева17.4.1. Высота поддерева с корнем в узле P.static int Height(Position P){ //static, чтобы можно было//использовать в рекурсивных функцияхif(P == NULL) return -1;else return P->Height;}Выбор более длинного поддереваstatic int Max( int Lhs, int Rhs ){return Lhs > Rhs ? Lhs : Rhs;}17.4.2. Однократные повороты17.4.2.1.
Между узлом и его левым ребенком/* Эту функцию можно вызывать только в том случае, когда у *//* узла K2 есть левый ребенок. Функция выполняет поворот *//* между узлом (K2) и его левым ребенком, корректирует */5(с) Кафедра системного программирования ф-та ВМК МГУ, 2010Лекции по курсу “Алгоритмы и алгоритмические языки”, 1 курс, 1 поток, 2010/2011 уч.год/* высоты поддеревьев, после чего возвращает новый корень */static Position SingleRotateWithLeft(Position K2) {Position K1;/* выполнение поворота */K1 = K2->Left;K2->Left = K1->Right;K1->Right = K2;/* корректировка высот переставленных узлов */K2->Height = Max(Height(K2->Left), Height(K2->Right))+1;K1->Height = Max(Height(K1->Left), K2->Height) + 1;return K1; /* новый корень */}17.4.2.2.
Между узлом и его правым ребенком/* Эту функцию можно вызывать только в том случае, когда у *//* узла K1 есть правый ребенок. Функция выполняет поворот *//* между узлом (K1) и его правым ребенком, корректирует *//* высоты поддеревьев, после чего возвращает новый корень */static Position SingleRotateWithRight(Position K1){Position K2;K2 = K1->Right;K1->Right = K2->Left;K2->Left = K1;K1->Height = Max(Height(K1->Left), Height(K1->Right))+1;K2->Height = Max(Height(K2->Right), K1->Height) + 1;return K2; /* новый корень */}17.4.3. Двойные повороты17.4.3.1. LR- поворот/* Эту функцию можно вызывать только тогда, когда *//* у узла K3 есть левый ребенок, а у левого ребенка *//* K3 есть правый ребенок.
Функция выполняет двойной *//* поворот LR, корректирует высоты поддеревьев, после *//* чего возвращает новый корень */static Position DoubleRotateWithLeft(Position K3){/* Поворот между K1 и K2 */K3->Left = SingleRotateWithRight(K3->Left);/* Поворот между K3 и K2 */return SingleRotateWithLeft(K3);}17.4.3.1. RL- поворот/* Эту функцию можно вызывать только в том случае, когда у *//* узла K1 есть правый ребенок, а у правого ребенка узла K1 *//* есть левый ребенок. Функция выполняет двойной поворот *//* RL, корректирует высоты поддеревьев, после чего *//* возвращает новый корень */static Position DoubleRotateWithRight(Position K1){6(с) Кафедра системного программирования ф-та ВМК МГУ, 2010Лекции по курсу “Алгоритмы и алгоритмические языки”, 1 курс, 1 поток, 2010/2011 уч.год/* Поворот между K3 и K2 */K1->Right = SingleRotateWithLeft(K1->Right);/* Поворот между K1 и K2 */return SingleRotateWithRight(K1);}17.4.4.
Вставить новый узелAvlTree Insert(ElementType X, AvlTree T){if(T == NULL){/* создание дерева с одним узлом */T = malloc(sizeof(struct AvlNode));if(T == NULL)FatalError("Out of space!");else {T->Element = X; T->Height = 0;T->Left = T->Right = NULL;}}elseif(X < T->Element){T->Left = Insert(X, T->Left);if(Height(T->Left) - Height(T->Right) == 2)if(X < T->Left->Element)T = SingleRotateWithLeft(T);elseT = DoubleRotateWithLeft(T);}if(X > T->Element){T->Right = Insert(X, T->Right);if(Height(T->Right) - Height(T->Left) == 2)if(X > T->Right->Element)T = SingleRotateWithRight(T);elseT = DoubleRotateWithRight(T);}/* Иначе X уже в дереве и ничего не нужно делать; */T->Height = Max(Height(T->Left), Height(T->Right)) + 1;return T;}17.4.5.
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
