Является ли результирующее красно-черное дерево уникальным после вставки?

Предположим, у меня есть бинарное дерево поиска, которое изначально удовлетворяет всем красно-черным условиям. и содержит по одному узлу для каждого целого числа s в некотором наборе S. Далее я хочу новый узел; произнесите a (которого нет в S).

Является ли результат этого добавления уникальным после перебалансировки?

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

Я считаю, что они не уникальны, хотя не привожу доказательств (и мало уверенности). Мне просто интересно, может ли кто-нибудь более осведомленный, чем я, быть столь любезным, чтобы наставить меня?


algorithm red-black-tree binary-tree
person Ryan    schedule 19.07.2011    source источник

Ответы (2)


arrow_upward
8
arrow_downward

Они не уникальны.

Простым доказательством было бы внесение тривиального алгоритмического изменения, например, проверка того, что мы можем изменить цвет корня, и предоставление случая, когда это все еще допустимо, например:

    1-B
   /  \
 0-R  2-R

add(3):

    1-B
   /  \
 0-B  2-B
        \
        3-R

Но новый алгоритм может так же легко дать

    1-R
   /  \
 0-B  2-B
        \
        3-R

Корень другого цвета, но, конечно, оба дерева все еще действительные деревья RB.

Это может показаться немного тривиальным, но вы можете расширить эту идею (если вам нужно менее тривиальное доказательство), чтобы проверить не только корень. Вы можете глубоко проверить уровни O(1), чтобы внести нетривиальное, но действительное изменение, которое сгенерирует два разных алгоритма с одинаковым временем выполнения.

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

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

person davin    schedule 19.07.2011
comment
Извините, я читал это и пытался понять это, но у меня возникли проблемы. Суть вашего примера в том, что мы можем изменить алгоритм и показать, что оба алгоритма генерируют правильные красно-черные деревья? Что, если мы добавим дополнительное ограничение, что корень всегда должен быть черным (хотя это действительно не имеет значения с точки зрения высоты черного) - person Ryan; 19.07.2011
comment
@ Райан, поэтому я объяснил, что идея может быть расширена за пределы корня. И да, идея в том, что мы можем сгенерировать два алгоритма, которые в определенной ситуации создадут два разных действительных дерева RB. - person davin; 19.07.2011
comment
о, я вижу - когда вы говорите O (1) уровней в глубину, вы имеете в виду относительно корня или только что добавленного узла? (Возможно, это не имеет значения). Поправьте меня, если я ошибаюсь, но вы говорите следующее: у меня может быть два алгоритма, единственное отличие которых состоит в том, что один делает нетривиальное, но действительное изменение, которое по-прежнему поддерживает красно-черную целостность. Может быть, например, изменить оба узла на уровне 2 на черный (поскольку это не изменит высоту черного листа). Поэтому я доказываю, что алгоритмы не уникальны. - person Ryan; 19.07.2011
comment
@Ryan, O(1) относительно корня. Вы правы, это идея, хотя, как я отметил в конце, это не означает, что это степень дисперсии алгоритмов RB. Могут быть и более общие различия. - person davin; 19.07.2011
comment
Итак, простите мое поспешное обобщение здесь, но можно ли сказать, что инвариантом для вставки/удаления любого красно-черного алгоритма является просто выполнение 4 (или 5) красно-черных свойств, независимо от того, как дерево манипулируется для Сделай так? Может быть, я неправильно сформулировал это (просто пытаюсь встроить в это больше интуиции) - person Ryan; 19.07.2011
comment
@Ryan, действительно, это был бы правильный способ классифицировать все алгоритмы RB, которые гибки в том смысле, что позволяют оптимизировать и варьировать. - person davin; 20.07.2011

arrow_upward
2
arrow_downward

Нет множественных алоритмов.

Начнем с этих двух предложений:

  • Количество красно-черных деревьев с 4 внутренними узлами равно 3.
  • Количество красно-черных деревьев с 5 внутренними узлами равно 8.

Теперь представьте, что существует уникальный алгоритм добавления узла к красно-черному дереву с 4 внутренними узлами. Тогда должно быть всего 3 красно-черных Дерева с 5 внутренними узлами, так как алгоритм приводит к одному единственному результату.

Это абсурд, так как количество красно-черных деревьев с 5 внутренними узлами равно 8.

(см. ПРИНЦИП PIGEONHOLE)

Поэтому существует несколько «красно-черных» алгоритмов

Надеюсь, я понял, что вы имели в виду.

person Ricky Bobby    schedule 19.07.2011
comment
Мне нравится этот подход, но мне нужно подумать об этом немного больше (абстрагирование слишком многих деталей сбивает меня с толку на этом этапе). - person Ryan; 19.07.2011
comment
Я вижу, что ты сейчас говоришь. Однако, если мы добавим случайный узел к 4-узловому RB-дереву, результатом может быть только 8 RB-деревьев с 5 внутренними узлами. Вопрос, однако, заключается в следующем: зафиксировав узел a, который мы добавим, существуют ли несколько решений с пятью внутренними узлами для данного узла a? - person Ryan; 19.07.2011
comment
Для дерева с 4 узлами это не более 4 позиций, в которые вы можете добавить узел, чтобы создать дерево с 5 узлами. Если существует 8 5 деревьев узлов, то в списке есть способ добавить узел с более чем 2 возможными деревьями RB-выхода (принцип PigeonHole), и поэтому существует один a, который отвечает на ваш вопрос. Но вы не можете доказать это для всех «а». На самом деле доказательство Давина доказывает это только в одной ситуации, а не для всех добавленных узлов (см. второй комментарий в доказательствах Давина: в определенных ситуациях - person Ricky Bobby; 20.07.2011
comment
Разве нет 6 возможных позиций для добавления узла в дерево с 4 внутренними узлами? - person Ryan; 20.07.2011