Оцените презентацию от 1 до 5 баллов!
Тип файла:
ppt / pptx (powerpoint)
Всего слайдов:
14 слайдов
Для класса:
1,2,3,4,5,6,7,8,9,10,11
Размер файла:
113.38 kB
Просмотров:
50
Скачиваний:
0
Автор:
неизвестен
Слайды и текст к этой презентации:
№1 слайд![Удаление вершин из АВЛ-дерева](/documents_6/21c0c8a7ac8294becc4c1625d34d4194/img0.jpg)
Содержание слайда: Удаление вершин из АВЛ-дерева
Процесс немного более сложный, чем добавление.
Хотя алгоритм операции балансировки остается тем же, что и при включении вершин.
Балансировка по-прежнему выполняется с помощью одного из четырех поворотов вершин:
LL, LR, RL, RR.
№2 слайд![Если при добавлении вершины](/documents_6/21c0c8a7ac8294becc4c1625d34d4194/img1.jpg)
Содержание слайда: Если при добавлении вершины название поворота определяется путем от вершины в которой нарушен баланс, к добавленной, то при удалении картина симметрична.
Если при добавлении вершины название поворота определяется путем от вершины в которой нарушен баланс, к добавленной, то при удалении картина симметрична.
Если удалена вершина из левого поддерева, потребуется один из правых поворотов
( RR или RL ),
а при удалении из правого поддерева потребуется один из левых поворотов
( LL или LR ).
№3 слайд![Идея алгоритма Удаляем](/documents_6/21c0c8a7ac8294becc4c1625d34d4194/img2.jpg)
Содержание слайда: Идея алгоритма:
Удаляем вершину так же, как это делалось для случайного дерева поиска (СДП);
Двигаясь назад по пути поиска от удаленной вершины к корню дерева, будем пересчитывать баланс каждой вершины и при необходимости восстанавливать с помощью поворотов.
Нарушение баланса возможно в нескольких вершинах, в худшем случае - во всех вершинах по пути поиска.
№4 слайд![Если удаляемая вершина не](/documents_6/21c0c8a7ac8294becc4c1625d34d4194/img3.jpg)
Содержание слайда: Если удаляемая вершина не имеет поддеревьев:
Если удаляемая вершина не имеет поддеревьев:
Если на удаляемой вершине одно поддерево:
Если вершина имеет два поддерева:
№5 слайд![Правила удаления а На место](/documents_6/21c0c8a7ac8294becc4c1625d34d4194/img4.jpg)
Содержание слайда: Правила удаления:
а) На место удаляемой вершины ставится наибольшая вершина из её левого поддерева, т.е. самая правая вершина из левого поддерева, не имеющая правого поддерева.
б) На место удаляемой вершины ставится наименьшая вершина из её правого поддерева, т.е. самая левая вершина из её правого поддерева, не имеющая левого поддерева.
Будем строить алгоритмы на правиле «а»
№6 слайд![Как и в случае добавления](/documents_6/21c0c8a7ac8294becc4c1625d34d4194/img5.jpg)
Содержание слайда: Как и в случае добавления вершин, введем логическую переменную Умен, показывающую, уменьшилась ли высота поддерева.
Как и в случае добавления вершин, введем логическую переменную Умен, показывающую, уменьшилась ли высота поддерева.
Балансировка производится только, когда Умен=истина. Это значение присваивается, если:
1. Обнаружена и удалена вершина;
2. Уменьшилась высота в ходе балансировки.
Введем две симметричные процедуры балансировки:
BL – при удалении из левого поддерева,
BR – при удалении из правого поддерева.
№7 слайд![BL Vertex amp p BL Vertex amp](/documents_6/21c0c8a7ac8294becc4c1625d34d4194/img6.jpg)
Содержание слайда: BL ( Vertex *&p )
BL ( Vertex *&p )
IF(p-->Bal = -1) p-->Bal = 0
ELSE IF(p-->Bal = 0) p->Bal = 1, умен=нет
ELSE IF (p-->Bal = 1)
IF (p-->Right-->Bal >= 0) <RR1-поворот>
ELSE <RL-поворот>
FI
FI
FI
№8 слайд![BR Vertex amp p BR Vertex amp](/documents_6/21c0c8a7ac8294becc4c1625d34d4194/img7.jpg)
Содержание слайда: BR ( Vertex *&p )
BR ( Vertex *&p )
IF (p-->Bal = 1) p-->Bal = 0
ELSE IF (p-->Bal = 0) p-->Bal = -1, умен=нет
ELSE IF (p-->Bal = -1)
IF (p-->Left-->Bal <= 0) <LL1-поворот>
ELSE <LR-поворот>
FI
FI
FI
№9 слайд![При добавлении вершины не](/documents_6/21c0c8a7ac8294becc4c1625d34d4194/img8.jpg)
Содержание слайда: При добавлении вершины не может быть случая,
При добавлении вершины не может быть случая,
когда p-->Left-->Bal = 0 или p-->Right-->Bal = 0.
Чтобы учесть эти случаи, LL-поворот необходимо изменить на LL1-поворот, а RR-поворот – на RR1-поворот .
LL1-поворот
q = p-->Left
IF (q-->Bal = 0) q-->Bal = 1, p-->Bal = -1, Умен = нет
ELSE q-->Bal = 0, p-->Bal = 0
FI
p-->Left = q-->Right
q-->Right = p
p = q
Аналогично изменяется RR-поворот на RR1-поворот, повороты LR и RL – не изменяются.
№10 слайд![DELETE x, vertex amp p DELETE](/documents_6/21c0c8a7ac8294becc4c1625d34d4194/img9.jpg)
Содержание слайда: DELETE (x, vertex *&p)
DELETE (x, vertex *&p)
IF (p = NULL)
ELSE IF (x < p-->Data) DELETE (x, p-->Left)
IF Умен=да BL(p) FI
ELSE IF (x > p-->Data) DELETE (x, p-->Right)
IF Умен=да BR(p) FI
ELSE q = p
IF (q-->Left = NULL) p = q-->Right, Умен=да
ELSE IF (q-->Right = NULL) p = q-->Left, Умен=да
ELSE del (q-->Left)
IF Умен=да BL(p) FI
FI
free(q)
FI
№11 слайд![Функция del удаляет вершину,](/documents_6/21c0c8a7ac8294becc4c1625d34d4194/img10.jpg)
Содержание слайда: Функция del удаляет вершину, имеющую два поддерева, т.е. заменяет ее на самую большую (правую) вершину из левого поддерева.
Функция del удаляет вершину, имеющую два поддерева, т.е. заменяет ее на самую большую (правую) вершину из левого поддерева.
del (vertex *&r)
IF (r-->Right != NULL) del (r->Right)
IF Умен=да BR(r) FI
ELSE q-->Data = r-->Data
q = r
r = r-->Left
Умен = да
FI
№12 слайд![Замечание По](/documents_6/21c0c8a7ac8294becc4c1625d34d4194/img11.jpg)
Содержание слайда: Замечание: «По экспериментальным оценкам на каждые два включения встречается один поворот, а при исключении поворот происходит в одном случае из пяти». Н.Вирт.
Замечание: «По экспериментальным оценкам на каждые два включения встречается один поворот, а при исключении поворот происходит в одном случае из пяти». Н.Вирт.
№13 слайд![Трудоемкость работы с](/documents_6/21c0c8a7ac8294becc4c1625d34d4194/img12.jpg)
Содержание слайда: Трудоемкость работы с АВЛ-деревьями
Поиск элемента с заданным ключом, включение элемента, удаление элемента – все операции производятся в худшем случае за O(log2n) операций сравнения.
Отличия между процедурой включения и удаления: включение может привести самое большое к одному повороту, а удаление может потребовать повороты во всех вершинах по пути поиска.
Наихудший случай с точки зрения количества поворотов – удаление самой правой вершины у плохого АВЛ-дерева (дерева Фибоначчи).
№14 слайд![Т Н Т Н](/documents_6/21c0c8a7ac8294becc4c1625d34d4194/img13.jpg)
Содержание слайда: Т5 : Н=5
Т5 : Н=5