Алгоритмы и структуры данных

Содержание

Слайд 2

Соболевская Елена Павловна
доцент кафедры дискретной математики и алгоритмики,
кандидат физико-математических наук,

Соболевская Елена Павловна доцент кафедры дискретной математики и алгоритмики, кандидат физико-математических наук,
доцент
Лауреат премии имени А.Н. Севченко в номинации «Образование»
за цикл пособий по дискретной математике, проектированию и анализу алгоритмов
http://fpmi.bsu.by/main.aspx?guid=30051

ФПМИ БГУ

Лектор

Слайд 3

Буславский Александр Андреевич
старший преподаватель кафедры дискретной математики и алгоритмики,
Лауреат специального фонда

Буславский Александр Андреевич старший преподаватель кафедры дискретной математики и алгоритмики, Лауреат специального
Президента Республики Беларусь по социальной поддержке одарённых учащихся и студентов.
http://fpmi.bsu.by/main.aspx?guid=39321

ФПМИ БГУ

Практические занятия

Соболевская Елена Павловна
доцент кафедры дискретной математики и алгоритмики,
кандидат физико-математических наук, доцент
Лауреат премии имени А.Н. Севченко в номинации «Образование»
за цикл пособий по дискретной математике, проектированию и анализу алгоритмов
http://fpmi.bsu.by/main.aspx?guid=30051

Слайд 4

Информационно-коммуникационные технологии:
Образовательный портал БГУ https://edufpmi.bsu.by
Образовательная платформа Insight Runner https://acm.bsu.by/
Группы в мессенджере Telegram,

Информационно-коммуникационные технологии: Образовательный портал БГУ https://edufpmi.bsu.by Образовательная платформа Insight Runner https://acm.bsu.by/ Группы
сервисы Google.

ФПМИ БГУ

Слайд 5

Соболь Сергей Александрович
инженер-программист ООО ЯндексБел,
старший преподаватель кафедры дискретной математики и

Соболь Сергей Александрович инженер-программист ООО ЯндексБел, старший преподаватель кафедры дискретной математики и
алгоритмики (2014-2020 год),
магистр математики и информационных технологий,
cеребряная медаль ACM ICPC 2013.

Разработчик Образовательной платформы Insight Runner

ФПМИ БГУ

Слайд 6

Insight Runner

ФПМИ БГУ

https://acm.bsu.by/
логин номер вашего студенческого (семь цифр)
пароль (по умолчанию): 11111

После

Insight Runner ФПМИ БГУ https://acm.bsu.by/ логин номер вашего студенческого (семь цифр) пароль
первого входа в iRunner необходимо сменить пароль и установить двухфакторную аутентификацию (для исключения противоправных действий в системе при несанкционированном доступе.)

Слайд 7

Insight Runner Wiki
(руководство по работе)

Insight Runner Wiki (руководство по работе)

Слайд 8

ФПМИ БГУ

Insight Runner Wiki

ФПМИ БГУ Insight Runner Wiki

Слайд 9

ФПМИ БГУ

Для самоконтроля усвоения теоретического материала в Insight Runner разработана система тестов.
Тесты разработаны

ФПМИ БГУ Для самоконтроля усвоения теоретического материала в Insight Runner разработана система
для большинства разделов учебной дисциплины.  Ответы к тестам (на усмотрение преподавателя) могут быть открыты после прохождения теста всеми учащимися.
Так как тесты в iRunner генерируются автоматически, то это позволяет бороться со списыванием.
Итоговый тест включает в себя 10 тестовых вопросов (20 минут) и его результат учитывается в рейтинговой оценке за работу в семестре.

Insight Runner
(тесты для самоконтроля)

Слайд 10

ФПМИ БГУ

Insight Runner
(тесты для самоконтроля)

ФПМИ БГУ Insight Runner (тесты для самоконтроля)

Слайд 11

ФПМИ БГУ
Для закрепления на практике теоретических знаний в Insight Runner разработаны общие

ФПМИ БГУ Для закрепления на практике теоретических знаний в Insight Runner разработаны
задачи (их должны выполнить все студенты).

Общие задачи открываются в iRunner, как правило, после каждой лекции и нацелены на проработку базовых знаний по пройденному на лекции материалу.
Эти задачи достаточно простые, не предполагают разработки сложных алгоритмов решения, а готовят студентов к решению индивидуальных задач.  

Insight Runner
(общие задачи)

Преподаватель может установить крайний срок выполнения задания. Задания, выполненные с нарушением этого срока, в системе iRunner имеют особые пометки.

Слайд 12

ФПМИ БГУ

 Тема 1. Бинарные поисковые деревья:
0.1 построение дерева 0.2 удаление вершин из дерева 0.3 проверка

ФПМИ БГУ Тема 1. Бинарные поисковые деревья: 0.1 построение дерева 0.2 удаление
является ли бинарное дерево поисковым
Тема 2. Динамическое программирование
0.1 Оптимальное перемножение группы матриц (двухмерное ДП) 0.2 Единицы - число сочетаний из n по k(одномерное ДП, модульная арифметика) 0.3. Единицы (большие ограничения, только для желающих) 20. Палиндром (двухмерное ДП, строки) 69. Кувшинки (простейшее одномерное ДП)
Тема 3. Структуры данных
0.1. Бинарный поиск (массив,  уметь реализовать BinarySearch, LowerBound, UpperBound) 0.2 Задача о сумме (реализация структур для интервальных запросов - сумма на отрезке) 0.3. Бинарная куча (проверка на соответствие структуре) 0.4. Биномиальная куча (понимание структуры) 0.5. Хеш-таблица (разрешение коллизий метом открытой адресации)
Тема 4. Алгоритмы на графах
0.1 Строительство дорог ( DSU + алг. на графах) 0.2 Разрушение дорог  ( DSU + алг. на графах)   0.3 Разрушение дорог (большие ограничения, только для желающих) 0.4 Матрица смежности 0.5. Канонический вид (по списку дуг) 0.6. Список смежности 0.7 Канонический вид (по матрице смежности) 0.8 BFS (поиск в ширину) 0.9 DFS (поиск в глубину) 0.10 Кратчайший путь. Алгоритм Дейкстры 0.11 Максимальный поток в сети (простая версия)    0.12 Максимальный поток в сети (большие ограничения, только для желающих)

Insight Runner
(общие задачи)

Слайд 13

ФПМИ БГУ

Insight Runner
(общие задачи)

ФПМИ БГУ Insight Runner (общие задачи)

Слайд 14

ФПМИ БГУ

В рамках учебной дисциплины студентами также выполняются индивидуальные задачи. Число индивидуальных

ФПМИ БГУ В рамках учебной дисциплины студентами также выполняются индивидуальные задачи. Число
задач - по каждой теме не менее одной.  Индивидуальная задача предполагает разработку эффективного алгоритма решения задачи с последующей реализацией его в Insight Runner на любом языке программирования. С 2016 г. в учебных курсах ограничивается до пяти число решений, которые можно отправить по каждой из назначенных задач в течение суток. На протяжении любого 24-часового отрезка времени разрешается отправить не более чем пять решений по каждой задаче. Ограничение не привязано к наступлению новых суток в 00:00. Решения с вердиктом «Ошибка компиляции» при подсчёте оставшихся попыток игнорируются.
  Отметим, что в течение многих лет для всех студентов, которые работали в старой версии системы Insight Runner, действовало ограничение в двадцать попыток по задаче в семестр. Это ограничение было нельзя увеличить индивидуально. Политика ограничения числа посылок в день вместо ограничения общего числа посылок является более гибкой и применяется во многих системах, например на платформе Kaggle. 
Призываем вас более качественно тестировать свои решения перед отправкой!!!

Insight Runner
(индивидуальные задачи)

Слайд 15

ФПМИ БГУ

Insight Runner
(индивидуальные задачи)

ФПМИ БГУ Insight Runner (индивидуальные задачи)

Слайд 16

ФПМИ БГУ

Insight Runner
проверка на плагиат
)

ФПМИ БГУ Insight Runner проверка на плагиат )

Слайд 17

ФПМИ БГУ

Insight Runner
проверка на плагиат

ФПМИ БГУ Insight Runner проверка на плагиат

Слайд 18

ФПМИ БГУ

В.М. Котов, Е. П. Соболевская, А. А. Толстиков. «Алгоритмы и структуры

ФПМИ БГУ В.М. Котов, Е. П. Соболевская, А. А. Толстиков. «Алгоритмы и
данных»: учеб. пособие Минск: БГУ, 2011г. – 267 с. – (Классическое университетское издание).  
Теория алгоритмов: учеб. пособие / П.А. Иржавский, В.М. Котов, А.Ю. Лобанов, Ю.Л. Орлович, Е.П. Соболевская – Минск : БГУ, 2013. – 159 с.  
Сборник задач по теории алгоритмов : учеб.-метод. пособие / В.М. Котов, Ю.Л. Орлович, Е.П. Соболевская, С.А. Соболь – Минск : БГУ, 2017.- 183с  
Соболь С.А., Вильчевский К.Ю., Котов В.М., Соболевская Е.П. Сборник задач по теории алгоритмов. Структуры данных: – Минск : БГУ, 2020. – 159 с. (с грифом УМО по естественнонаучному образованию).

Литература

Алгоритмы: построение и анализ / Т. Кормен [и др.] – М.: Вильямс, 2005. – 1296 c.

Литература

Слайд 19

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

Для выполнения первой индивидуальной задачи, необходимо обладать навыками работы с бинарными поисковыми
деревьями. Частично вы уже получили эти навыки в рамках дисциплин по программированию, поэтому сейчас систематизируем их.

ФПМИ БГУ

Insight Runner
(индивидуальное задание № 1)

Слайд 20

Словарные операции

поиск элемента с заданным ключом х
добавление нового элемента с заданным ключом

Словарные операции поиск элемента с заданным ключом х добавление нового элемента с
х
удаление элемента с заданным ключом х

ФПМИ БГУ

Слайд 21

Бинарное поисковое дерево

Поисковое
5. Каждой вершине поставлено в соответствие некоторое целое число -

Бинарное поисковое дерево Поисковое 5. Каждой вершине поставлено в соответствие некоторое целое
ключ. Для каждой вершины v все ключи в её левом поддереве строго меньше ключа вершины v, а в правом – строго больше.

корень

n – число вершин
m=n-1 – число дуг

ФПМИ БГУ

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

Бинарное
4. Каждая вершина содержит не более 2-х сыновей.

Слайд 22

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
БГУ

2, 1, 6, 4, 3, 10, 9, 8, 7, 18, 17, 14, 13, 11, 19, 20, 22, 23, 21

Слайд 23

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
дереве все ключи различны, то одинаковые элементы при добавлении будем игнорировать

Слайд 24

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

высота (10) = 5
Высота дерева: высота корня.
высота (дерева) = 7

Глубина вершины: длина пути из корня в вершину (этот путь единственный).
глубина (10) = 2

Уровень вершины: высота дерева минус глубина вершины
уровень (10) = высота (дерева)- глубина (10) =7 – 2 = 5

ФПМИ БГУ

Высота, глубина, уровень

0-й уровень

1-й уровень

2-й уровень

7-й уровень

3-й уровень

4-й уровень

5-й уровень

6-й уровень

Слайд 25

10

18

23

21

22

20

19

11

13

14

17

3

4

6

8

9

7

2

1

Для полупути снимается ограничение на направление дуг.
Пример полупути, соединяющего вершины 1 и

10 18 23 21 22 20 19 11 13 14 17 3
7: 1 - 2 - 6 - 10 - 9 - 8 - 7

ФПМИ БГУ

Путь, полупуть

Слайд 26

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
равно количеству вершин после неё.

Средняя по значению (медиана) вершина полупути -такая вершина, что у половины из оставшихся вершин этого полупути ключ меньше, а у половины – больше.

Что делать, если число вершин, среди которых надо найти центральную или среднюю ЧЁТНО?

ФПМИ БГУ

Центральная и средняя вершины полупути

