Введение в программирование 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 - Зачем мы всем этим занимались? Сравнение КЧ-дерева с другими