Презентация Деревья. Идеально сбалансированные бинарные деревья онлайн
На нашем сайте вы можете скачать и просмотреть онлайн доклад-презентацию на тему Деревья. Идеально сбалансированные бинарные деревья абсолютно бесплатно. Урок-презентация на эту тему содержит всего 64 слайда. Все материалы созданы в программе PowerPoint и имеют формат ppt или же pptx. Материалы и темы для презентаций взяты из открытых источников и загружены их авторами, за качество и достоверность информации в них администрация сайта не отвечает, все права принадлежат их создателям. Если вы нашли то, что искали, отблагодарите авторов - поделитесь ссылкой в социальных сетях, а наш сайт добавьте в закладки.
Оцените презентацию от 1 до 5 баллов!
- Тип файла:ppt / pptx (powerpoint)
- Всего слайдов:64 слайда
- Для класса:1,2,3,4,5,6,7,8,9,10,11
- Размер файла:731.88 kB
- Просмотров:70
- Скачиваний:0
- Автор:неизвестен
Слайды и текст к этой презентации:
№1 слайд
Содержание слайда: Деревья 2
№2 слайд
Содержание слайда: Идеально сбалансированные бинарные деревья
Бинарное дерево назовем идеально сбалансированным, если для каждой его вершины количество вершин в левом и правом поддереве различаются не более чем на 1.
№3 слайд
Содержание слайда: Теорема
Длина внутреннего пути в идеально сбалансированном дереве, содержащем n вершин, не превосходит величины:
(n+1)[log2n] - 2 * 2[log2n] - 2
№4 слайд
Содержание слайда: Алгоритм построения идеально сбалансированного дерева при известном числе вершин n
взять одну вершину в качестве корня.
построить левое поддерево с nl = n DIV 2 вершинами тем же способом.
построить правое поддерево с nr = n-nl-1 вершинами тем же способом.
№5 слайд
Содержание слайда: node *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;}
}
№6 слайд
Содержание слайда:
№7 слайд
Содержание слайда: Балансированные по высоте деревья (АВЛ-деревья)
Бинарное дерево поиска называется балансированным по высоте, если для каждой его вершины высота ее двух поддеревьев различается не более, чем на 1. Деревья, удовлетворяющие этому условию, часто называют АВЛ-деревьями (по первым буквам фамилий их изобретателей Г.М.Адельсона-Вельского иЕ.М.Ландиса).
Показателем балансированности вершины бинарного дерева мы будем называть разность высоты его правого и левого поддерева.
№8 слайд
Содержание слайда: Математический анализ АВЛ-деpевьев
бозначим Th - АВЛ-деpево высотой h с количеством узлов Nh. Тогда
№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и имеет место следующая асимптотическая оценка:
№12 слайд
Содержание слайда: Деревья Фибоначчи
Hаиболее асимметpичное АВЛ-деpево Th высоты h имеет наиболее асимметpичное АВЛ-деpевоTh-1 высоты h-1 в качестве одного из своих поддеpевьев и наиболее асимметpичное АВЛ-деpево высоты h-2 в качестве дpугого. Подобные деpевья называются деpевьями Фибоначчи.
№13 слайд
Содержание слайда: Дерево Фибоначчи порядка k
если 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,
№14 слайд
Содержание слайда: Приммер деpевьев Фибоначчи
№15 слайд
Содержание слайда: показатель сбалансиpованности
показатель сбалансиpованности узла = = высота пpавого поддеpева - высота левого поддеpева.
№16 слайд
Содержание слайда: Балансированные по весу деревья (WB-деревья)
Класс бинарных деревьев, в которых ограничения на высоты поддеревьев заменено ограничением на число вершин в поддеревьях.
От АВЛ-деревьев WB-деревья отличаются тем, что содержат параметр, который может изменяться так, что можно произвольно ограничивать длину самого длинного пути из корня в висячую вершину за счет увеличения дисбаланса.
№17 слайд
Содержание слайда: Корневым балансом b(Tn) бинарного дерева Tn=(Tl,v,Tr) называется величина
nl+1
b(Tn)=-------, n >= 1
n+1
0 < b(Tn) < 1
№18 слайд
Содержание слайда: Определение
Дерево Tn называется балансированным по весу с балансом A, 0< A < 1/2, если оно удовлетворяет следующим условиям:
A <= b(Tn) <= 1 - A;
Tl, Tr - балансированные по весу деревья с балансом A.
№19 слайд
Содержание слайда: Класс бинарных деревьев с балансом A - WB[A].
Пустое бинарное дерево T0, по определению, входит в WB[A] для любого A.
Класс WB[A] становится все более ограниченным по мере того, как A меняется от 0 до 1/2.
Случай 1/2
либо левое и правое поддеревья каждой вершины содержат одинаковое число вершин, поэтому классу WB[1/2] принадлежат полностью балансированные деревья с n=2k-1 вершинами,
Либо см. рисунок
№20 слайд
Содержание слайда: Деревья Фибоначчи
№21 слайд
Содержание слайда: Теорема
Высота дерева Tn из класса WB[A] не превышает
№22 слайд
Содержание слайда: Алгоритмы балансировки
сначала было hL = hR. После включения L и R станут разной высоты, но критерий сбалансированности не будет нарушен;
сначала было hL < hR. После включения L и R станут равной высоты, то есть критерий сбалансированности даже улучшится;
сначала было hL > hR. После включения критерий сбалансированности нарушится и дерево необходимо перестраивать.
№23 слайд
Содержание слайда: struct node
{
int Key;
int Count;
int bal; // Показатель балансированности вершины.
node *Left;
node *Right;
};
№24 слайд
Содержание слайда: Определение
Показатель сбалансированности вершины = разность между высотой правого и левого поддерева
№25 слайд
Содержание слайда: Проход по дереву, чтобы убедиться, что включаемого значения в дереве нет;
включение новой вершины и определение результирующего показателя сбалансированности;
"отступление" по пути поиска и проверка в каждой вершине показателя сбалансированности. При необходимости - балансировка.
№26 слайд
Содержание слайда: Однократный LL-поворот
p1 = (*p).Left;
(*p).Left = (*p1).Right;
(*p1).Right = p;
(*p).bal = 0;
p = p1;
№27 слайд
Содержание слайда: LL-поворот
№28 слайд
Содержание слайда:
№29 слайд
Содержание слайда: Сохранение адреса нового корня дерева
p1 = (*p).Left;
№30 слайд
Содержание слайда: Переприкрепление
(*p).Left = (*p1).Right;
№31 слайд
Содержание слайда: Определение правого поддерева "нового" корня
(*p1).Right = p;
№32 слайд
Содержание слайда: Установка начальных значений
(*p).bal = 0;
p = p1;
№33 слайд
Содержание слайда:
№34 слайд
Содержание слайда: Однократный RR-поворот
p1 = (*p).Right;
(*p).Right = (*p1).Left;
(*p1).Left = p;
(*p).bal = 0; p = p1;
№35 слайд
Содержание слайда:
№36 слайд
Содержание слайда: Сохранение адреса нового корня дерева
p1 = (*p).Right;
№37 слайд
Содержание слайда: Переприкрепление
(*p).Right = (*p1).Left;
№38 слайд
Содержание слайда: Определение левого поддерева "нового" корня
(*p1).Left = p;
№39 слайд
Содержание слайда: Установка начальных значений
(*p).bal = 0; p = p1;
№40 слайд
Содержание слайда:
№41 слайд
Содержание слайда: Если после вставки показатели сбалансированности вершин имеют одинаковый знак и отличаются только на единицу, то восстановить баланс дерева можно однократным поворотом (включая одно "переприкрепление" поддерева), при этом вставка не будет оказывать влияния на другие участки дерева.
№42 слайд
Содержание слайда:
№43 слайд
Содержание слайда: Двукратный LR-поворот
p1 = (*p).Left;
p2 = (*p1).Right;
(*p1).Right = (*p2).Left;
(*p2).Left = p1;
(*p).Left = (*p2).Right;
(*p2).Right = *p;
p = p2;
№44 слайд
Содержание слайда:
№45 слайд
Содержание слайда: Определение p1 и p2
p1 = (*p).Left; p2 = (*p1).Right;
№46 слайд
Содержание слайда: Переприкрепление
(*p1).Right = (*p2).Left;
№47 слайд
Содержание слайда: Определение левого поддерева "нового" корня
(*p2).Left = p1;
№48 слайд
Содержание слайда: Переприкрепление
(*p).Left = (*p2).Right;
№49 слайд
Содержание слайда: Определение правого поддерева "нового" корня
(*p2).Right = *p;
№50 слайд
Содержание слайда: Установка начальных значений
p = p2;
№51 слайд
Содержание слайда:
№52 слайд
Содержание слайда: Двукратный RL-поворот
p1 =(*p).Right; p2 = (*p1).Left;
(*p1).Left = (*p2). Right; (*p2). Right = p1;
(*p).Right = (*p2). Left; (*p2). Left = *p;
p = p2;
№53 слайд
Содержание слайда:
№54 слайд
Содержание слайда: Определение p1 и p2
p1 = (*p).Right; p2 = (*p1).Left;
№55 слайд
Содержание слайда: Переприкрепление
(*p1).Left = (*p2). Right;
№56 слайд
Содержание слайда: Определение правого поддерева "нового" корня
(*p2). Right = p1;
№57 слайд
Содержание слайда: Переприкрепление
(*p).Right = (*p2). Left;
№58 слайд
Содержание слайда: Определение правого поддерева "нового" корня
(*p2). Left = *p;
№59 слайд
Содержание слайда: Установка начальных значений
p = p2;
№60 слайд
Содержание слайда:
№61 слайд
Содержание слайда: Если после вставки показатели сбалансированности имеют разный знак, то можно восстановить баланс дерева двухкратными поворотами трех вершин. В этом случае вставка также не оказывает влияния на другие участки дерева
№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%BE
http://www.proteus2001.narod.ru/gen/txt/6/avl.html
http://habrahabr.ru/post/150732/
Скачать все slide презентации Деревья. Идеально сбалансированные бинарные деревья одним архивом:
