Презентация на тему: Деревья 2

Деревья 2
Идеально сбалансированные бинарные деревья
Теорема
Алгоритм построения идеально сбалансированного дерева при известном числе вершин  n
Деревья 2
Деревья 2
Балансированные по высоте деревья (АВЛ-деревья)
Математический анализ АВЛ-де p евьев
Деревья 2
Деревья 2
Деревья 2
Деревья Фиб о наччи
Дерево Фибоначчи порядка  k
Приммер де p евьев Фибоначчи
показатель сбалансиpованности
Балансированные по весу деревья ( WB -деревья)
Деревья 2
Определение
Деревья 2
Деревья Фибоначчи
Теорема
Алгоритмы балансировки
Деревья 2
Определение
Деревья 2
Однократный LL- поворот
Деревья 2
Деревья 2
Сохранение адреса нового корня дерева
Переприкрепление
Определение правого поддерева "нового" корня
Установка начальных значений
Деревья 2
Однократный RR- поворот
Деревья 2
Сохранение адреса нового корня дерева
Переприкрепление
Определение левого поддерева "нового" корня
Установка начальных значений
Деревья 2
Деревья 2
Деревья 2
Двукратный LR- поворот
Деревья 2
Определение  p1   и  p2
Переприкрепление
Определение левого поддерева "нового" корня
Переприкрепление
Определение правого поддерева "нового" корня
Установка начальных значений
Деревья 2
Двукратный RL- поворот
Деревья 2
Определение  p1   и  p2
Переприкрепление
Определение правого поддерева "нового" корня
Переприкрепление
Определение правого поддерева "нового" корня
Установка начальных значений
Деревья 2
Деревья 2
Деревья 2
Построение AVL дерева
Деревья 2
1/64
Средняя оценка: 4.9/5 (всего оценок: 83)
Код скопирован в буфер обмена
Скачать (731 Кб)
1

Первый слайд презентации: Деревья 2

Изображение слайда
2

Слайд 2: Идеально сбалансированные бинарные деревья

Бинарное дерево назовем  идеально сбалансированным, если для  каждой его вершины количество вершин в левом и правом поддереве различаются не более чем на 1. Идеально сбалансированные бинарные деревья

Изображение слайда
3

Слайд 3: Теорема

Длина внутреннего пути в идеально сбалансированном дереве, содержащем n вершин, не превосходит величины : ( n+1)[log 2 n] - 2 * 2 [log 2 n]  - 2 Теорема

Изображение слайда
4

Слайд 4: Алгоритм построения идеально сбалансированного дерева при известном числе вершин  n

взять одну вершину в качестве корня. построить левое поддерево с  nl = n DIV 2  вершинами тем же способом. построить правое поддерево с  nr = n-nl-1  вершинами тем же способом. Алгоритм построения идеально сбалансированного дерева при известном числе вершин  n

Изображение слайда
5

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

Слайд 6

Изображение слайда
7

Слайд 7: Балансированные по высоте деревья (АВЛ-деревья)

Бинарное дерево поиска называется  балансированным по высоте, если  для каждой его вершины высота ее двух поддеревьев различается не более, чем на 1. Деревья, удовлетворяющие этому условию, часто называют  АВЛ-деревьями  (по первым буквам фамилий их изобретателей  Г.М.Адельсона -Вельского   и Е.М.Ландиса ). Показателем балансированности вершины бинарного дерева мы будем называть  разность высоты его правого и левого поддерева. Балансированные по высоте деревья (АВЛ-деревья)

Изображение слайда
8

Слайд 8: Математический анализ АВЛ-де p евьев

бозначим   T h  - АВЛ- деpево высотой  h  с количеством узлов  N h. Тогда Математический анализ АВЛ-де p евьев Тео p ема

Изображение слайда
9

Слайд 9

Hаибольшая длина ветвей  (h+1)  в АВЛ- деpеве, содеpжащем   N h  узлов, опpеделяется неравенством Лемма

Изображение слайда
10

Слайд 10

Hаименьшая длина ветвей  (h+1)  в АВЛ- деpеве, содеpжащем   N h  узлов опpеделяется фоpмулой h+1=log 2 (N h +1) Лемма

Изображение слайда
11

Слайд 11

Пусть  T h  - АВЛ- деpево высоты  h, имеющее  N h  узлов. Тогда для  средней длины ветвей дерева   S h   пpи  имеет место следующая асимптотическая оценка: Тео p ема

Изображение слайда
12

Слайд 12: Деревья Фиб о наччи

Hаиболее асимметpичное АВЛ- деpево   T h  высоты  h  имеет  наиболее асимметpичное АВЛ-деpевоT h-1   высоты h-1  в качестве одного из своих поддеpевьев и  наиболее асимметpичное АВЛ- деpево  высоты  h-2  в качестве дpугого. Подобные деpевья называются  деpевьями Фибоначчи. Деревья Фиб о наччи

Изображение слайда
13

Слайд 13: Дерево Фибоначчи порядка  k

если  k=0, то дерево Фибоначчи  пусто ; если  k=1, то дерево Фибоначчи состоит из единственного узла, ключ которого содержит 1; если  k >=2, то корень дерева Фибоначчи содержит ключ  F k, левое поддерево есть  дерево Фибоначчи порядка  k-1, правое поддерево есть  дерево Фибоначчи порядка  k-2  с ключами в узлах, увеличенными на  F k. F k  -  k - е число Фибоначчи:  F 0 =1, F 1 =1, F 2 =2, F 3 =3, F 4 =5, F 5 =8, F 6 =13, Дерево Фибоначчи порядка  k

Изображение слайда
14

Слайд 14: Приммер де p евьев Фибоначчи

Изображение слайда
15

Слайд 15: показатель сбалансиpованности

узла = = высота пpавого поддеpева - высота левого поддеpева. показатель сбалансиpованности

Изображение слайда
16

Слайд 16: Балансированные по весу деревья ( WB -деревья)

Класс бинарных деревьев, в которых ограничения на высоты поддеревьев заменено ограничением на число вершин в поддеревьях. От АВЛ-деревьев  WB -деревья отличаются тем, что содержат параметр, который может изменяться так, что можно произвольно ограничивать длину самого длинного пути из корня в висячую вершину за счет увеличения дисбаланса. Балансированные по весу деревья ( WB -деревья)

Изображение слайда
17

Слайд 17

Корневым балансом  b( T n )  бинарного дерева   T n =( T l,v,T r )  называется величина n l +1 b(T n )=-------, n >= 1 n+1 0 < b( T n ) < 1

Изображение слайда
18

Слайд 18: Определение

Дерево   T n   называется балансированным по весу с балансом   A, 0< A < 1/2, если оно удовлетворяет следующим условиям: A <= b( T n ) <= 1 - A ; T l, T r  -  балансированные по весу деревья с балансом   A. Определение

Изображение слайда
19

Слайд 19

Класс бинарных деревьев с балансом  A   -   WB[A]. Пустое бинарное дерево  T 0, по определению, входит в  WB[A]  для любого  A. Класс   WB[A]  становится все более ограниченным по мере того, как  A меняется от 0 до 1/2. Случай 1/2 либо левое и правое поддеревья каждой вершины содержат одинаковое число вершин, поэтому классу WB[1/2 ]  принадлежат полностью балансированные деревья с  n=2 k -1  вершинами, Либо см. рисунок

Изображение слайда
20

Слайд 20: Деревья Фибоначчи

Изображение слайда
21

Слайд 21: Теорема

Высота дерева  T n  из класса  WB[A]  не превышает Теорема высота дерева Фибоначчи  не превышает  log 2 (n+1)-1

Изображение слайда
22

Слайд 22: Алгоритмы балансировки

сначала было  h L  = h R. После включения  L  и  R  станут разной высоты, но критерий сбалансированности не будет нарушен; сначала было  h L  < h R. После включения  L  и  R  станут равной высоты, то есть критерий сбалансированности даже улучшится; сначала было  h L  > h R. После включения критерий сбалансированности нарушится и дерево необходимо перестраивать. Алгоритмы балансировки Включение в сбалансированное дерево новой вершины

Изображение слайда
23

Слайд 23