?

центральной и средней вершины НЕ СУЩЕСТВУЕТ

Слайд 27

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
пути измеряется в рёбрах, а не вершинах).

ФПМИ БГУ

Корнем полупути назовём вершину полупути с самой большой высотой (на рисунке выделены два наибольших полупути и у них общий корень 18).

Слайд 28

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
длины?
3) Сколько попарно различных полупутей наибольшей длины проходит через вершину 18?

ФПМИ БГУ

=5

=8

=18 и 6

Слайд 29

прямой (левый, правый) - PreOrderTraversal (v)

ФПМИ БГУ

Обходы

обратный (левый, правый) - PostOrderTraversal (v)

внутренний

прямой (левый, правый) - PreOrderTraversal (v) ФПМИ БГУ Обходы обратный (левый, правый)
(левый, правый) - InOrderTraversal (v)

Время выполнения обхода: пропорционально числу вершин в дереве (=n)

Слайд 30

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 (v)

10 18 23 21 22 20 19 11 13 14 17 3
PreOrderTraversal (v.left)
PreOrderTraversal (v.right)

прямой правый обход
def PreOrderTraversal (v):
if v is not None:
Action (v)
PreOrderTraversal (v.right)
PreOrderTraversal (v.left)

прямой левый обход

прямой правый обход

2, 1, 6, 4, 3, 10, 9, 8, 7, 18, 17, 14, 13, 11, 19, 20, 22, 21, 23

2, 6, 10, 18, 19, 20, 22, 23, 21, 17, 14, 13, 11, 9, 8, 7, 4, 3, 1

ФПМИ БГУ

Слайд 31

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 (v.left)

10 18 23 21 22 20 19 11 13 14 17 3
PostOrderTraversal (v.right)
Action (v)

обратный правый обход
def PostOrderTraversal (v):
if v is not None:
PostOrderTraversal (v.right)
PostOrderTraversal (v.left)
Action (v)

обратный левый обход

обратный правый обход

1 ,3, 4, 7, 8, 9, 11, 13, 14, 17, 21, 23, 22, 20, 19, 18, 10, 6, 2

23, 21, 22, 20, 19, 11, 13, 14, 17, 18, 7, 8, 9, 10, 3, 4, 6, 1, 2

ФПМИ БГУ

Слайд 32

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 (v.left)

10 18 23 21 22 20 19 11 13 14 17 3
Action (v)
InOrderTraversal (v.right)

внутренний правый обход
def InOrderTraversal (v):
if v is not None:
InOrderTraversal (v.right)
Action (v)
InOrderTraversal (v.left)

внутренний левый обход
(ключи отсортированы по возрастанию)

внутренний правый обход
(ключи отсортированы по убыванию)

1, 2, 3, 4, 6, 7, 8, 9, 10, 11, 13, 14, 17, 18, 19, 20, 21, 22, 23

23, 22, 21, 20, 19, 18, 17, 14, 13, 11, 10, 9, 8, 7, 6, 4, 3, 2, 1

ФПМИ БГУ

Слайд 33

ФПМИ БГУ

Примеры задач

Найти высоту дерева.
Определить, является ли дерево сбалансированнным по высоте.
Найти длину

ФПМИ БГУ Примеры задач Найти высоту дерева. Определить, является ли дерево сбалансированнным
наибольшего полупути (корни полупутей наибольшей длины).
Проверить, является ли дерево идеально-сбалансированным по числу вершин.
Найти среднюю по значению вершину в дереве.
Найти среднюю по значению вершину среди вершин, у которых высоты поддеревьев совпадают.
Найти среднюю по значению вершину среди вершин некоторого пути.

Слайд 34

Обратный левый (или правый) обход

если вершина v лист, то её высота равна

Обратный левый (или правый) обход если вершина v лист, то её высота
0;
если у вершины v только одно поддерево, то её высота равна высоте этого поддерева +1;
если у вершины v есть оба поддерева, то её высота равна максимуму из высот поддреревьев, увеличенному на 1.

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

