Как легко запомнить вставку и удаление красно-черного дерева?

игнорируйте мой (теперь удаленный) комментарий - я думаю, что код Окасаки вам поможет. если у вас есть книга («чисто функциональные структуры данных»), посмотрите текст на стр. 26 и рисунок 3.5 (лицевая сторона, стр. 27). Трудно сделать яснее этого.

к сожалению, в тезисе, доступном в Интернете, нет этой части .

Я не собираюсь копировать это, потому что диаграмма важна, но она показывает, что все разные случаи в основном одно и то же, и дает очень простой код ML, который забивает этот дом.

[обновление] похоже, вы сможете увидеть это на Amazon. перейдите на страницу книги, наведите указатель мыши на изображение и введите "красный черный" в поле поиска. это дает вам результаты, которые включают страницы 25 и 26, но вам нужно войти в систему, чтобы увидеть их (очевидно - я не пробовал войти в систему, чтобы проверить).

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

Вращение переводит дерево в состояние, в котором оно соответствует критериям для перекраски (у дочернего узла есть красный дядя). Есть два ключевых отличия:

• какой узел является «дочерним», а какой - «дядей»;
• вместо того, чтобы перекрашивать родителя и дядю в черный цвет, а бабушку и дедушку - в красный, вы перекрашиваете родителя в красный, а бабушку и дедушку в черный.

Когда у дочернего узла нет красного дяди, вам нужно повернуть, потому что, если дядя-узел уже черный, то создание черного родительского узла увеличит высоту черного на 1 только с одной стороны от бабушки и дедушки. Это нарушит свойство инвариантности высоты красно-черных деревьев и сделает дерево несбалансированным.

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

• Пусть x будет текущим красным узлом с красным родителем.
• Пусть p будет красным родительским элементом x перед поворотом (если бы родительский элемент был черным, мы бы уже сделали).
• Пусть y будет черным дядей x перед вращением (если бы дядя был красным, нам не нужно было бы вращать. Мы просто перекрасили бы родителя и дядю в черный, а бабушку и дедушку в красный).
• Пусть g будет черным прародителем x перед поворотом (поскольку родитель красный, дедушка и бабушка должны быть черными; в противном случае это не было бы красно-черным деревом с самого начала).
• Когда у вас есть случай слева-слева (LL) или справа-справа (RR) (то есть x является левым дочерним элементом p, а p является левым дочерним элементом g ИЛИ x является правым дочерним элементом p, а p является правым дочерний элемент g), после одного поворота (вправо, если LL, влево, если RR), y становится дочерним элементом, а x - его дядей. Поскольку x - красный дядя, теперь у вас есть случай, когда вы можете перекрасить. Итак, перекрасим родительский элемент дочернего элемента (поскольку дочерний элемент теперь y, его родительский элемент - g) в красный цвет, а прародитель ребенка (который теперь является p) в черный.
• Когда у вас есть LR (x - левый дочерний элемент или p, а p - правый дочерний элемент g) или случай RL (x - правый дочерний элемент p, а p - левый дочерний элемент g), после двойного поворота (справа, затем left, если LR, влево, затем вправо, если RL), y становится дочерним элементом, а p - его дядей. Поскольку p - красный дядя, у вас снова есть случай, когда вы можете перекрасить. Итак, перекрасим родительский элемент (поскольку дочерний элемент теперь y, его родительский элемент - g) в красный цвет, а прародитель ребенка (который теперь равен x) в черный.

Перед поворотом и перекрашиванием у вас был черный прародитель с 2 красными узлами и 0 черными узлами на стороне A (слева или справа), а также 0 красными узлами и 1 черным узлом на стороне B (противоположность стороне A). После поворота и перекраски у вас есть черный прародитель с 1 красным узлом и 0 черными узлами на стороне A, 1 красным узлом и 1 черным узлом на стороне B. Таким образом, вы по существу переместили один из красных узлов в другое поддерево дерева. бабушкой и дедушкой, не увеличивая высоту черного любого поддерева.

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

Логика довольно проста. Предположим, z красный, а родитель z красный: если дядя z красный, выполните шаг 1, чтобы подтолкнуть проблемный узел вверх до тех пор, пока (1) родитель не станет корнем. Затем просто отметьте корень черным. Готово или (2) дядя z черный.

В случае (2) либо (a) z является левым потомком своего родителя, тогда шаг 3 будет последним шагом, поскольку все свойства BST выполнены. Выполнено. или (b) z - правый дочерний элемент своего родителя. Шаг 2 преобразует проблему в случай (а). Затем выполните шаг 3. Выполнено.

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

Любое 2-4 (2-3-4) дерево можно превратить в красно-черное дерево. А понять 2-4 дерева намного проще. Если вы просто выполните операции вставки и удаления в 2-4 деревьях, вы почувствуете, что для достижения того же нет необходимости запоминать какие-либо правила. Вы увидите ясную простую логику, которая позволяет вам предлагать решения для различных сценариев вставки и удаления.

Когда у вас есть четкое представление о 2-4 деревьях, когда вы имеете дело с красно-черными деревьями, вы можете мысленно сопоставить эти красно-черные деревья с 2-4 деревьями и самостоятельно придумать логику.

Я нашел следующие несколько видеороликов, которые чрезвычайно полезны для понимания 2-4 деревьев, красно-черных деревьев и сопоставления 2-4 деревьев с красно-черными деревьями. Я бы рекомендовал просмотреть эти видео.

1) Для 2–4 деревьев: http://www.youtube.com/watch?v=JZhdUb5F7oY&list=PLBF3763AF2E1C572F&index=13

2) Для красно-черных деревьев: http://www.youtube.com/watch?v=JRsN4Oz36QU&list=PLBF3763AF2E1C572F&index=14

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

Возможно, стоит начать с красно-черных деревьев, наклоненных влево . Они предлагают интересную упрощенную реализацию.

вы действительно делаете хороший вывод, что три случая.

после вставки в RB-Tree осталась основная проблема, которую нужно решить, если она есть. там два сплошных красных узла !! как мы могли сделать так, чтобы два непрерывных красных узла исчезли, не нарушая этого правила (каждый путь имеет одинаковое количество черных узлов), поэтому мы видим два узла, существует только 3 круга ...

Извините, вы видели учебник "Инструкции по алгоритмам".

никакое тело не может помочь вам продумать rb-tree. они могут направить вас только в какой-то ключевой момент.