Цвет бинарного дерева, чтобы быть красно-черным деревом

Обычный вопрос интервью - дать алгоритм для определения того, является ли данное двоичное дерево сбалансированным по высоте (определение дерева AVL).

Мне было интересно, можем ли мы сделать что-то подобное с красно-черными деревьями.

Учитывая произвольное неокрашенное двоичное дерево (с узлами NULL), существует ли «быстрый» алгоритм, который может определить, можем ли мы покрасить (и найти раскраску) узлы в красный / черный, чтобы они удовлетворяли всем свойствам красно-черного дерева (определение как в этом вопросе )?

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

Я сделал (краткий) поиск в Интернете документов, но, похоже, не смог найти ни одной, которая, кажется, имеет дело с этой проблемой.

Возможно, мне не хватает чего-то простого.

algorithms data-structures binary-trees search-trees Арьябхата
источник

Я почти уверен, что дерево может быть красно-черного цвета, если для каждого узла, самый длинный путь от него к узлу NULL не более чем в два раза длиннее, чем самый короткий. Это достаточно быстро?

Каролис Юоделе

Ответы:

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

Вот алгоритм, чтобы выяснить цвет любого узла n

if n is root,
    n.color = black
    n.black-quota = height n / 2, rounded up.

else if n.parent is red,
    n.color = black
    n.black-quota = n.parent.black-quota.

else (n.parent is black)
    if n.min-height < n.parent.black-quota, then
        error "shortest path was too short"
    else if n.min-height = n.parent.black-quota then
        n.color = black
    else (n.min-height > n.parent.black-quota)
        n.color = red
    either way,
        n.black-quota = n.parent.black-quota - 1

Вот n.black-quotaколичество черных узлов, которые вы ожидаете увидеть идущими к листу от узла, nи n.min-heightрасстояние до ближайшего листа.

Для краткости обозначений пусть , и . $b(n) =$ n.black-quota $h(n) =$ n.height $m(n) =$ n.min-height

Теорема: Фикс бинарного дерева . Если для каждого узла , и для узла , $T$ $n \in T$ $h(n) \leq 2m(n)$ $r = \text{root}(T)$ тогдаимеет красно-черную окраску с ровночерными узлами на каждом пути от корня до листа. $b(r) \in [\frac{1}{2}h(r), m(r)]$ $T$ $b(r)$

Доказательство: индукция по . $b(n)$

Убедитесь, что все четыре дерева высотой один или два удовлетворяют теореме с . $b(n) = 1$

По определению красно-черного дерева, корень черный. Пусть узел с черным родителем такой, что $n$ $p$ . Тогда,и. $b(p) \in [\frac{1}{2}h(p), m(p)]$ $b(n) = b(p) -1$ $h(n) = h(p)-1$ $h(n) \geq m(n) \geq m(p)-1$

Предположим, что теорема верна для всех деревьев с корнем , . $r$ $b(r) < b(q)$

Если , то может иметь красно-черный цвет по предположению индуктивности. $b(n) = m(n)$ $n$

Если то $b(p) = \frac{1}{2}h(p)$ . не удовлетворяет индуктивному предположению и поэтому должно быть красным. Пусть- дитя. и $b(n) = \lceil \frac{1}{2}h(n) \rceil - 1$ $n$ $c$ $n$ $h(c) = h(p)-2$ . Тогдаможет быть красно-черным, окрашенным индуктивным предположением. $b(c) = b(p)-1 = \frac{1}{2}h(p)-1 = \frac{1}{2}h(c)$ $c$

Отметим, что по тем же соображениям, если , то ии потомокудовлетворяют индуктивному предположению. Поэтомуможет иметь любой цвет. $b(n) \in (\frac{1}{2}h(r), m(r))$ $n$ $n$ $n$

Каролис Юоделе
источник

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

Каролис Юоделе

@ Арьябхата, я добавил доказательство. Извини, что так долго.

Каролис Юоделе

@Aryabhata, идея состоит в том, что если

некоторого узла

находится в пределах определенных границ, у ребенка или внука

из

может быть

в этих же пределах. Наличие

в этих границах может соответствовать

являющемуся черным. Большая часть доказательств касается ограничения

ребенка или внука, учитывая

родителя или деда. Ваше дерево, безусловно, раскрашено.

b (p)

$b(p)$

p

$p$

c

$c$

p

$p$

b (c)

$b(c)$

b (n)

$b(n)$

n

$n$

h

$h$

m

$m$

h

$h$

m

$m$

, левый дочерний элемент черного цвета, а правый дочерний элемент красного цвета, путь длины 16 -

, путь длины 8 -

, пути 9 и 12 могут иметь несколько действительных расцветок.

b (r o o t) = 8

$b(root) = 8$

b r b r b r \dots

$brbrbr\dots$

b b b b b b b b

$bbbbbbbb$

Каролис Юоделе

Есть вопрос об этом ответе .

Дэвид Ричерби

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

Одним из подходов является использование динамического программирования.

Учитывая дерево, для каждого узла вы создаете два набора: и которые содержат возможные высоты черного для поддерева с корнем в . содержит высоты черного цвета, предполагая, что окрашен в красный цвет, а предполагая, что окрашен в черный цвет. $n$ $S_R(n)$ $S_B(n)$ $n$ $S_R(n)$ $n$ $S_B(n)$ $n$

Теперь даны наборы для и (то есть прямые потомки ), мы можем вычислить соответствующие множества для , взяв соответствующие пересечения и объединения (и увеличивая при необходимости). $n.Left$ $n.Right$ $n$ $n$

Я полагаю, что это будет алгоритм времени. $O(n \log n)$

Арьябхата
источник