struct node { int Key; int Count; int bal ; // Показатель балансированности вершины. node *Left; node *Right; };

Изображение слайда
24

Слайд 24: Определение

Показатель сбалансированности вершины =   разность между высотой правого и левого поддерева Определение

Изображение слайда
25

Слайд 25

П роход по дереву, чтобы убедиться, что включаемого значения в дереве нет; включение новой вершины и определение результирующего показателя сбалансированности; "отступление" по пути поиска и проверка в каждой вершине показателя сбалансированности. При необходимости - балансировка.

Изображение слайда
26

Слайд 26: Однократный LL- поворот

p1 = (*p).Left; (*p).Left = (*p1).Right; (*p1).Right = p; (*p). bal = 0; p = p1; Однократный LL- поворот

Изображение слайда
27

Слайд 27

LL- поворот 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;

Изображение слайда
28

Слайд 28

Изображение слайда
29

Слайд 29: Сохранение адреса нового корня дерева

p1 = (*p).Left; Сохранение адреса нового корня дерева

Изображение слайда
30

Слайд 30: Переприкрепление

(*p).Left = (*p1).Right; Переприкрепление

Изображение слайда
31

Слайд 31: Определение правого поддерева "нового" корня

(*p1).Right = p; Определение правого поддерева "нового" корня

Изображение слайда
32

Слайд 32: Установка начальных значений

(*p). bal = 0; p = p1; Установка начальных значений

Изображение слайда
33

Слайд 33

Изображение слайда
34

Слайд 34: Однократный RR- поворот

p1 = (*p).Right; (*p).Right = (*p1).Left; (*p1).Left = p; (*p). bal = 0; p = p1; Однократный RR- поворот

Изображение слайда
35

Слайд 35

Изображение слайда
36

Слайд 36: Сохранение адреса нового корня дерева

p1 = (*p).Right; Сохранение адреса нового корня дерева

Изображение слайда
37

Слайд 37: Переприкрепление

(*p).Right = (*p1).Left; Переприкрепление

Изображение слайда
38

Слайд 38: Определение левого поддерева "нового" корня

(*p1).Left = p; Определение левого поддерева "нового" корня

Изображение слайда
39

Слайд 39: Установка начальных значений

(*p). bal = 0; p = p1; Установка начальных значений

Изображение слайда
40

Слайд 40

Изображение слайда
41

Слайд 41

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

Изображение слайда
42

Слайд 42

Изображение слайда
43

Слайд 43: Двукратный LR- поворот

p1 = (*p).Left; p2 = (*p1).Right; (*p1).Right = (*p2).Left; (* p2).Left = p1; (*p).Left = (*p2).Right; (* p2).Right = *p; p = p2; Двукратный LR- поворот

Изображение слайда
44

Слайд 44

Изображение слайда
45

Слайд 45: Определение  p1   и  p2

p1 = (*p).Left; p2 = (*p1).Right; Определение  p1   и  p2

Изображение слайда
46

Слайд 46: Переприкрепление

(*p1).Right = (*p2).Left; Переприкрепление

Изображение слайда
47

Слайд 47: Определение левого поддерева "нового" корня

(*p2).Left = p1; Определение левого поддерева "нового" корня

Изображение слайда
48

Слайд 48: Переприкрепление

(*p).Left = (*p2).Right; Переприкрепление

Изображение слайда
49

Слайд 49: Определение правого поддерева "нового" корня

(*p2).Right = *p; Определение правого поддерева "нового" корня

Изображение слайда
50

Слайд 50: Установка начальных значений

p = p2; Установка начальных значений

Изображение слайда
51

Слайд 51

Изображение слайда
52

Слайд 52: Двукратный RL- поворот

p1 =(*p).Right; p2 = (*p1).Left; (*p1).Left = (*p2). Right; (*p2). Right = p1; (*p).Right = (*p2). Left; (*p2). Left = *p; p = p2; Двукратный RL- поворот

Изображение слайда
53

Слайд 53

Изображение слайда
54

Слайд 54: Определение  p1   и  p2

p1 = (*p).Right; p2 = (*p1).Left; Определение  p1   и  p2

Изображение слайда
55

Слайд 55: Переприкрепление

(*p1).Left = (*p2). Right; Переприкрепление

Изображение слайда
56

Слайд 56: Определение правого поддерева "нового" корня

(*p2). Right = p1; Определение правого поддерева "нового" корня

Изображение слайда
57

Слайд 57: Переприкрепление

(*p).Right = (*p2). Left ; Переприкрепление

Изображение слайда
58

Слайд 58: Определение правого поддерева "нового" корня

( * p2). Left = *p; Определение правого поддерева "нового" корня

Изображение слайда
59

Слайд 59: Установка начальных значений

p = p2; Установка начальных значений

Изображение слайда
60

Слайд 60

Изображение слайда
61

Слайд 61

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

Изображение слайда
62

Слайд 62

Изображение слайда
63

Слайд 63: Построение AVL дерева

Изображение слайда
64

Последний слайд презентации: Деревья 2

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 /

Изображение слайда