Введение в программирование 14. Красно-чёрное дерево

Введение в программирование, алгоритмы и структуры данных. МФТИ, Физтех-школа прикладной математики и информатики

Лекция прочитана 9 декабря 2021 года
Лектор: Степанов Илья Даниилович
Оператор: Мария Шкатова
Монтаж: Жильцов Игорь

0:00 - Красно-чёрное дерево. Определение
5:56 - Пример
8:42 - Оценка глубины КЧ-дерева
19:00 - find (как в любом дереве поиска)
19:26 - insert
20:44 - Как хранить листья?
25:35 - Какие свойства КЧ-дерева нарушаются после insert?
26:54 - (Очевидный) фикс 2 свойства
27:22 - Фикс 4 свойства
28:23 - Разбор случаев: цвет дяди. Случай 1 - красный
32:28 - Случай 2.1 - чёрный дядя, Х - левый сын
38:48 - Случай 2.2 - чёрный дядя, Х - правый сын
41:06 - Резюме: как работает insert?
42:27 - Преимущество insert'а в КЧ-дереве
44:55 - erase. Ещё больше случаев (но мало поворотов)
46:15 - Как свести случай когда у Х два ребёнка к случаю когда у Х не более 1 ребёнка
48:00 - Случай 1. Красный Х без детей
49:58 - Случай 3. У Х есть есть ребёнок
56:08 - Случай 2. Чёрный Х без детей. Общая задача
1:00:00 - Случай 2.1. Красная вершина А
1:01:35 - Случай 2.1.1. У В есть красный сын
1:05:17 - Случай 2.1.2. У В нет красного сына
1:07:42 - Случай 2.2.1. А - чёрный, В - красный
1:10:15 - Случай 2.2.1.1. У С есть красный сын
1:12:44 - Случай 2.2.1.2 У С нет красного сына
1:15:01 - Случай 2.2.2 - А - чёрный, В - чёрный
1:15:26 - Случай 2.2.2.1. У В есть красные дети
1:16:54 - Случай 2.2.2.2. У В нет красных детей
1:20:20 - Зачем мы всем этим занимались? Сравнение КЧ-дерева с другими