Презентация Удаление вершин из АВЛ-дерева онлайн
На нашем сайте вы можете скачать и просмотреть онлайн доклад-презентацию на тему Удаление вершин из АВЛ-дерева абсолютно бесплатно. Урок-презентация на эту тему содержит всего 14 слайдов. Все материалы созданы в программе PowerPoint и имеют формат ppt или же pptx. Материалы и темы для презентаций взяты из открытых источников и загружены их авторами, за качество и достоверность информации в них администрация сайта не отвечает, все права принадлежат их создателям. Если вы нашли то, что искали, отблагодарите авторов - поделитесь ссылкой в социальных сетях, а наш сайт добавьте в закладки.
Оцените презентацию от 1 до 5 баллов!
- Тип файла:ppt / pptx (powerpoint)
- Всего слайдов:14 слайдов
- Для класса:1,2,3,4,5,6,7,8,9,10,11
- Размер файла:113.38 kB
- Просмотров:50
- Скачиваний:0
- Автор:неизвестен
Слайды и текст к этой презентации:
№1 слайд
Содержание слайда: Удаление вершин из АВЛ-дерева
Процесс немного более сложный, чем добавление.
Хотя алгоритм операции балансировки остается тем же, что и при включении вершин.
Балансировка по-прежнему выполняется с помощью одного из четырех поворотов вершин:
LL, LR, RL, RR.
№2 слайд
Содержание слайда: Если при добавлении вершины название поворота определяется путем от вершины в которой нарушен баланс, к добавленной, то при удалении картина симметрична.
Если при добавлении вершины название поворота определяется путем от вершины в которой нарушен баланс, к добавленной, то при удалении картина симметрична.
Если удалена вершина из левого поддерева, потребуется один из правых поворотов
( RR или RL ),
а при удалении из правого поддерева потребуется один из левых поворотов
( LL или LR ).
№3 слайд
Содержание слайда: Идея алгоритма:
Удаляем вершину так же, как это делалось для случайного дерева поиска (СДП);
Двигаясь назад по пути поиска от удаленной вершины к корню дерева, будем пересчитывать баланс каждой вершины и при необходимости восстанавливать с помощью поворотов.
Нарушение баланса возможно в нескольких вершинах, в худшем случае - во всех вершинах по пути поиска.
№4 слайд
Содержание слайда: Если удаляемая вершина не имеет поддеревьев:
Если удаляемая вершина не имеет поддеревьев:
Если на удаляемой вершине одно поддерево:
Если вершина имеет два поддерева:
№5 слайд
Содержание слайда: Правила удаления:
а) На место удаляемой вершины ставится наибольшая вершина из её левого поддерева, т.е. самая правая вершина из левого поддерева, не имеющая правого поддерева.
б) На место удаляемой вершины ставится наименьшая вершина из её правого поддерева, т.е. самая левая вершина из её правого поддерева, не имеющая левого поддерева.
Будем строить алгоритмы на правиле «а»
№6 слайд
Содержание слайда: Как и в случае добавления вершин, введем логическую переменную Умен, показывающую, уменьшилась ли высота поддерева.
Как и в случае добавления вершин, введем логическую переменную Умен, показывающую, уменьшилась ли высота поддерева.
Балансировка производится только, когда Умен=истина. Это значение присваивается, если:
1. Обнаружена и удалена вершина;
2. Уменьшилась высота в ходе балансировки.
Введем две симметричные процедуры балансировки:
BL – при удалении из левого поддерева,
BR – при удалении из правого поддерева.
№7 слайд
Содержание слайда: 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 *&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 слайд
Содержание слайда: При добавлении вершины не может быть случая,
При добавлении вершины не может быть случая,
когда 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 *&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 удаляет вершину, имеющую два поддерева, т.е. заменяет ее на самую большую (правую) вершину из левого поддерева.
Функция 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 слайд
Содержание слайда: Замечание: «По экспериментальным оценкам на каждые два включения встречается один поворот, а при исключении поворот происходит в одном случае из пяти». Н.Вирт.
Замечание: «По экспериментальным оценкам на каждые два включения встречается один поворот, а при исключении поворот происходит в одном случае из пяти». Н.Вирт.
№13 слайд
Содержание слайда: Трудоемкость работы с АВЛ-деревьями
Поиск элемента с заданным ключом, включение элемента, удаление элемента – все операции производятся в худшем случае за O(log2n) операций сравнения.
Отличия между процедурой включения и удаления: включение может привести самое большое к одному повороту, а удаление может потребовать повороты во всех вершинах по пути поиска.
Наихудший случай с точки зрения количества поворотов – удаление самой правой вершины у плохого АВЛ-дерева (дерева Фибоначчи).
№14 слайд
Содержание слайда: Т5 : Н=5
Т5 : Н=5
Скачать все slide презентации Удаление вершин из АВЛ-дерева одним архивом:
