Глава 2. Деревья. Тема 2. Двоичное дерево поиска презентация

Содержание

Слайд 2

Определение двоичного дерева поиска
Двоичное дерево называется деревом поиска, если для каждого узла дерева

выполняется условие:
значение ключа в узле больше значений ключей в левом поддереве и меньше значений ключей в правом поддереве

Определение двоичного дерева поиска Двоичное дерево называется деревом поиска, если для каждого узла

Слайд 3

Пример дерева поиска

У всех узлов правого  поддерева произвольного узла X значения ключей данных больше, нежели значение

ключа данных самого узла X

У всех узлов левого  поддерева произвольного узла X значения ключей данных меньше, нежели значение ключа данных самого узла X.

50

70

60

90

20

30

25

10

5

15

40

35

45

<

<

<

<

<

<

<

<

<

<

<

<

Пример дерева поиска У всех узлов правого поддерева произвольного узла X значения ключей

Слайд 4

Операции над деревьями поиска

Основные операции при работе с деревьями поиска не отличаются от

обычного двоичного дерева:
Добавление узла
Удаление узла
Поиск узла
Обход узлов
Главное требование при выполнении этих операций – сохранение указанного выше свойства двоичного дерева поиска:
значение ключа в узле больше значений ключей в левом поддереве и меньше значений ключей в правом поддереве

Операции над деревьями поиска Основные операции при работе с деревьями поиска не отличаются

Слайд 5

Добавление узла в дерево поиска

Если корень поддерева пуст, поместить в него заданный ключ;

закончить алгоритм.
Если новый ключ меньше ключа корня: перейти в левое поддерево и повторить с п.1.
Иначе, перейти в правое поддерево и повторить с п.1.
Замечание: при равенстве ключей в зависимости от конкретной задачи можно либо выйти и не помещать такое же значение, либо поместить, переходя, например, вправо (как будет далее).

Добавление узла в дерево поиска Если корень поддерева пуст, поместить в него заданный

Слайд 6

Добавление узла в дерево поиска

//ToDo: сделать метод родителя виртуальным
Node *addNode(Node *root, int key)

override
{
if (!root) {
root = new Node(key);
} else if (key < root->key()) {
root->setLeftChild(addNode(root->leftChild(), key));
} else {
root->setRightChild(addNode(root->rightChild(), key));
}
return root;
}

Добавление узла в дерево поиска //ToDo: сделать метод родителя виртуальным Node *addNode(Node *root,

Слайд 7

Добавление узла в дерево поиска

if (!root) {
root = new Node(key);
} else if

(root->key() < key) {
root->setLeftChild(addNode(root->leftChild(), key));
} else {
root->setRightChild(addNode(root->rightChild(), key));
}

50

70

60

90

20

30

10

<

<

<

<

<

<

50, 70, 60, 20, 30, 90, 10

Добавление узла в дерево поиска if (!root) { root = new Node(key); }

Слайд 8

Добавление узла в дерево поиска

Задание: расставьте числа 10 20 30 40 50 в

следующие деревья поиска:

50

10

40

20

30

<

<

<

<

10

50

20

40

30

<

<

<

<

30

10

20

40

50

<

<

<

<

Добавление узла в дерево поиска Задание: расставьте числа 10 20 30 40 50

Слайд 9

Поиск узла в дереве поиска

50

70

60

90

20

30

10

5

15

40

35

45

<

<

<

<

<

<

<

<

<

<

<

Node *findNode(Node *root, int key)

key = 40

if

(root->key() == key) {
return root;
}

Поиск узла в дереве поиска 50 70 60 90 20 30 10 5

Слайд 10

Поиск узла в дереве поиска

50

70

60

90

20

30

10

5

15

40

35

45

<

<

<

<

<

<

<

<

<

<

<

Node *findNode(Node *root, int key)

key = 25

if

(root == nullptr) {
return nullptr;
}

<

Поиск узла в дереве поиска 50 70 60 90 20 30 10 5

Слайд 11

Удаление узла из дерева поиска

Аналогично двоичному дереву, при удалении узла из дерева поиска

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

Удаление узла из дерева поиска Аналогично двоичному дереву, при удалении узла из дерева

Слайд 12

Удаление узла из дерева поиска

50

70

60

90

20

30

10

5

15

40

35

45

<

<

<

<

<

<

<

<

<

<

<

bool removeNode(Node *root, int key)

key = 25

Не

забудьте почистить указатель на потомка у родителя удаляемого узла!

<

25

Удаление узла из дерева поиска 50 70 60 90 20 30 10 5

Слайд 13

Удаление узла из дерева поиска

50

70

60

90

20

30

10

5

15

40

35

45

<

<

<

<

<

<

<

<

<

<

<

bool removeNode(Node *root, int key)

key = 30

После удаления

узла 30 и проведения связи 20 - 40 это всё ещё дерево поиска!

Удаление узла из дерева поиска 50 70 60 90 20 30 10 5

Слайд 14

Удаление узла из дерева поиска

50

70

60

90

20

30

10

5

15

40

35

45

<

<

<

<

<

<

<

<

<

<

<

bool removeNode(Node *root, int key)

key = 50, до

удаления

Больше любого ключа в левом поддереве и меньше остальных в правом

Меньше любого ключа в правом поддереве и больше остальных в левом

Удаление узла из дерева поиска 50 70 60 90 20 30 10 5

Слайд 15

Удаление узла из дерева поиска

60

70

90

20

30

10

5

15

40

35

45

<

<

<

<

<

<

<

<

<

<

bool removeNode(Node *root, int key)

key = 50, замена

на минимум из правого поддерева

Удаление узла из дерева поиска 60 70 90 20 30 10 5 15

Слайд 16

Удаление узла из дерева поиска

45

70

60

90

20

30

10

5

15

40

35

<

<

<

<

<

<

<

<

<

<

bool removeNode(Node *root, int key)

key = 50, замена

на максимум левого поддерева

Удаление узла из дерева поиска 45 70 60 90 20 30 10 5

Слайд 17

Удаление узла из дерева поиска

50

70

60

90

20

30

10

5

15

40

35

<

<

<

<

<

<

<

<

<

<

bool removeNode(Node *root, int key)

key = 50, до

удаления

Меньше любого ключа в правом поддереве и больше остальных в левом

Пример с заменой не на лист

Перед заменой узла найденным передаём его потомка (а он точно будет один) родителю

Удаление узла из дерева поиска 50 70 60 90 20 30 10 5

Слайд 18

Удаление узла из дерева поиска

40

70

60

90

20

30

10

5

15

35

<

<

<

<

<

<

<

<

<

bool removeNode(Node *root, int key)

key = 50, замена

на максимум левого поддерева

Поддерево узла 40 теперь наследник его прежнего родителя (30)

Удаление узла из дерева поиска 40 70 60 90 20 30 10 5

Слайд 19

Удаление узла из дерева поиска

Алгоритм определения узла r, который заменит удаляемый узел n:
Тривиальные

случаи: у n есть только один потомок. Тогда r равен этому потомку. Алгоритм окончен, дополнительных действий не требуется.
Спуск по правой ветви: r = n->rightChild().
Если r->leftChild() == nullptr, замена найдена. Установить левого потомка n в качестве левого потомка r. Алгоритм окончен.
Поиск в поддереве с корнем r->leftChild() узла, у которого нет левого потомка (далее r указывает на найденный узел, rp указывает на его родителя).
Передаём правое поддерево узла r его родителю: rp->setLeftChild(r->rightChild());
Передаём потомков узла n узлу r. Алгоритм окончен.
Всё, что останется для завершения удаления – заменить n на r в родителе n и очистить память n.

Удаление узла из дерева поиска Алгоритм определения узла r, который заменит удаляемый узел

Слайд 20

Удаление узла из дерева поиска

Замечание: аналогично можно выполнить удаление ключа, спускаясь по левой

ветви от n и найдя самый правый узел (с пустым правым потомком), т.е. поиск наиболее близкого ключа с меньшим значением, чем n->key(). Далее выполнить симметричные действия.
Замечание 2: т.к. при поиске потомка спуск всегда происходит только по одной ветви (левой/правой), он легко реализуется обычным циклом.

Удаление узла из дерева поиска Замечание: аналогично можно выполнить удаление ключа, спускаясь по

Слайд 21

Использование функции удаления

Пусть функция удаления узла имеет сигнатуру:
Node *removeNode(Node *node)
И удаляет переданный узел,

возвращая указатель на узел, который его заменил.
Как применить эту функцию для удаления всех узлов с чётными ключами из поддерева?

Использование функции удаления Пусть функция удаления узла имеет сигнатуру: Node *removeNode(Node *node) И

Слайд 22

Использование функции удаления

Node *removeEvenNodes(Node *root)
{
if (root == nullptr) {
return nullptr;
}

root->setLeftChild(removeEvenNodes(root->leftChild()));
root->setRightChild(removeEvenNodes(root->rightChild()));
if (root->key() % 2 == 0) {
return removeNode(root);
}
return root;
}

Использование функции удаления Node *removeEvenNodes(Node *root) { if (root == nullptr) { return

Слайд 23

Использование функции удаления

46

35

82

56

93

95

91

47

49

<

<

<

<

<

<

<

<

<

30

17

26

15

<

<

<

57

<

root

Использование функции удаления 46 35 82 56 93 95 91 47 49 30

Слайд 24

Использование функции удаления

46

35

82

56

93

95

91

47

49

<

<

<

<

<

<

<

<

<

30

17

26

15

<

<

<

57

<

root

Спустя три рекурсивных вызова, один возврат и ещё один рекурсивный вызов

будет удалена первая из вершин

Использование функции удаления 46 35 82 56 93 95 91 47 49 30

Слайд 25

Использование функции удаления

46

35

82

56

93

95

91

47

49

<

<

<

<

<

<

<

<

<

30

17

15

<

<

57

<

root

r

Эта связь будет установлена после возврата в вызвавшую функцию

Использование функции удаления 46 35 82 56 93 95 91 47 49 30

Слайд 26

Использование функции удаления

46

82

56

93

95

91

47

49

<

<

<

<

<

<

<

<

35

17

15

<

<

57

<

root

r

Эта связь будет установлена после возврата в вызвавшую функцию

Использование функции удаления 46 82 56 93 95 91 47 49 35 17

Слайд 27

Использование функции удаления

46

82

57

93

95

91

47

49

<

<

<

<

<

<

<

<

35

17

15

<

<

rp

root

r

Эта связь будет установлена после возврата в вызвавшую функцию

Использование функции удаления 46 82 57 93 95 91 47 49 35 17

Слайд 28

Использование функции удаления

46

91

57

93

95

47

49

<

<

<

<

<

<

<

35

17

15

<

<

rp

root

r

<

Использование функции удаления 46 91 57 93 95 47 49 35 17 15 rp root r

Слайд 29

Использование функции удаления

47

91

57

93

95

49

<

<

<

<

<

<

35

17

15

<

<

<

Выход из функции

Использование функции удаления 47 91 57 93 95 49 35 17 15 Выход из функции

Слайд 30

Обход дерева поиска

Обход дерева поиска может выполняться по тем же правилам, что и

обход любого двоичного дерева:
К-Л-П, К-П-Л, Л-К-П, П-К-Л, Л-П-К, по уровням.
Рассмотрим обход Л-К-П для дерева поиска.

Обход дерева поиска Обход дерева поиска может выполняться по тем же правилам, что

Слайд 31

Л-К-П обход дерева поиска

При Л-К-П обходе дерева поиска узлы будут перебираться по возрастанию

ключей:
15, 17, 26, 30, 35, 46, 47, 56, 57, 82, 91, 93, 95
Такой обход называется симметричным.

46

35

82

56

93

95

91

47

<

<

<

<

<

<

<

<

30

17

26

15

<

<

<

57

<

Л-К-П обход дерева поиска При Л-К-П обходе дерева поиска узлы будут перебираться по

Слайд 32

Л-К-П обход дерева поиска
//Пример реализации обхода
//Вместо вывода в этот раз складываем ключи узлов

в вектор
void SearchTree::lnrKeys(Node *root, std::vector &keys) const
{
if (!root) {
return;
}
lnrPrint(root->leftChild());
keys->push_back(root->key());
lnrPrint(root->rightChild());
}

Л-К-П обход дерева поиска //Пример реализации обхода //Вместо вывода в этот раз складываем

Слайд 33

Дерево поиска для символьных данных

Дерево поиска может быть построено и для символьных /

текстовых данных:

Николай

Дмитрий

Екатерина

Андрей

Александр

Артём

Илья

<

<

<

<

<

<

<

Павел

Сергей

Роман

Татьяна

<

<

<

Евгений

<

Дерево поиска для символьных данных Дерево поиска может быть построено и для символьных

Имя файла: Глава-2.-Деревья.-Тема-2.-Двоичное-дерево-поиска.pptx
Количество просмотров: 13
Количество скачиваний: 0
- Предыдущая
Происхождение славян. Восточные славяне в древности
Следующая -
Равновесия в растворах электролитов

Похожие презентации

Нововведения в Windows 7
Security Monitoring
The Pochinov platform
Редизайн сайта. Невельский историко - краеведческий музей
Профилактика интернет - зависимости. Программа профилактики зависимости от социальных сетей
Instructions for use edit in google slides
Персональные компьютеры
Системы программного управления промышленными установками
Архитектура ORACLE. Процессы и потоки Windows (Лекция 6)
Компьютерные коммуникации. ЛВС. Топологии сетей. Сеть интернет. Сервисы интернета
Рекурсия
Introduction to CFX. Workshop 3 Room Temperature Study
Скрипты и механика акции. Газпромнефть. Сентябрь
Порядок регистрации в ЕСИА
Электронные системы тестирования
Отображение данных из нескольких таблиц
Информационные системы. Базы данных
Создание зубчатых передач на Компас 3D
Безопасный интернет
Характеристика и типы линий связи
Гид-навигатор. Организационно-методическое отделение
Вложеные циклы
Рефлексія та атрибути. Лекція №4
Истинность высказываний. Логические операции
Файлдық жүйелер мен ДҚБЖ арасындағы негізгі айырмашылық
Продвижение некоммерческого проекта в социальных сетях
ВКР: Разработка информационной системы управления заявками клиентов в магазине бытовой техники и электроники
Інтернет-ресурси та інтернет-технології у роботі сучасної бібліотеки
Обратная связь
Email: Нажмите что бы посмотреть