в левом и правом поддереве различаются не более чем на
1.Идеально сбалансированные бинарные деревья
Разделы презентаций
- Разное
- Английский язык
- Астрономия
- Алгебра
- Биология
- География
- Геометрия
- Детские презентации
- Информатика
- История
- Литература
- Математика
- Медицина
- Менеджмент
- Музыка
- МХК
- Немецкий язык
- ОБЖ
- Обществознание
- Окружающий мир
- Педагогика
- Русский язык
- Технология
- Физика
- Философия
- Химия
- Шаблоны, картинки для презентаций
- Экология
- Экономика
- Юриспруденция
Деревья 2
Содержание
- 1. Деревья 2
- 2. Бинарное дерево назовем идеально сбалансированным, если для каждой его
- 3. Длина внутреннего пути в идеально сбалансированном дереве,
- 4. взять одну вершину в качестве корня.построить левое
- 5. node *Tree (int n, node **p)// Построение
- 6. Слайд 6
- 7. Бинарное дерево поиска называется балансированным по высоте, если для
- 8. бозначим Th - АВЛ-деpево высотой h с количеством узлов Nh. ТогдаМатематический анализ АВЛ-деpевьевТеоpема
- 9. Hаибольшая длина ветвей (h+1) в АВЛ-деpеве, содеpжащем Nh узлов, опpеделяется неравенствомЛемма
- 10. Hаименьшая длина ветвей (h+1) в АВЛ-деpеве, содеpжащем Nh узлов опpеделяется фоpмулойh+1=log2(Nh+1)Лемма
- 11. Пусть Th - АВЛ-деpево высоты h, имеющее Nh узлов. Тогда для средней длины ветвей дерева Sh пpи имеет место следующая асимптотическая оценка:Теоpема
- 12. Hаиболее асимметpичное АВЛ-деpево Th высоты h имеет наиболее асимметpичное АВЛ-деpевоTh-1 высоты h-1 в качестве одного
- 13. если k=0, то дерево Фибоначчи пусто;если k=1, то дерево Фибоначчи
- 14. Приммер деpевьев Фибоначчи
- 15. показатель сбалансиpованности узла = = высота пpавого поддеpева - высота левого поддеpева.показатель сбалансиpованности
- 16. Класс бинарных деревьев, в которых ограничения на
- 17. Корневым балансом b(Tn) бинарного дерева Tn=(Tl,v,Tr) называется величина
- 18. Дерево Tn называется балансированным по весу с балансом A, 0
- 19. Класс бинарных деревьев с балансом A - WB[A]. Пустое бинарное
- 20. Деревья Фибоначчи
- 21. Высота дерева Tn из класса WB[A] не превышаетТеоремавысота дерева Фибоначчи не превышает log2(n+1)-1
- 22. сначала было hL = hR. После включения L и R станут разной высоты,
- 23. struct node { int Key;
- 24. Показатель сбалансированности вершины = разность между высотой правого и левого поддереваОпределение
- 25. Проход по дереву, чтобы убедиться, что включаемого
- 26. p1 = (*p).Left; (*p).Left = (*p1).Right; (*p1).Right = p; (*p).bal = 0; p = p1;Однократный LL-поворот
- 27. LL-поворотp1 = (*p).Left; (*p).Left = (*p1).Right; (*p1).Right
- 28. Слайд 28
- 29. p1 = (*p).Left;Сохранение адреса нового корня дерева
- 30. (*p).Left = (*p1).Right;Переприкрепление
- 31. (*p1).Right = p;Определение правого поддерева "нового" корня
- 32. (*p).bal = 0; p = p1; Установка начальных значений
- 33. Слайд 33
- 34. p1 = (*p).Right; (*p).Right = (*p1).Left;
- 35. Слайд 35
- 36. p1 = (*p).Right;Сохранение адреса нового корня дерева
- 37. (*p).Right = (*p1).Left;Переприкрепление
- 38. (*p1).Left = p;Определение левого поддерева "нового" корня
- 39. (*p).bal = 0; p = p1;Установка начальных значений
- 40. Слайд 40
- 41. Если после вставки показатели сбалансированности вершин имеют
- 42. Слайд 42
- 43. p1 = (*p).Left; p2 = (*p1).Right;
- 44. Слайд 44
- 45. p1 = (*p).Left; p2 = (*p1).Right;Определение p1 и p2
- 46. (*p1).Right = (*p2).Left;Переприкрепление
- 47. (*p2).Left = p1;Определение левого поддерева "нового" корня
- 48. (*p).Left = (*p2).Right;Переприкрепление
- 49. (*p2).Right = *p;Определение правого поддерева "нового" корня
- 50. p = p2;Установка начальных значений
- 51. Слайд 51
- 52. p1 =(*p).Right; p2 = (*p1).Left;
- 53. Слайд 53
- 54. p1 = (*p).Right; p2 = (*p1).Left;Определение p1 и p2
- 55. (*p1).Left = (*p2). Right;Переприкрепление
- 56. (*p2). Right = p1;Определение правого поддерева "нового" корня
- 57. (*p).Right = (*p2). Left;Переприкрепление
- 58. (*p2). Left = *p;Определение правого поддерева "нового" корня
- 59. p = p2;Установка начальных значений
- 60. Слайд 60
- 61. Если после вставки показатели сбалансированности имеют разный
- 62. Слайд 62
- 63. Построение AVL дерева
- 64. http://neerc.ifmo.ru/wiki/index.php?title=%D0%90%D0%92%D0%9B-%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%BEhttp://www.proteus2001.narod.ru/gen/txt/6/avl.htmlhttp://habrahabr.ru/post/150732/
- 65. Скачать презентанцию
Бинарное дерево назовем идеально сбалансированным, если для каждой его вершины количество вершин в левом и правом поддереве различаются не более чем на 1.Идеально сбалансированные бинарные деревья
Слайды и текст этой презентации
Слайд 2Бинарное дерево назовем идеально сбалансированным, если для каждой его вершины количество вершин
Слайд 3Длина внутреннего пути в идеально сбалансированном дереве, содержащем n вершин,
не превосходит величины:
(n+1)[log2n] - 2 * 2[log2n] - 2
Теорема
![Длина внутреннего пути в идеально сбалансированном дереве, содержащем n вершин, не превосходит величины:(n+1)[log2n] - 2 * 2[log2n] -](/img/thumbs/614328d4afb9b21b5270946c8bddcfed-800x.jpg "Деревья 2 Длина внутреннего пути в идеально сбалансированном дереве, содержащем n вершин, не")
Слайд 4взять одну вершину в качестве корня.
построить левое поддерево с nl =
n DIV 2 вершинами тем же способом.
построить правое поддерево с nr =
n-nl-1 вершинами тем же способом.Алгоритм построения идеально сбалансированного дерева при известном числе вершин n
Слайд 5node *Tree (int n, node **p)
// Построение идеально сбалансированного дерева
с n вершинами.
// *p - указатель на корень дерева.
{
node
*now;int x,nl,nr;
now = *p;
if (n==0) *p = NULL;
else
{ nl = n/2; nr = n - nl - 1; cin>>x;
now = new(node);(*now).Key = x;
Tree (nl,&((*now).Left)); Tree (nr,&((*now).Right)); *p = now;}
}
Слайд 7Бинарное дерево поиска называется балансированным по высоте, если для каждой его вершины
высота ее двух поддеревьев различается не более, чем на 1.
Деревья, удовлетворяющие этому условию, часто называют АВЛ-деревьями (по первым буквам фамилий их изобретателей Г.М.Адельсона-Вельского иЕ.М.Ландиса).Показателем балансированности вершины бинарного дерева мы будем называть разность высоты его правого и левого поддерева.
Балансированные по высоте деревья (АВЛ-деревья)
Слайд 8бозначим Th - АВЛ-деpево высотой h с количеством узлов Nh. Тогда
Математический анализ АВЛ-деpевьев
Теоpема
Слайд 9Hаибольшая длина ветвей (h+1) в АВЛ-деpеве, содеpжащем Nh узлов, опpеделяется неравенством
Лемма
Слайд 10Hаименьшая длина ветвей (h+1) в АВЛ-деpеве, содеpжащем Nh узлов опpеделяется фоpмулойh+1=log2(Nh+1)
Лемма
Слайд 11Пусть Th - АВЛ-деpево высоты h, имеющее Nh узлов. Тогда для средней длины ветвей дерева Sh пpи имеет место
следующая асимптотическая оценка:
Теоpема
Слайд 12Hаиболее асимметpичное АВЛ-деpево Th высоты h имеет наиболее асимметpичное АВЛ-деpевоTh-1 высоты h-1 в качестве одного из своих поддеpевьев
и наиболее асимметpичное АВЛ-деpево высоты h-2 в качестве дpугого. Подобные деpевья называются деpевьями Фибоначчи.
Деревья Фибоначчи
Слайд 13если k=0, то дерево Фибоначчи пусто;
если k=1, то дерево Фибоначчи состоит из единственного
узла, ключ которого содержит 1;
если k >=2, то корень дерева Фибоначчи содержит
ключ Fk, левое поддерево есть дерево Фибоначчи порядка k-1, правое поддерево есть дерево Фибоначчи порядка k-2 с ключами в узлах, увеличенными на Fk.Fk - k-е число Фибоначчи: F0=1, F1=1, F2=2, F3=3, F4=5, F5=8, F6=13,
Дерево Фибоначчи порядка k
Слайд 15показатель сбалансиpованности узла = = высота пpавого поддеpева - высота
левого поддеpева.
показатель сбалансиpованности
Слайд 16Класс бинарных деревьев, в которых ограничения на высоты поддеревьев заменено
ограничением на число вершин в поддеревьях.
От АВЛ-деревьев WB-деревья отличаются тем,
что содержат параметр, который может изменяться так, что можно произвольно ограничивать длину самого длинного пути из корня в висячую вершину за счет увеличения дисбаланса.Балансированные по весу деревья (WB-деревья)
Слайд 17Корневым балансом b(Tn) бинарного дерева Tn=(Tl,v,Tr) называется величина
nl+1
b(Tn)=-------, n >= 1
n+10 < b(Tn) < 1
Слайд 18Дерево Tn называется балансированным по весу с балансом A, 0
оно удовлетворяет следующим условиям:
A
по весу деревья с балансом A.Определение
Слайд 19Класс бинарных деревьев с балансом A - WB[A].
Пустое бинарное дерево T0, по определению,
входит в WB[A] для любого A.
Класс WB[A] становится все более ограниченным по мере того,
как A меняется от 0 до 1/2.Случай 1/2
либо левое и правое поддеревья каждой вершины содержат одинаковое число вершин, поэтому классу WB[1/2] принадлежат полностью балансированные деревья с n=2k-1 вершинами,
Либо см. рисунок
![Класс бинарных деревьев с балансом A - WB[A]. Пустое бинарное дерево T0, по определению, входит в WB[A] для любого A. Класс WB[A] становится все более ограниченным](/img/thumbs/60633ae977d42dc53bd4532558047b33-800x.jpg "Деревья 2 Класс бинарных деревьев с балансом A - WB[A]. Пустое бинарное дерево T0, по определению, входит")
Слайд 21Высота дерева Tn из класса WB[A] не превышает
Теорема
высота дерева Фибоначчи не превышает log2(n+1)-1
![Высота дерева Tn из класса WB[A] не превышаетТеоремавысота дерева Фибоначчи не превышает log2(n+1)-1](/img/thumbs/05f82d885e0f750861fb99a4678f8e3d-800x.jpg "Деревья 2 Высота дерева Tn из класса WB[A] не превышаетТеоремавысота дерева Фибоначчи не превышает log2(n+1)-1")
Слайд 22сначала было hL = hR. После включения L и R станут разной высоты, но критерий сбалансированности
не будет нарушен;
сначала было hL < hR. После включения L и R станут равной высоты, то
есть критерий сбалансированности даже улучшится;сначала было hL > hR. После включения критерий сбалансированности нарушится и дерево необходимо перестраивать.
Алгоритмы балансировки
Включение в сбалансированное дерево новой вершины
Слайд 23struct node
{
int Key;
int Count;
int bal; // Показатель балансированности вершины.
node
*Left; node *Right;
};
Слайд 24Показатель сбалансированности вершины = разность между высотой правого и левого поддерева
Определение
Слайд 25Проход по дереву, чтобы убедиться, что включаемого значения в дереве
нет;
включение новой вершины и определение результирующего показателя сбалансированности;
"отступление" по пути
поиска и проверка в каждой вершине показателя сбалансированности. При необходимости - балансировка.
Слайд 26p1 = (*p).Left;
(*p).Left = (*p1).Right;
(*p1).Right = p;
(*p).bal
= 0;
p = p1;
Однократный LL-поворот
Слайд 27LL-поворот
p1 = (*p).Left;
(*p).Left = (*p1).Right;
(*p1).Right = p;
(*p).bal
= 0;
p = p1;
RR-поворот
p1 = (*p).Right;
(*p).Right =
(*p1).Left;(*p1).Left = p;
(*p).bal = 0;
p = p1;
Слайд 34p1 = (*p).Right;
(*p).Right = (*p1).Left;
(*p1).Left =
p;
(*p).bal = 0; p = p1;
Однократный RR-поворот
Слайд 41Если после вставки показатели сбалансированности вершин имеют одинаковый знак и
отличаются только на единицу, то восстановить баланс дерева можно однократным поворотом (включая
одно "переприкрепление" поддерева), при этом вставка не будет оказывать влияния на другие участки дерева.
Слайд 43 p1 = (*p).Left;
p2 = (*p1).Right;
(*p1).Right =
(*p2).Left;
(*p2).Left = p1;
(*p).Left = (*p2).Right;
(*p2).Right =
*p;p = p2;
Двукратный LR-поворот
Слайд 52p1 =(*p).Right; p2 = (*p1).Left;
(*p1).Left = (*p2).
Right; (*p2). Right = p1;
(*p).Right = (*p2). Left;
(*p2). Left = *p;p = p2;
Двукратный RL-поворот
Слайд 61Если после вставки показатели сбалансированности имеют разный знак, то можно
восстановить баланс дерева двухкратными поворотами трех вершин. В этом случае вставка
также не оказывает влияния на другие участки дерева
Слайд 64http://neerc.ifmo.ru/wiki/index.php?title=%D0%90%D0%92%D0%9B-%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%BE
http://www.proteus2001.narod.ru/gen/txt/6/avl.html
http://habrahabr.ru/post/150732/
