Лекция 18. AVL-деревья (окончание) (1107993)
Текст из файла
Лекции по курсу “Алгоритмы и алгоритмические языки”, 1 курс, 1 поток, 2010/2011 уч.годЛекция 18 AVL-деревья (окончание)18.1. Построение АВЛ-дерева18.1.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;}18.1.2. Однократные повороты18.1.2.1. Между узлом и его левым ребенком/* Эту функцию можно вызывать только в том случае, когда у *//* узла K2 есть левый ребенок. Функция выполняет поворот *//* между узлом (K2) и его левым ребенком, корректирует *//* высоты поддеревьев, после чего возвращает новый корень */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; /* новый корень */}18.1.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; /* новый корень */}18.1.3. Двойные повороты18.1.3.1.
LR- поворот/* Эту функцию можно вызывать только тогда, когда *//* у узла K3 есть левый ребенок, а у левого ребенка *//* K3 есть правый ребенок. Функция выполняет двойной *//* поворот LR, корректирует высоты поддеревьев, после *//* чего возвращает новый корень */static Position DoubleRotateWithLeft(Position K3){/* Поворот между K1 и K2 */(с) Кафедра системного программирования ф-та ВМК МГУ, 20101Лекции по курсу “Алгоритмы и алгоритмические языки”, 1 курс, 1 поток, 2010/2011 уч.год}K3->Left = SingleRotateWithRight(K3->Left);/* Поворот между K3 и K2 */return SingleRotateWithLeft(K3);18.1.3.1. RL- поворот/* Эту функцию можно вызывать только в том случае, когда у *//* узла K1 есть правый ребенок, а у правого ребенка узла K1 *//* есть левый ребенок. Функция выполняет двойной поворот *//* RL, корректирует высоты поддеревьев, после чего *//* возвращает новый корень */static Position DoubleRotateWithRight(Position K1){/* Поворот между K3 и K2 */K1->Right = SingleRotateWithLeft(K1->Right);/* Поворот между K1 и K2 */return SingleRotateWithRight(K1);}18.1.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;}18.1.5.
Пример построения АВЛ-дерева.(с) Кафедра системного программирования ф-та ВМК МГУ, 20102Лекции по курсу “Алгоритмы и алгоритмические языки”, 1 курс, 1 поток, 2010/2011 уч.годПусть на «вход» функции Search() последовательно поступают целые числа4,5,7,2,1,3,6. Изобразим процесс «роста» АВЛ-дерева (в скобках для части вершинуказан показатель сбалансированности) [1,с.256]:Это тщательно подобранный пример, показывающий ситуацию: как можно большеповоротов при минимальном числе включений. (рис. 6)Рис.6.
Построение АВЛ-дерева18.2. Исключение узла из АВЛ-дерева18.2.1. Объявление функции:AvlTree Delete( ElementType X, AvlTree T ){}18.2.2. Исключение узла из АВЛ-дерева отличается от исключения узла из двоичного дерева(рассматривалось на прошлой лекции) необходимостью балансировки дерева послеисключения узла. Иными словами в конец функции, выполняющей исключение узланеобходимо добавить вызовы функций:SingleRotateWithRight(T), SingleRotateWithLeft(T),DoubleRotateWithRight(T) и DoubleRotateWithLeft(T)18.2.3. При исключении узла, имеющего двух детей возможен случай, не возникающий привставке узлов: дерево, подвешенное к узлу rr, имеет высоту h + 1 (при вставке узловтакой случай возникнуть не может, так как в этом случае может увеличиться высотатолько одного поддерева).
В этом случае необходим дополнительный поворототносительно узла r.(с) Кафедра системного программирования ф-та ВМК МГУ, 20103Лекции по курсу “Алгоритмы и алгоритмические языки”, 1 курс, 1 поток, 2010/2011 уч.год18.3. Оценки сложности18.3.1. На лекции 16 были получены оценки высоты для самого «хорошего» АВЛ-дерева,содержащего m узлов – h = O(log2m) (полностью сбалансированное дерево) и самого«плохого» АВЛ-дерева, содержащего m узлов – h ≤ 1.44⋅ log 2 (m + 1) – 0.32 (деревоФибоначчи). Следовательно, для «среднего» АВЛ-дерева, содержащего m узлов оценкавысоты будет log 2 (m + 1) ≤ h ≤ 1.44⋅ log 2 (m + 1) – 0.32.m1162564,096log 2 m04812m65,5361,048,47616,778,616(с) Кафедра системного программирования ф-та ВМК МГУ, 2010log 2 m1620244.
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
