Слайды лекций - 2014 (лектор - Белеванцев А. А.) (1107979), страница 14

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

Текст из файла (страница 14)

Пусть имеется множество K из m ключей:K = {k0, k1, …, km-1}Разбиение K на три подмножества K1, K2, K3:|K2 | = 1, |K1| ≥ 0, |K3| ≥ 0.K2 = {k} ⇒ ∀l∈ K1: l < k и ∀r∈ K3: r ≥ kДалее по рекурсии: разбиваемK1 на K11, K12, K13K3 на K31, K32, K33и т.д. пока ключи не кончатсяПример:K = {15,10,1,3,8,12,4}.Первое разбиение: {1,3,4}, {8}, {15,10,12};второе разбиение: {{1}{3}{4}}{8}{{10}{12}{15}}.Получилось полностью сбалансированное двоичное дерево.Определение.

Дерево называется полностьюсбалансированным (совершенным), если длина пути от корнядо любой листовой вершины одинакова.13Построение двоичного дерева поиска.Пусть h – высота полностью сбалансированного двоичногодерева. Тогда число вершин m должно быть равно:m = 1 + 2 + 22 + … + 2h-1 = 2h – 1откуда h = log2(m + 1).Если все m ключей известны заранее, их можно отсортироватьза O(m⋅log2m), после чего построение сбалансированногодерева будет тривиальной задачей.Если дерево строится по мере поступления ключей,то возможны все варианты: от линейного дерева с высотой O(m)до полностью сбалансированного дерева с высотой O(log2m).Пусть T = {root, left, right} – двоичное дерево; тогдаhT = max(hleft, hright) + 1.14Деревья ФибоначчиЧисла Фибоначчи возникли в решении задачи о кроликах,предложенном в XIII веке Леонардо из Пизы, известным какФибоначчи.Задача о кроликах: пара новорожденных кроликов помещенана остров.

Каждый месяц любая пара дает приплод – также парукроликов.Пара начинает давать приплод в возрасте двух месяцев.Сколько кроликов будет на острове в конце n-го месяца?В конце первого и второго месяцев на острове будет одна паракроликов:f1 = 1, f2 = 1.В конце третьего месяца родится новая пара, так чтоf3 = f2 + f1 = 2.По индукции можно доказать, что для n ≥ 3fn = fn-1 + fn-2.15Деревья Фибоначчиn-е число Фибоначчи вычисляет следующая функция:int Fbn (int n) {if (n == 1 || n == 2)return 1;else {int g, h, k, Fb;g = h = 1;for (k = 2; k < n; k++) {Fb = g + h;h = g;g = Fb;}return Fb;}}16Деревья ФибоначчиОпределение дерева Фибоначчи(это тоже искусственное дерево).(1)(2)Пустое дерево – это дерево Фибоначчи с высотой h = 0.Двоичное дерево, левое и правое поддерево которогоесть деревья Фибоначчи с высотами соответственноh – 1 и h – 2 (либо h – 2 и h – 1), есть деревоФибоначчи с высотой h.Из определения следует, что в дереве Фибоначчизначения высот левого и правого поддерева отличаютсяровно на 1.17Деревья ФибоначчиПример.

Дерево Фибоначчи с h = 6.131885113274610916151220171914118Деревья ФибоначчиТеорема 1. Число вершин в дереве Фибоначчи Fh высоты hравно m(h) = fh+2 – 1.Доказательство (по индукции).h = 0:m(0) = f2 – 1 = 0m(1) = f3 – 1 = 1.Шаг: по определению m(h) = m(h – 1) + m(h – 2) + 1.Имеем m(h) = (fh+1 – 1) + (fh – 1) + 1 = fh+2 – 1,так как fh + fh + 1 = f h + 219Деревья ФибоначчиТеорема 2. Пусть C1 и C2 таковы, что уравнениеr2 – C1r – C2 = 0имеет два различных корня r1 и r2 , r1 ≠ r2.Тогда дляan = α1r1n + α2r2nвыполняется соотношениеan = C1an-1 + C2an-2 .(*)Доказательство.

r1 и r2 – корни уравнения (*),тоr12 = C1r1 + C2r22 = C1r2 + C2.Имеем:C1an-1 + C2an-2 = C1(α1r1n-1 + α2r2n-1) + C2(α1r1n-2 + α2r2n-2) == α1r1n-2 (C1r1 + C2) + α2r2n-2 (C1r2 + C2) == α1r1n-2 r12 + α2r2n-2 r22 = α1r1n + α2r2n = an(**)Теорема доказана.20Деревья ФибоначчиТеорема 3. Пусть C1 и C2 таковы, что уравнениеr2 – C1r – C2 = 0имеет два корня r1 и r2 , r1 ≠ r2.(*)Тогдаиз an = C1an-1 + C2an-2 и начальных условий а0 и а1следует an =α1r1n + α2r2nдля n = 1, 2, ...Доказательство.