Найти высоту дерева.
Определить, является ли дерево сбалансированнным по высоте (для всех вершин высоты их подеревьев должны отличаться не более, чем на 1.

ФПМИ БГУ

Нужно знать высоту каждой вершины.

Слайд 35

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

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

Вершина

10 18 23 21 22 20 19 11 13 14 17 6
18: 3+3+2=8
является корнем наибольшего полупути.
Длина наибольшего полупути равна 8.

3) Найти длину наибольшего полупути (корни полупутей наибольшей длины).

ФПМИ БГУ

найдём ту вершину v, для которой сумма меток высот её поддеревьев, увеличенная на число 2 или 1 (в зависимости от того, сколько поддеревьев у вершины v), является наибольшей.

Слайд 36

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

3) Найти длину наибольшего полупути и указать корни полупутей наибольшей длины.

ФПМИ БГУ

1

0

7

2

Вершины

10 18 23 21 22 20 19 11 13 14 17 6
2, 10, 18 являются корнями полупутей наибольшей длины 8.

Вопрос 1.
Сколько полупутей наибольшей длины проходит через вершины?
1
2
10
18
19

Вопрос 2.
Через какие вершины пройдёт наибольшее число полупутей наибольшей длины?

Слайд 37

если вершина v лист, то её метка равна 1;
если у вершины v

если вершина v лист, то её метка равна 1; если у вершины
только одно поддерево, то её метка равна метке этого поддерева +1;
если у вершины v есть оба поддерева, то её метка равна сумме меток поддеревьев, увеличенной на 1.

10

18

23

21

22

20

19

11

13

14

17

6

8

9

2

1

2

1

1

1

2

3

4

3

4

10

13

14

15

5

4) Проверить, является ли дерево идеально-сбалансированным по числу вершин: для каждой вершины число вершин в поддеревьях должно отличаться не более, чем на 1 (для простоты вычислений, если у вершины отсутствует поддерево, то число вершин в таком поддереве полагается равным 0).

ФПМИ БГУ

Нужно знать число вершин в каждом поддереве.

Обратный левый (или правый) обход

Слайд 38

Выполнить любой обход дерева и подсчитать число вершин (n=15).
Если n –

Выполнить любой обход дерева и подсчитать число вершин (n=15). Если n –
чётно, то полагаем, что средней не существует.
Если n – нечётно, то выполним внутренний обход, считая пройденные во время этого обхода вершины. Остановимся, как только счётчик пройденных вершин станет равным [n/2]+1 (=8).

10

18

23

21

22

20

19

11

13

14

17

6

8

9

2

1

2

3

4

5

6

7

8

ФПМИ БГУ

5) Найти среднюю по значению вершину в дереве
(не использовать дополнительную память, зависящую от n, решить задачу за линейное от количества вершин время).

Сначала нужно узнать, чётно или нет число вершин в дереве.
Если число вершин нечётно, то средняя вершина существует и её можно найти, просматривая вершины дерева, например, по неубыванию ключей.

на рис. показана нумерация вершин при обходе:

def InOrderTraversal (v):
if v is not None:
InOrderTraversal (v.left)
Action (v)
InOrderTraversal (v.right)

Слайд 39

Сначала обратным обходом расставить вершинам метки высот. Во время этого же обхода

Сначала обратным обходом расставить вершинам метки высот. Во время этого же обхода
подсчитать количество вершин, у которых метки высот поддеревьев совпали. Пусть у нас m таких вершин.
Если m – чётно, то средней не существует.
Если m – нечётно, то выполним внутренний обход, считая при этом только лишь те вершины, для которых высоты их поддеревьев совпадают. Остановимся, как только счётчик станет равным [m/2]+1.

18

23

22

20

19

11

12

14

17

0

1

2

4

3

3

2

1

0

21

0

13

0

ФПМИ БГУ

6) Найти среднюю по значению вершину среди вершин, у которых высоты поддеревьев совпадают.

Сначала нужно определить нужные вершину, узнать чётно или нет их количество. Если нечётно, то средняя вершина существует и её можно найти, просматривая нужные вершины, например, по неубыванию ключей.

