Деревья. Идеально сбалансированные бинарные деревья - презентация, доклад, проект скачать

Нажмите для полного просмотра!

Деревья. Идеально сбалансированные бинарные деревья, слайд №1

Деревья. Идеально сбалансированные бинарные деревья, слайд №2

Деревья. Идеально сбалансированные бинарные деревья, слайд №3

Деревья. Идеально сбалансированные бинарные деревья, слайд №4

Деревья. Идеально сбалансированные бинарные деревья, слайд №5

Деревья. Идеально сбалансированные бинарные деревья, слайд №6

Деревья. Идеально сбалансированные бинарные деревья, слайд №7

Деревья. Идеально сбалансированные бинарные деревья, слайд №8

Деревья. Идеально сбалансированные бинарные деревья, слайд №9

Деревья. Идеально сбалансированные бинарные деревья, слайд №10

Деревья. Идеально сбалансированные бинарные деревья, слайд №11

Деревья. Идеально сбалансированные бинарные деревья, слайд №12

Деревья. Идеально сбалансированные бинарные деревья, слайд №13

Деревья. Идеально сбалансированные бинарные деревья, слайд №14

Деревья. Идеально сбалансированные бинарные деревья, слайд №15

Деревья. Идеально сбалансированные бинарные деревья, слайд №16

Деревья. Идеально сбалансированные бинарные деревья, слайд №17

Деревья. Идеально сбалансированные бинарные деревья, слайд №18

Деревья. Идеально сбалансированные бинарные деревья, слайд №19

Деревья. Идеально сбалансированные бинарные деревья, слайд №20

Деревья. Идеально сбалансированные бинарные деревья, слайд №21

Деревья. Идеально сбалансированные бинарные деревья, слайд №22

Деревья. Идеально сбалансированные бинарные деревья, слайд №23

Деревья. Идеально сбалансированные бинарные деревья, слайд №24

Деревья. Идеально сбалансированные бинарные деревья, слайд №25

Деревья. Идеально сбалансированные бинарные деревья, слайд №26

Деревья. Идеально сбалансированные бинарные деревья, слайд №27

Деревья. Идеально сбалансированные бинарные деревья, слайд №28

Деревья. Идеально сбалансированные бинарные деревья, слайд №29

Деревья. Идеально сбалансированные бинарные деревья, слайд №30

Деревья. Идеально сбалансированные бинарные деревья, слайд №31

Деревья. Идеально сбалансированные бинарные деревья, слайд №32

Деревья. Идеально сбалансированные бинарные деревья, слайд №33

Деревья. Идеально сбалансированные бинарные деревья, слайд №34

Деревья. Идеально сбалансированные бинарные деревья, слайд №35

Деревья. Идеально сбалансированные бинарные деревья, слайд №36

Деревья. Идеально сбалансированные бинарные деревья, слайд №37

Деревья. Идеально сбалансированные бинарные деревья, слайд №38

Деревья. Идеально сбалансированные бинарные деревья, слайд №39

Деревья. Идеально сбалансированные бинарные деревья, слайд №40

Деревья. Идеально сбалансированные бинарные деревья, слайд №41

Деревья. Идеально сбалансированные бинарные деревья, слайд №42

Деревья. Идеально сбалансированные бинарные деревья, слайд №43

Деревья. Идеально сбалансированные бинарные деревья, слайд №44

Деревья. Идеально сбалансированные бинарные деревья, слайд №45

Деревья. Идеально сбалансированные бинарные деревья, слайд №46

Деревья. Идеально сбалансированные бинарные деревья, слайд №47

Деревья. Идеально сбалансированные бинарные деревья, слайд №48

Деревья. Идеально сбалансированные бинарные деревья, слайд №49

Деревья. Идеально сбалансированные бинарные деревья, слайд №50

Деревья. Идеально сбалансированные бинарные деревья, слайд №51

Деревья. Идеально сбалансированные бинарные деревья, слайд №52

Деревья. Идеально сбалансированные бинарные деревья, слайд №53

Деревья. Идеально сбалансированные бинарные деревья, слайд №54

Деревья. Идеально сбалансированные бинарные деревья, слайд №55

Деревья. Идеально сбалансированные бинарные деревья, слайд №56

Деревья. Идеально сбалансированные бинарные деревья, слайд №57

Деревья. Идеально сбалансированные бинарные деревья, слайд №58

Деревья. Идеально сбалансированные бинарные деревья, слайд №59

Деревья. Идеально сбалансированные бинарные деревья, слайд №60

Деревья. Идеально сбалансированные бинарные деревья, слайд №61

Деревья. Идеально сбалансированные бинарные деревья, слайд №62

Деревья. Идеально сбалансированные бинарные деревья, слайд №63

Деревья. Идеально сбалансированные бинарные деревья, слайд №64

Содержание ▲

Вы можете ознакомиться и скачать презентацию на тему Деревья. Идеально сбалансированные бинарные деревья. Доклад-сообщение содержит 64 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

Слайды и текст этой презентации

Слайд 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

Слайд 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

Описание слайда:

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