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

Довольно легко понять стандартное двоичное дерево поиска и его операции. Из-за этого понимания мне даже не нужно запоминать реализации этих операций вставки, удаления, поиска.

Сейчас я изучаю Red-Black Tree, и я понимаю его свойства для сохранения сбалансированного дерева. Однако мне очень трудно понять его процедуры вставки и удаления.

Я понимаю, что при вставке нового node мы отмечаем node как красный (потому что красный - это лучшее, что мы можем сделать, чтобы не нарушать красно-черные законы дерева). Новый красный node может по-прежнему нарушать "закон непрерывных красных узлов". Затем мы фиксируем его через:

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

сделано (в основном, как указано выше).

Во многих местах описывается вставка красного-черного дерева, как указано выше. Они просто расскажут вам, как это сделать. Но почему эти шаги могут исправить дерево? Почему сначала левое вращение, а затем правое вращение?

Может ли кто-нибудь объяснить, почему мне более понятно, еще более ясно, чем CLRS? Какая магия вращения?

Я действительно хочу понять, что через 1 год я смогу реализовать дерево Red-Black самостоятельно, не просматривая книгу.

Спасибо

Ответ 1

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

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

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

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

Ответ 2

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

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

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

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

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

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

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

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

Ответ 3

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

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

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

Ответ 4

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

Ответ 5

Любое дерево 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

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

Ответ 6

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

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

Прошу прощения, вы могли видеть текстовую книгу Инструкции к алгоритмам

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