Внутренний (левый) обход:
11, 12, 13, 14, 17, 18, 19, 20, 21, 22, 23

Слайд 40

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 является
среди вершин некоторого пути.
Предположим, что задан корень этого пути.

Слайд 41

Удаление вершины

ФПМИ БГУ

Случай 1. Удаляется лист.

Случай 2. Удаляется вершина, у которой есть

Удаление вершины ФПМИ БГУ Случай 1. Удаляется лист. Случай 2. Удаляется вершина,
только одно поддерево

Случай 3. Удаляется вершина, у которой есть оба поддерева (возможно «правое» или «левое» удаление).

Слайд 42

ФПМИ БГУ

Случай 1. Удаляется лист.

ФПМИ БГУ Случай 1. Удаляется лист.

Слайд 43

ФПМИ БГУ

Случай 2. Удаляется вершина, у которой есть только одно поддерево.

ФПМИ БГУ Случай 2. Удаляется вершина, у которой есть только одно поддерево.

Слайд 44

ФПМИ БГУ

Случай 2. Удаляется вершина, у которой есть только одно поддерево

ФПМИ БГУ Случай 2. Удаляется вершина, у которой есть только одно поддерево

Слайд 45

10

18

23

21

22

20

19

11

13

14

17

6

8

9

2

правое удаление

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
«правое» удаление).

Слайд 46

10

18

23

21

22

20

19

11

13

14

17

6

8

9

2

левое удаление

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
«левое» удаление).

Слайд 47

!!! Если у удаляемой вершины только одно поддерево, то НЕТ ПОНЯТИЯ ПРАВОЕ/ЛЕВОЕ
удаление.

!!! Если у удаляемой вершины только одно поддерево, то НЕТ ПОНЯТИЯ ПРАВОЕ/ЛЕВОЕ
Удаление всегда выполняется однозначно.

Найти вершину, которая удовлетворяет заданному свойству. Удалить эту вершину (правое удаление).

?

(рис.1)

или

ФПМИ БГУ

(рис.2)

Ответ: правильно выполнено удаление на рис. 1.

Слайд 48

Оценки числа операций
в худшем случае

10

18

19

6

2

построение дерева для последовательности из n элементов

поиск

Оценки числа операций в худшем случае 10 18 19 6 2 построение
элемента с заданным ключом x

добавление элемента с заданным ключом х

в худшем случае высота дерева
h = n-1

обход дерева из n вершин

удаление элемента с заданным ключом x

ФПМИ БГУ

h

h

n·h

n

h

Слайд 49

Георгий Максимович Адельсон-Вельский

Евгений Михайлович Ландис 

В 1962 году советские учёные Г.М. Адельсон-Вельский

Георгий Максимович Адельсон-Вельский Евгений Михайлович Ландис В 1962 году советские учёные Г.М.
и  Е.М. Ландис предложили структуру данных сбалансированного поискового дерева (АВЛ-дерево).

Слайд 50

ФПМИ БГУ

В рамках дисциплины мы подробно исследуем эту структуру данных, а пока

ФПМИ БГУ В рамках дисциплины мы подробно исследуем эту структуру данных, а
- краткая информация о ней.

Слайд 51

АВЛ-дерево – это бинарное поисковое дерево, которое является сблансированным по высоте.

2

4

1

3

5

Свойство

АВЛ-дерево – это бинарное поисковое дерево, которое является сблансированным по высоте. 2
сбалансированности по высоте:
для каждой вершины дерева высоты её поддеревьев отличаются не более, чем на 1.

ФПМИ БГУ

АВЛ-дерево

2

4

3

5

не является АВЛ-деревом, так как для вершины 2 не выполняется свойство сбалансированности

Слайд 52


ТЕОРЕМА. Пусть n – число внутренних вершин АВЛ-дерева, а h – его

ТЕОРЕМА. Пусть n – число внутренних вершин АВЛ-дерева, а h – его
высота.
Тогда справедливы следующие неравенства:

ФПМИ БГУ

Слайд 53

Использование поисковых деревьев на практике

ФПМИ БГУ

Использование поисковых деревьев на практике ФПМИ БГУ

