- Бинарные поисковые деревья
Содержание
- 2. Словарные операции поиск элемента с заданным ключом х добавление нового элемента с заданным ключом х удаление
- 3. Бинарное поисковое дерево Поисковое 5. Каждой вершине поставлено в соответствие некоторое целое число - ключ. Для
- 4. 10 18 23 21 22 20 19 11 13 14 17 3 4 6 8 9
- 5. 10 18 23 21 22 20 19 11 13 14 17 3 4 6 8 9
- 6. 10 18 23 21 22 20 19 11 13 14 17 3 4 6 8 9
- 7. Для полупути снимается ограничение на направление дуг. Пример полупути, соединяющего вершины 1 и 7: 1 -
- 8. Центральная вершина полупути - такая вершина, что количество вершин в полупути до неё равно количеству вершин
- 9. 10 18 23 21 22 20 19 11 13 14 17 6 8 9 2 Наибольшим
- 10. 10 18 23 21 22 20 19 11 13 14 17 3 4 6 8 9
- 11. прямой (левый, правый) - PreOrderTraversal (v) ФПМИ БГУ Обходы обратный (левый, правый) - PostOrderTraversal (v) внутренний
- 12. 10 18 23 21 22 20 19 11 13 14 17 3 4 6 8 9
- 13. 10 18 23 21 22 20 19 11 13 14 17 3 4 6 8 9
- 14. 10 18 23 21 22 20 19 11 13 14 17 3 4 6 8 9
- 15. ФПМИ БГУ Примеры задач Найти высоту дерева. Определить, является ли дерево сбалансированнным по высоте. Найти длину
- 16. 7 0 0 1 3 4 3 2 0 0 1 1 Обратный левый (или правый)
- 17. 0 0 1 0 1 2 3 0 1 2 4 5 6 7 3 10
- 18. 0 1 0 0 0 1 2 3 1 2 4 5 6 7 3 0
- 19. 1 2 1 1 1 2 3 4 3 4 10 13 14 15 5 если
- 20. 1 2 3 4 5 6 7 8 Выполнить любой обход дерева и подсчитать число вершин
- 21. Сначала обратным обходом расставить вершинам метки высот. Во время этого же обхода подсчитать количество вершин, у
- 22. m i a t u s b p f вершина t является средней по значению f
- 23. Удаление вершины ФПМИ БГУ Случай 1. Удаляется лист. Случай 2. Удаляется вершина, у которой есть только
- 24. ФПМИ БГУ Случай 1. Удаляется лист.
- 25. ФПМИ БГУ Случай 2. Удаляется вершина, у которой есть только одно поддерево.
- 26. ФПМИ БГУ Случай 2. Удаляется вершина, у которой есть только одно поддерево
- 27. 10 18 23 21 22 20 19 11 13 14 17 6 8 9 2 правое
- 28. 10 18 23 21 22 20 19 11 13 14 17 6 8 9 2 левое
- 29. !!! Если у удаляемой вершины только одно поддерево, то НЕТ ПОНЯТИЯ ПРАВОЕ/ЛЕВОЕ удаление. Удаление всегда выполняется
- 30. Оценки числа операций в худшем случае 10 18 19 6 2 построение дерева для последовательности из
- 31. Сборник задач по теории алгоритмов : учеб.-метод. пособие / В.М. Котов, Ю.Л. Орлович, Е.П. Соболевская, С.А.
- 33. Скачать презентацию
Словарные операции
поиск элемента с заданным ключом х
добавление нового элемента с заданным
Словарные операции
поиск элемента с заданным ключом х
добавление нового элемента с заданным
Бинарное поисковое дерево
Поисковое
5. Каждой вершине поставлено в соответствие некоторое целое число
Бинарное поисковое дерево
Поисковое
5. Каждой вершине поставлено в соответствие некоторое целое число
10
18
23
21
22
20
19
11
13
14
17
3
4
6
8
9
7
2
1
Построить бинарное поисковое дерево для последовательности элементов последовательным добавлением нового элемента:
10
18
23
21
22
20
19
11
13
14
17
3
4
6
8
9
7
2
1
Построить бинарное поисковое дерево для последовательности элементов последовательным добавлением нового элемента:
10
18
23
21
22
20
19
11
13
14
17
3
4
6
8
9
7
2
1
ФПМИ БГУ
6
??? добавить
так как мы договорились (см. определение) , что
10
18
23
21
22
20
19
11
13
14
17
3
4
6
8
9
7
2
1
ФПМИ БГУ
6
??? добавить
так как мы договорились (см. определение) , что
10
18
23
21
22
20
19
11
13
14
17
3
4
6
8
9
7
2
1
Высота вершины: длина наибольшего пути от вершины до одного из её
10
18
23
21
22
20
19
11
13
14
17
3
4
6
8
9
7
2
1
Высота вершины: длина наибольшего пути от вершины до одного из её
Для полупути снимается ограничение на направление дуг.
Пример полупути, соединяющего вершины 1
Для полупути снимается ограничение на направление дуг.
Пример полупути, соединяющего вершины 1
Центральная вершина полупути -
такая вершина, что количество вершин в полупути до
Центральная вершина полупути -
такая вершина, что количество вершин в полупути до
10
18
23
21
22
20
19
11
13
14
17
6
8
9
2
Наибольшим полупутём в дереве будем называть полупуть наибольшей длины (напомним, что
10
18
23
21
22
20
19
11
13
14
17
6
8
9
2
Наибольшим полупутём в дереве будем называть полупуть наибольшей длины (напомним, что
10
18
23
21
22
20
19
11
13
14
17
3
4
6
8
9
2
10
18
23
21
22
20
19
11
13
14
17
3
4
6
8
9
2
Пример.
1) Длина наибольшего полупути?
2) Какие вершины являются корнями полупутей
10
18
23
21
22
20
19
11
13
14
17
3
4
6
8
9
2
10
18
23
21
22
20
19
11
13
14
17
3
4
6
8
9
2
Пример.
1) Длина наибольшего полупути?
2) Какие вершины являются корнями полупутей
прямой (левый, правый) - PreOrderTraversal (v)
ФПМИ БГУ
Обходы
обратный (левый, правый) - PostOrderTraversal
прямой (левый, правый) - PreOrderTraversal (v)
ФПМИ БГУ
Обходы
обратный (левый, правый) - PostOrderTraversal
10
18
23
21
22
20
19
11
13
14
17
3
4
6
8
9
2
1
7
прямой левый обход
def PreOrderTraversal (v):
if v is not None:
Action
10
18
23
21
22
20
19
11
13
14
17
3
4
6
8
9
2
1
7
прямой левый обход
def PreOrderTraversal (v):
if v is not None:
Action
10
18
23
21
22
20
19
11
13
14
17
3
4
6
8
9
2
1
7
обратный левый обход
def PostOrderTraversal (v):
if v is not None:
PostOrderTraversal
10
18
23
21
22
20
19
11
13
14
17
3
4
6
8
9
2
1
7
обратный левый обход
def PostOrderTraversal (v):
if v is not None:
PostOrderTraversal
10
18
23
21
22
20
19
11
13
14
17
3
4
6
8
9
2
1
7
внутренний левый обход
def InOrderTraversal (v):
if v is not None:
InOrderTraversal
10
18
23
21
22
20
19
11
13
14
17
3
4
6
8
9
2
1
7
внутренний левый обход
def InOrderTraversal (v):
if v is not None:
InOrderTraversal
ФПМИ БГУ
Примеры задач
Найти высоту дерева.
Определить, является ли дерево сбалансированнным по высоте.
Найти
ФПМИ БГУ
Примеры задач
Найти высоту дерева.
Определить, является ли дерево сбалансированнным по высоте.
Найти
7
0
0
1
3
4
3
2
0
0
1
1
Обратный левый (или правый) обход
если вершина v лист, то её высота
7
0
0
1
3
4
3
2
0
0
1
1
Обратный левый (или правый) обход
если вершина v лист, то её высота
0
0
1
0
1
2
3
0
1
2
4
5
6
7
3
10
18
23
21
22
20
19
11
13
14
17
6
8
9
2
Зная метки высот, можно найти длину наибольшего полупути и его корень:
0
0
1
0
1
2
3
0
1
2
4
5
6
7
3
10
18
23
21
22
20
19
11
13
14
17
6
8
9
2
Зная метки высот, можно найти длину наибольшего полупути и его корень:
0
1
0
0
0
1
2
3
1
2
4
5
6
7
3
0
2
10
18
23
21
22
20
19
11
13
14
17
6
8
9
2
3) Найти длину наибольшего полупути и указать корни полупутей наибольшей длины.
ФПМИ
0
1
0
0
0
1
2
3
1
2
4
5
6
7
3
0
2
10
18
23
21
22
20
19
11
13
14
17
6
8
9
2
3) Найти длину наибольшего полупути и указать корни полупутей наибольшей длины.
ФПМИ
1
2
1
1
1
2
3
4
3
4
10
13
14
15
5
если вершина v лист, то её метка равна 1;
если у вершины
1
2
1
1
1
2
3
4
3
4
10
13
14
15
5
если вершина v лист, то её метка равна 1;
если у вершины
1
2
3
4
5
6
7
8
Выполнить любой обход дерева и подсчитать число вершин (n=15).
Если n
1
2
3
4
5
6
7
8
Выполнить любой обход дерева и подсчитать число вершин (n=15).
Если n
Сначала обратным обходом расставить вершинам метки высот. Во время этого же
Сначала обратным обходом расставить вершинам метки высот. Во время этого же
m
i
a
t
u
s
b
p
f
вершина t является средней по значению
f
p
m
i
b
s
u
t
ФПМИ БГУ
7) Найти среднюю по значению
m
i
a
t
u
s
b
p
f
вершина t является средней по значению
f
p
m
i
b
s
u
t
ФПМИ БГУ
7) Найти среднюю по значению
Удаление вершины
ФПМИ БГУ
Случай 1. Удаляется лист.
Случай 2. Удаляется вершина, у которой
Удаление вершины
ФПМИ БГУ
Случай 1. Удаляется лист.
Случай 2. Удаляется вершина, у которой
ФПМИ БГУ
Случай 1. Удаляется лист.
ФПМИ БГУ
Случай 1. Удаляется лист.
ФПМИ БГУ
Случай 2. Удаляется вершина, у которой есть только одно поддерево.
ФПМИ БГУ
Случай 2. Удаляется вершина, у которой есть только одно поддерево.
ФПМИ БГУ
Случай 2. Удаляется вершина, у которой есть только одно поддерево
ФПМИ БГУ
Случай 2. Удаляется вершина, у которой есть только одно поддерево
10
18
23
21
22
20
19
11
13
14
17
6
8
9
2
правое удаление
вершины 10
11
18
23
21
22
20
19
13
14
17
6
8
9
2
12
11
ФПМИ БГУ
Случай 3. Удаляется вершина, у которой есть
10
18
23
21
22
20
19
11
13
14
17
6
8
9
2
правое удаление
вершины 10
11
18
23
21
22
20
19
13
14
17
6
8
9
2
12
11
ФПМИ БГУ
Случай 3. Удаляется вершина, у которой есть
10
18
23
21
22
20
19
11
13
14
17
6
8
9
2
левое удаление
вершины 10
9
18
23
21
22
20
19
13
14
17
6
8
2
12
9
ФПМИ БГУ
Случай 3. Удаляется вершина, у которой есть оба
10
18
23
21
22
20
19
11
13
14
17
6
8
9
2
левое удаление
вершины 10
9
18
23
21
22
20
19
13
14
17
6
8
2
12
9
ФПМИ БГУ
Случай 3. Удаляется вершина, у которой есть оба
!!! Если у удаляемой вершины только одно поддерево, то НЕТ ПОНЯТИЯ
!!! Если у удаляемой вершины только одно поддерево, то НЕТ ПОНЯТИЯ
Оценки числа операций
в худшем случае
10
18
19
6
2
построение дерева для последовательности из n элементов
Оценки числа операций
в худшем случае
10
18
19
6
2
построение дерева для последовательности из n элементов
Сборник задач по теории алгоритмов : учеб.-метод. пособие / В.М. Котов,
Сборник задач по теории алгоритмов : учеб.-метод. пособие / В.М. Котов,
Prezentatsia_4 (1)
Алгоритм с ветвлением. Исполнитель робот
Презентация "Блок-схемы алгоритмов" - скачать презентации по Информатике
Презентация "Кодирование информации" - скачать презентации по Информатике
Создание БД и таблиц в СУБД. Понятие ключевого поля и индекса. Типы данных. Свойства полей
Последовательный порт. Архитектура персональных компьютеров
Алгоритмическая конструкция. Ветвление
Информационное обеспечение прогнозирования
Разработка web-представительства агентства недвижимости
Аттестационная работа. Образовательная программа внеурочной деятельности по информатике Занимательная компьютерная графика
Проектировка и разработка игры в жанре RPG
Что умеет компьютер
Международная электронная платёжная система Wallet One (единый кошелёк)
Алгоритмы поиска подстроки в строке
Бесплатные аналоги коммерческих программ для Windows Подготовила учитель информатики МОУ «ООШ №10» Нестеренко Е.С.
Типы данных
Оформление презентаций
Основы работы MS Excel
Создание документов средствами on-line сервисов
Контент для социальных сетей
Технологии 3D печати и тенденции их развития
Базы данных и СУБД. Модели данных. Реляционная модель данных
Радиопрограмма Адреса милосердия союз НКО и социального СМИ
Кодирование информации ( шифровка информации ) Подготовила: Беломестнова Марина Вадимовна учитель начальных классов МОУ ООШ № 1
Классификация информационных систем
CSS Properties. The position property
Презентация на тему: Графология как инструмент кадрового менеджмента.
База данных. Прикладная среда-система управления базой данных Аccess.