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

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

7 голосов
/ 19 июля 2011

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

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

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

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

Ответы [ 2 ]

7 голосов
/ 19 июля 2011

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

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

    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, которые отличаются более фундаментальными способами.

2 голосов
/ 19 июля 2011

Нет, есть многократные алгоритмы.

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

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

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

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

(ср. ПРИНЦИП КУКОЛЫ )

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

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

...