двигаясь влево или вправо по пути поиска, пока не остановимся на вершине с ключом Х или пока не достигнем листовой вершины с нулевыми указателями.
Поиск в дереве не осуществляется перебором (обходом).
Обходом осуществляется лишь распечатка вершин.
- Главная
- Разное
- Дизайн
- Бизнес и предпринимательство
- Аналитика
- Образование
- Развлечения
- Красота и здоровье
- Финансы
- Государство
- Путешествия
- Спорт
- Недвижимость
- Армия
- Графика
- Культурология
- Еда и кулинария
- Лингвистика
- Английский язык
- Астрономия
- Алгебра
- Биология
- География
- Детские презентации
- Информатика
- История
- Литература
- Маркетинг
- Математика
- Медицина
- Менеджмент
- Музыка
- МХК
- Немецкий язык
- ОБЖ
- Обществознание
- Окружающий мир
- Педагогика
- Русский язык
- Технология
- Физика
- Философия
- Химия
- Шаблоны, картинки для презентаций
- Экология
- Экономика
- Юриспруденция
Удаление вершин из СДП презентация
Содержание
- 1. Удаление вершин из СДП
- 2. Если удаляемая вершина не имеет поддеревьев:
- 3. Из этого дерева нужно удалить вершину 5,
- 4. Правила удаления: а) На место удаляемой вершины
- 5. B 9 2 4
- 6. B 9 2 4
- 7. B 9 2 4
- 8. B 9 2 4
- 9. B 9 2 4
- 10. B 9 2 4
- 11. B 9 2 4
- 12. B 9 2 4
- 13. B 9 2 4
- 14. B 9 2 4
- 15. B 9 2 4
- 16. B 9 2 4
- 17. B 9 2 4
- 18. p - адрес адреса удаляемой вершины q
- 19. Удаление ( D, *Root) p=&Root
- 20. IF (r-->Right = NULL)
Если удаляемая вершина не имеет поддеревьев: Если на удаляемой вершине одно поддерево: Если вершина имеет два поддерева:
Слайд 2Если удаляемая вершина не имеет поддеревьев:
Если на удаляемой вершине одно поддерево:
Если
вершина имеет два поддерева:
Слайд 4Правила удаления:
а) На место удаляемой вершины ставится наибольшая вершина из её
левого поддерева, т.е. самая правая вершина из левого поддерева, не имеющая правого поддерева.
б) На место удаляемой вершины ставится наименьшая вершина из её правого поддерева, т.е. самая левая вершина из её правого поддерева, не имеющая левого поддерева.
Будем строить алгоритмы на правиле «а»
б) На место удаляемой вершины ставится наименьшая вершина из её правого поддерева, т.е. самая левая вершина из её правого поддерева, не имеющая левого поддерева.
Будем строить алгоритмы на правиле «а»
Слайд 19Удаление ( D, *Root)
p=&Root
DO (*p ≠ NULL) //
поиск элемента
IF (D<(*p)-->Data) p:=&((*p)-->Left)
ELSE IF (D>((*p)-->Data) p:=&((*p)-->Right)
ELSE OD {данные есть в дереве}
FI
OD
IF (*p ≠ NULL)
q:=*p
IF (q-->Left=NULL ) *p:=q-->Right;
ELSE IF (q-->Right=NULL ) *p:=q-->Left;
ELSE /*2 поддерева*/
r:=q-->Left ; S:=q;
IF (D<(*p)-->Data) p:=&((*p)-->Left)
ELSE IF (D>((*p)-->Data) p:=&((*p)-->Right)
ELSE OD {данные есть в дереве}
FI
OD
IF (*p ≠ NULL)
q:=*p
IF (q-->Left=NULL ) *p:=q-->Right;
ELSE IF (q-->Right=NULL ) *p:=q-->Left;
ELSE /*2 поддерева*/
r:=q-->Left ; S:=q;
Слайд 20 IF (r-->Right = NULL)
r-->Right:= q-->Right ; (3)
*p:=r; (4)
ELSE
DO (r-->Right ≠ NULL)
S:=r; r:=r-->Right ;
OD
s-->Right:=r-->Right; (1)
r-->Left:=q-->Left; (2)
r-->Right:=q-->Right; (3)
*p:=r; (4)
FI
FI
free(q)
FI
*p:=r; (4)
ELSE
DO (r-->Right ≠ NULL)
S:=r; r:=r-->Right ;
OD
s-->Right:=r-->Right; (1)
r-->Left:=q-->Left; (2)
r-->Right:=q-->Right; (3)
*p:=r; (4)
FI
FI
free(q)
FI
p
q
r
4
3
