Красно-черные деревья: учебник Самуэля

Учебник Сэмюэля по красно-чёрным деревьям, охватывающий операции поиска, вставки и удаления. Тайм-коды: 00:00 — Краткое руководство по красно-чёрным деревьям 02:45 — Свойства красно-чёрного дерева 05:25 — Операции поворота 07:52 — Почему повороты полезны? 09:44 — Вставка в красно-чёрное дерево 14:48 — Удаление из красно-чёрного дерева 19:26 — Исправление нарушений красно-чёрного дерева при удалении Исправления: 03:56 — Примечание: иногда здесь используется термин «совершенное двоичное дерево» вместо «полное двоичное дерево». В сообществе нет единого консенсуса (см., например, https://cs.stackexchange.com/question...)
16:40 Переменная x должна быть определена как u.right в первом условии и как u.left во втором условии. Подробное описание: В этом видео представлено краткое описание красно-чёрных деревьев. Сначала мы рассмотрим их историческое развитие и опишем их ключевое свойство: гарантированную сложность O(log n) для операций поиска, вставки и удаления. Затем мы обсудим пять свойств, характеризующих красно-чёрные деревья, и объясним, как их сочетание обеспечивает высоту дерева, равную Theta(log n). Далее мы обсудим операции вращения. Они позволяют локально реструктурировать дерево, не нарушая свойства двоичного дерева поиска. Они особенно полезны для балансировки деревьев, поскольку позволяют перемещать узлы с одного пути на другой. Мы подробно описываем вставку в красно-чёрное дерево, пошагово разбирая каждый возможный случай и способы устранения нарушений свойств красно-чёрного дерева. Наконец, мы рассмотрим операцию удаления в красно-чёрных деревьях, описывая приём «двойного чёрного», различные случаи, которые необходимо обработать, и то, как всё это работает для обеспечения сложности O(log n). Темы: #datastructures #redblacktree #coding Краткое руководство по бинарным деревьям поиска (упоминается в видео как строительный блок для вставки красно-черного дерева):    • Binary Search Trees: Samuel's tutorial   Код Python для минималистичной реализации красно-черных деревьев можно найти здесь: https://github.com/albanie/algorithms...
Слайды (pdf): https://samuelalbanie.com/files/diges...
Ссылки на статьи, упомянутые в видео, можно найти по адресу: http://samuelalbanie.com/digests/2022...
Рекомендуемая дополнительная литература по этой теме: Л. Арге и М. Лагудакис, Конспект лекций по CPS 230, https://courses.cs.duke.edu/cps130/fa...
Кормен, Т. Х., Лейзерсон, К. Э., Ривест, Р. Л. и Штайн, К. (2022). Введение в алгоритмы. Издательство MIT. https://mitpress.mit.edu/978026204630...
Похожие материалы: YouTube:    / @samuelalbanie1   Twitter:   / samuelalbanie