Слайд 54

Сортировка деревом

1. По последовательности чисел сначала построим АВЛ-дерево последовательным добавлением элемента.

Сортировка деревом 1. По последовательности чисел сначала построим АВЛ-дерево последовательным добавлением элемента.
n*log n
2. Выполним внутренний левый обход дерева.
n

ФПМИ БГУ

Предположим, что на вход поступаю числа, среди которых нет повторяющихся. Необходимо выдать числа в порядке возрастания.
Какое время работы алгоритма сортировки деревом худшем случае, если на вход поступило n чисел?
n*log n

Слайд 55

Абстрактный тип данных: множество (set)

Множество (англ. set) —хранит набор попарно различных объектов

Абстрактный тип данных: множество (set) Множество (англ. set) —хранит набор попарно различных
без определённого порядка.
Интерфейс множества включает три основные операции:
Insert(x) — добавить в множество ключ x;
Contains(x) — проверить, содержится ли в множестве ключ x;
Remove(x) — удалить ключ x из множества.

ФПМИ БГУ

Для реализации интерфейса множества обычно используются такие структуры данных, как:
сбалансированные поисковые деревья: например, AVL-деревья, 2-3-деревья, красно-чёрные деревья.
хеш-таблицы.

В стандартной библиотеке C++ есть контейнер std::set, который реализует множество на основе сбалансированного дерева (обычно красно-чёрного), и контейнер std::unordered_set, построенный на базе хеш-таблицы.
В языке Java определён интерфейс Set, у которого есть несколько реализаций, среди которых классы TreeSet (работает на основе красно-чёрного дерева) и HashSet (на основе хеш-таблицы).
В языке Python есть только встроенный тип set, использующий хеширование, но нет готового класса множества, построенного на сбалансированных деревьях.

Слайд 56

Абстрактный тип данных ассоциативный массив (map)

Ассоциативный массив (англ. associative array), или отображение

Абстрактный тип данных ассоциативный массив (map) Ассоциативный массив (англ. associative array), или
(англ. map), или словарь (англ. dictionary), —хранит пары вида (ключ, значение), при этом каждый ключ встречается не более одного раза.
Название «ассоциативный» происходит от того, что значения ассоциируются с ключами.
Интерфейс ассоциативного массива включает операции:
Insert(k,v) — добавить пару, состоящую из ключа k и значения v;
Find(k) — найти значение, ассоциированное с ключом k, или сообщить, что значения, связанного с заданным ключом, нет;
Remove(k) — удалить пару, ключ в которой равен k.

ФПМИ БГУ

Данный интерфейс реализуется на практике теми же способами, что и интерфейс множества. Реализация технически немного сложнее, чем множества, но использует те же идеи.
Для языка программирования C++ в стандартной библиотеке доступен контейнер std::map, работающий на основе сбалансированного дерева (обычно красно-чёрного), и контейнер std::unordered_map, работающий на основе хеш-таблицы.
В языке Java определён интерфейс Map, который реализуется несколькими классами, в частности классом TreeMap (базируется на красно-чёрном дереве) и HashMap (базируется на хеш-таблице).
В языке Python очень широко используется встроенный тип dict. Этот словарь использует внутри хеширование.

Слайд 57

Сборник задач по теории алгоритмов : учеб.-метод. пособие / В.М. Котов, Ю.Л.

Сборник задач по теории алгоритмов : учеб.-метод. пособие / В.М. Котов, Ю.Л.
Орлович, Е.П. Соболевская, С.А. Соболь – Минск : БГУ, 2017. С. 122-180

Литература по теме: «Бинарные поисковые деревья»

https://acm.bsu.by/wiki/Программная_реализация_бинарных_поисковых_деревьев

ФПМИ БГУ

0.1 построение дерева 0.2 удаление вершин из дерева 0.3 проверка является ли бинарное дерево поисковым

Общие задачи в iRunner

Индивидуальная задача по теме «Деревья поиска» в iRunner

Имя файла: Алгоритмы-и-структуры-данных.pptx
Количество просмотров: 61
Количество скачиваний: 0