20 (1106257)

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла

Курс «Алгоритмы и алгоритмические языки»1 семестр 2013/2014Лекция 201АВЛ-деревьяВ АВЛ-деревьях (Адельсон-Вельский, Ландис) оценка сложностине лучше, чем в совершенном дереве, но не хуже, чем вдеревьях Фибоначчи для всех операций: поиск, исключение,занесение.АВЛ-деревом (подравненным деревом) называется такоедвоичное дерево, в котором для любой его вершины высотылевого и правого поддерева отличаются не более, чем на 1.Пример АВЛ-дерева.2АВЛ-деревья В узлах дерева записаны значения показателя сбалансированности(balance factor), определяемого по формуле:balance factor = height(right subtree) – height(left subtree)Показатель сбалансированности может иметь одно из трех значений–1: Высота левого поддерева на 1 больше высоты правого поддерева.0: Высоты обоих поддеревьев одинаковы.+1: Высота правого поддерева на 1 больше высоты левого поддерева. У совершенного дерева все узлы имеют показатель баланса 0 (этосамое «хорошее» АВЛ-дерево) а у дерева Фибоначчи все узлы имеютпоказатель баланса +1 (либо –1) (это самое «плохое» АВЛ-дерево).

3АВЛ-деревьяТипичная структура узла АВЛ-дерева:typedef int key_t;struct avlnode;typedef struct avlnode *avltree;struct avlnode {key_tkey;//ключavltreeleft;//левое поддеревоavltreeright;//правое поддеревоintbalance;//показатель балансаintheight;//высота поддерева};4АВЛ-деревья.Базовые операции над АВЛ-деревьями.avltree makeempty (avltree t);//удалить деревоavltree find (key_t x, avltree t); //поиск по ключуavltree findmin (avltree t);//минимальный ключavltree findmax (avltree t);//максимальный ключavltree insert (key_t x, avltree t); //вставить узелavltree delete (key_t x, avltree t); //исключить узел5Реализация простейших базовых операцийУдалить дерево:avltree makeempty (avltree t) {if (t != NULL) {makeempty (t->left);makeempty (t->right);free (t);}return NULL;}Поиск по ключу:avltree find (key_t x, avltree t) {if (t == NULL || x == t->key)return t;if (x < t->key)return find (x, t->left);if (x > t->key)return find (x, t->right);}6Реализация простейших базовых операцийМинимальный и максимальный ключи:avltree findmin (avltree t) {if (t == NULL)return NULL;else if (t->left == NULL)return t;elsereturn findmin (t->left);}avltree findmax (avltree t) {if (t != NULL)while (t->right != NULL)t = t->right;return t;}7Включение узла в АВЛ-деревоПоддержка балансировки АВЛ-дерева при выполненииоперации включения ключейРассматриваемое дерево состоит из корневой вершины r илевого (L) и правого (R) поддеревьев, имеющих высоты hL и hRсоответственно.Для определенности будем считать, что новый ключ включаетсяв поддерево L.hL не изменяется ⇒ не изменяются соотношения между hL и hR⇒ свойства АВЛ-дерева сохраняются.hL увеличивается на 1 ⇒ возможны три случая:(1) hL = hR ⇒ после добавления вершины L и R станут разнойвысоты, но свойство сбалансированности сохранится(2) hL < hR ⇒ после добавления новой вершины L и R станутравной высоты, т.е.

сбалансированность общего дерева дажеулучшится(3) hL > hR ⇒ после включения ключа сбалансированностьнарушится, и потребуется перестройка дерева.8Включение узла в АВЛ-дерево(3a)Новая вершина добавляется к левому поддеревуподдерева L. В результате поддерево с корнем в узле Bразбалансировалось: разность высот его левого иправого поддеревьев стала равной –2 .hh+1hh+1zxxyhhyzПреобразование, разрешающее ситуацию (3a)(однократный поворот RR):Делаем узел A корневым узлом поддерева, в результатеправое поддерева с корнам в узле B «опускается» иразность высот становится равной 09Включение узла в АВЛ-дерево(3b)Новая вершина добавляется к правому поддеревуподдерева L. В результате поддерево с корнем в Cразбалансировалось: разность высот его левого иправого поддеревьев стала равной -2.h-1h-1hxyhh-1zhtxhh-1yztПреобразование, разрешающее ситуацию (3b)(двукратный поворот LR):«Вытягиваем» узел B на самый верх, чтобы егоподдеревья поднялись.

Для этого сначала делаем левыйповорот, меняя местами поддеревья с корневыми узламиA и B, а потом – правый поворот, меняя местами10поддеревья с корневыми узлами B и C.Построение АВЛ-дереваВысота поддерева с корнем в узле P.static inline int height (avltree p) {return p ? p->height : 0;}Выбор более длинного поддереваstatic inline int max (int lhs, int rhs) {return lhs > rhs ? lhs : rhs;}11Построение АВЛ-дереваОднократные поворотыМежду узлом и его левым сыномФункция SingleRotateWithLeft вызываетсятолько в том случае, когда у узла K2 есть левыйсын.

Функция выполняет поворот между узлом (K2)и его левым сыном, корректирует высоты поддеревьев,после чего возвращает новый кореньstatic avltree SingleRotateWithLeft (avltree k2) {avltree k1;/* выполнение поворота */k1 = k2->left;k2->left = k1->right;/* k1 != NULL */k1->right = k2;/* корректировка высот переставленных узлов */k2->height = max (height (k2->left),height (k2->right)) + 1;k1->height = max (height (k1->left), k2->height) + 1;return k1; /* новый корень */12}Построение АВЛ-дереваОднократные поворотыМежду узлом и его правым сыномЭта функция вызывается только в том случае, когда уузла K1 есть правый сын. Функция выполняет поворотмежду узлом (K1) и его правым сыном, корректируетвысоты поддеревьев, после чего возвращает новый кореньstatic avltree SingleRotateWithRight (avltree k1) {avltree 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; /* новый корень */}13Построение АВЛ-дерева Двойные поворотыLR- поворотЭта функция вызывается только тогда, когдау узла K3 есть левый сын, а у левого сынаK3 есть правый сын.

Функция выполняет двойнойповорот LR, корректирует высоты поддеревьев, послечего возвращает новый кореньstatic avltree DoubleRotateWithLeft (avltree k3) {/* Поворот между K1 и K2 */k3->left = SingleRotateWithRight (k3->left);/* Поворот между K3 и K2 */return SingleRotateWithLeft (k3);}14Построение АВЛ-дерева Двойные поворотыRL- поворотЭта функция вызывается только в том случае, когда уузла K1 есть правый сын, а у правого сына узла K1есть левый сын. Функция выполняет двойной поворотRL, корректирует высоты поддеревьев, после чеговозвращает новый кореньstatic avltree DoubleRotateWithRight (avltree k1){/* Поворот между K3 и K2 */k1->right = SingleRotateWithLeft (k1->right);/* Поворот между K1 и K2 */return SingleRotateWithRight(k1);}15Построение АВЛ-дерева Вставить новый узел (все)avltree insert (key_t x,avltree t) {if (t == NULL) {/* создание дерева с одним узлом */t = malloc (sizeof(struct avlnode));if (!t)abort();t->key = x;t->height = 1;t->left = t->right = NULL;}else if (x < t->key) {t->left = insert (x, t->left);if (height (t->left) –height (t->right) == 2) {if (x < t->left->key)t = SingleRotateWithLeft (t);elset = DoubleRotateWithLeft (t);}}else if (x > t->key) {t->right = insert (x, t->right);if (height (t->right) –height (t->left) == 2) {if (x > t->right->key)t = SingleRotateWithRight (t);elset = DoubleRotateWithRight (t);}}/* иначе x уже в дереве */t->height = max (height (t->left),height (t->right)) + 1;t->balance = height (t->right)– height (t->left);return t;16}Построение АВЛ-дерева Вставить новый узелavltree insert (key_t x, avltree t) {if (t == NULL) {/* создание дерева с одним узлом */t = malloc (sizeof (struct avlnode));if (!t)abort();t->key = x;t->height = 1;t->left = t->right = NULL;}else if (x < t->key) {t->left = insert (x, t->left);if (height (t->left) – height (t->right) == 2) {17 Вставить новый узелif (x < t->left->key)t = SingleRotateWithLeft (t);elset = DoubleRotateWithLeft (t);}}else if (x > t->key) {t->right = insert (x, t->right);if (height (t->right) – height (t->left) == 2) {if (x > t->right->key)t = SingleRotateWithRight (t);elset = DoubleRotateWithRight (t);}}/* иначе x уже в дереве */t->height = max (height (t->left), height (t->right)) + 1;t->balance = height (t->right) – height (t->left);return t;18}Построение АВЛ-дерева ПримерПусть на «вход» функции insert() последовательно поступаютцелые числа 4,5,7,2,1,3,6.Изобразим процесс «роста» АВЛ-дерева (в скобках для частивершин указан показатель сбалансированности):Числа в примере подобраны так, чтобы обеспечить как можнобольше поворотов при минимальном числе включений.19Построение АВЛ-дерева Пример построения АВЛ-дерева20Исключение узла из АВЛ-дереваОбъявление функции:avltree delete (key_t x, avltree t);Исключение узла из АВЛ-дерева требует балансировки дерева.Иными словами, в конец функции, выполняющей исключениеузла, необходимо добавить вызовы функций:SingleRotateWithRight(T), SingleRotateWithLeft(T),DoubleRotateWithRight(T) и DoubleRotateWithLeft(T)Возможны случаи вращения, не встречавшиеся при вставке.Может оказаться необходимым выполнить несколько вращений.21Оценка сложностиРанее были получены оценки высоты(1)самого «хорошего» АВЛ-дерева, содержащего m узлов(полностью сбалансированное дерево)h = O(log2(m+1))(2)самого «плохого» АВЛ-дерева, содержащего m узлов(дерево Фибоначчи)h ≤ 1.44 ⋅ log 2 (m + 1) − 0.32Следовательно, для «среднего» АВЛ-дерева, содержащего mузлов оценка высоты будет где-то посередине:log 2 (m + 1) ≤ h ≤ 1.44 ⋅ log 2 (m + 1) − 0.3222.

Характеристики

Тип файла PDF

PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.

Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.

Список файлов лекций