Алгоритмы и структуры данных (основной поток) 13. Красно-чёрное дерево

• Красно-черное дерево - это корневое бинарное дерево, которое удовлетворяет пяти условиям: все вершины покрашены в красный или черный цвет, корень всегда черный, у каждой вершины ровно два сына, нет двух красных вершин подряд, и на любом пути от корня до листа одинаковое количество черных вершин.  

• Доказывается, что в красно-черном дереве с ключами глубина не превосходит удвоенного логарифма от количества ключей плюс один.  

• Доказательство основано на индукции по глубине вершины в дереве.  

• База индукции: если вершина находится на глубине один, то у нее нет детей и она черная, поэтому ее глубина равна нулю.  

• Переход: если вершина находится на глубине n + 1, то у нее есть два сына, и глубина каждого из поддеревьев не превосходит n.  

• Суммарная глубина поддеревьев равна n + 1, поэтому глубина вершины не превосходит удвоенного логарифма от количества ключей плюс один.  

• Автор доказывает неравенство, связывающее глубину и черную глубину красно-черного дерева.  

• Он использует лемму о черной глубине и показывает, что количество ключей в дереве больше или равно двум в степени половины глубины.  

• В обычном дереве поиска, если нужно найти икс, его сравнивают с корнем и вставляют в соответствующую вершину.  

• В красно-черном дереве, если икс меньше текущего значения в вершине, его вставляют в левое поддерево, иначе - в правое.  

• Если икс нужно вставить в пустую вершину, его вставляют в фиктивный лист и подвешивают к нему двух черных сыновей.  

• Если корень дерева становится красным, его можно перекрасить в черный, чтобы сохранить черные глубины.  

• Если родитель вершины становится красным, его можно перекрасить в черный, чтобы сохранить второе и четвертое свойства красно-черного дерева.  

• В видео обсуждается проблема нарушения свойств красно-черного дерева, когда две вершины подряд становятся красными.  

• Рассматривается случай, когда у вершины икс есть родитель, который также красный.  

• В этом случае у вершины игрек обязательно есть родитель, так как иначе она не могла бы быть корнем.  

• Обсуждается, что родитель обязательно должен быть черным, так как изначально дерево было корректно раскрашено.  

• Предлагается рекурсивное решение проблемы, которое заключается в подъеме по дереву и исправлении конфликтов.  

• Обсуждаются случаи, когда дядя вершины икс красный или черный.  

• В случае, когда дядя красный, проблема решается перекрашиванием икса в черный цвет.  

• В случае, когда дядя черный, проблема решается перекрашиванием корня в красный цвет.  

• В видео приводится пример красно-черного дерева, где пустые вершины обязательно черные, но не всегда.  

• Обсуждается, что черные вершины могут быть не пустыми, и это не нарушает свойства красно-черного дерева.  

• В видео обсуждается корректное красно-черное дерево, где у каждого узла есть два цвета: красный и черный.  

• Рассматривается случай, когда у узла есть черный дядя и икс по ту же сторону от родителя, что и игрек.  

• В этом случае, чтобы исправить проблему, нужно сделать поворот и перекраску.  

• В видео объясняется, как работает инсерт - операция вставки нового элемента в дерево.  

• Сначала спускаемся от корня в поисках икса, затем вешаем красный икс на место эффективного элемента и решаем проблему, если икс красный корень или у него красный родитель.  

• Рассматриваются два случая: либо перекрашиваем, либо поднимаемся наверх.  

• В конце видео автор сравнивает инсерт с другими операциями и отмечает, что инсерт имеет максимум два поворота, что делает его более эффективным.  

• В видео обсуждается оптимизация константы в красно-черном дереве.  

• Рассматривается случай, когда для удаления вершины достаточно одного поворота.  

• Рассматриваются случаи, когда у удаляемой вершины есть два обычных сына или один обычный и один эффективный.  

• В случае двух обычных сыновей, максимум один из них заменяется на эффективный лист.  

• Если черная глубина уменьшилась на единицу, то корень дерева должен быть черным.  

• Рассматривается задача восстановления черной глубины после удаления вершины.  

• Рассматривается случай, когда у удаляемой вершины есть один красный сын и один эффективный сын.  

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

• В случае, когда у бэ есть красный сын, автор предлагает повернуть дерево, чтобы поднять ц в корень.  

• После поворота, черная глубина остается прежней, а черная глубина под-деревьев также сохраняется.  

• В случае, когда а черный, автор предлагает перекрасить б в красный, чтобы сохранить черную глубину.  

• После перекрашивания, автор утверждает, что все подчинилось и с черными глубинами все хорошо.  

• В случае, когда оба сына у а красные, автор утверждает, что это невозможно, так как под-дерево имеет своим корнем черную штуку.  

• В случае, когда у ц нет красных детей, автор предлагает повернуть дерево и перекрасить б в красный.  

• После поворота, автор утверждает, что все подчинилось и с черными глубинами все хорошо.  

• Разбор случаев с красно-черным деревом, где у родителя есть красный или черный сын.  

• Решение проблемы с черной глубиной, когда она уменьшается на один.  

• Красно-черное дерево имеет глубину примерно два логарифма двоичных, а авель - полтора логарифма.  

• Если у вас много файндов и мало инсертов и рейзов, используйте авель.  

• Если у вас много инсертов и рейзов, используйте красно-черное дерево.  

• Сплей-дерево имеет недавние запросы, находящиеся близко к корню.  

• Минусы: только амортизационная оценка, каждый конкретный запрос может работать долго.  

• Б-дерево хорошо на больших объемах данных, но на маленьких объемах данных оно не лучше, чем другие деревья.  

• Минусы: вероятностное, на маленьких объемах данных не лучше других деревьев.