Нужно не только повторить в обратномпорядке вывод (**), но и подобрать такие α1 и α2, чтобыа0 = α1 + α2, а1 = α1r1 + α2r2(***)Рассматривая (***) как систему линейных уравненийотносительно α1 и α2, получим:α1 =a1 − a0 ⋅ r2,r1 − r2Теорема доказана.− a1 + a0 ⋅ r1α2 =r1 − r221Деревья ФибоначчиПрименим доказанные теоремы к числам Фибоначчи:fn = fn-1 + fn-2.Уравнение r2 – r – 1 = 0 имеет корни1− 51+ 5r2 =r1 =22Следовательно, согласно теореме 3nn1− 5 1+ 5  ,αf n = α1 ⋅ r + α 2 ⋅ r = α1 ⋅ +⋅2 2  2 f 0 = α1 + α 2 = 0,n1n21− 5 1+ 5  =1 + α2 ⋅ f1 = α1 ⋅ 2211,α 2 = −α1 =5522Деревья ФибоначчиОткудаn1 1+ 5 1 1− 5  −fn =⋅ ⋅ 5  2 5  2 nСогласно теореме 1m( h ) = f h + 21 1+ 5 −1 =5  2 1 1− 5 5  2 h+ 21 1− 5 −5  2 h+ 2−1h+2<11 1+ 5 m( h ) + 1 >5  2 h+ 223Деревья Фибоначчи1+ 5Обозначение γ =21 h+2m( h) + 1 > γ5(****)Логарифмируя обе части (****) , получаемh+2<откудаlog 2 (m + 1) log 2 5+log 2 γlog 2 γh < 1,44 ⋅ log 2 (m + 1) − 0,32Таким образом, мы доказали, что для деревьев Фибоначчи с числомвершин m количество сравнений в худшем случае не превышает1,44 ⋅ log 2 (m + 1) − 0,3224АВЛ-деревьяВ АВЛ-деревьях (Адельсон-Вельский, Ландис) оценка сложностине лучше, чем в совершенном дереве, но не хуже, чем вдеревьях Фибоначчи для всех операций: поиск, исключение,занесение.АВЛ-деревом (подравненным деревом) называется такоедвоичное дерево, в котором для любой его вершины высотылевого и правого поддерева отличаются не более, чем на 1.Пример АВЛ-дерева.25АВЛ-деревья В узлах дерева записаны значения показателя сбалансированности(balance factor), определяемого по формуле:balance factor = height(right subtree) – height(left subtree)Показатель сбалансированности может иметь одно из трех значений–1: Высота левого поддерева на 1 больше высоты правого поддерева.0: Высоты обоих поддеревьев одинаковы.+1: Высота правого поддерева на 1 больше высоты левого поддерева. У совершенного дерева все узлы имеют показатель баланса 0 (этосамое «хорошее» АВЛ-дерево) а у дерева Фибоначчи все узлы имеютпоказатель баланса +1 (либо –1) (это самое «плохое» АВЛ-дерево).

26АВЛ-деревьяТипичная структура узла АВЛ-дерева:typedef int key_t;struct avlnode;typedef struct avlnode *avltree;struct avlnode {key_tkey;//ключavltreeleft;//левое поддеревоavltreeright;//правое поддерево// intbalance;показатель балансаintheight;//высота поддерева};27АВЛ-деревья.Базовые операции над АВЛ-деревьями.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); //исключить узел28Реализация простейших базовых операцийУдалить дерево: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);}29Реализация простейших базовых операцийМинимальный и максимальный ключи: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;}30Включение узла в АВЛ-деревоПоддержка балансировки АВЛ-дерева при выполненииоперации включения ключейРассматриваемое дерево состоит из корневой вершины r илевого (L) и правого (R) поддеревьев, имеющих высоты hL и hRсоответственно.Для определенности будем считать, что новый ключ включаетсяв поддерево L.hL не изменяется ⇒ не изменяются соотношения между hL и hR⇒ свойства АВЛ-дерева сохраняются.hL увеличивается на 1 ⇒ возможны три случая:(1) hL = hR ⇒ после добавления вершины L и R станут разнойвысоты, но свойство сбалансированности сохранится(2) hL < hR ⇒ после добавления новой вершины L и R станутравной высоты, т.е.

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

В результате поддерево с корнем в Cразбалансировалось: разность высот его левого иправого поддеревьев стала равной -2.h-1h-1hxyhh-1zhtxhh-1yztПреобразование, разрешающее ситуацию (3b)(двукратный поворот LR):«Вытягиваем» узел B на самый верх, чтобы егоподдеревья поднялись. Для этого сначала делаем левыйповорот, меняя местами поддеревья с корневыми узламиA и B, а потом – правый поворот, меняя местами33поддеревья с корневыми узлами 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;}34Построение АВЛ-дереваОднократные поворотыМежду узлом и его левым сыномФункция SingleRotateWithLeft вызываетсятолько в том случае, когда у узла K2 есть левыйсын.

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

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