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

16

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

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

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

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

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

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

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

Ответы:

12

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

Вот алгоритм, чтобы выяснить цвет любого узла 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расстояние до ближайшего листа.

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

Теорема: Фикс бинарного дерева . Если для каждого узла п T , ч ( п ) 2 м ( п ) и для узла г = корень ( Т ) , б ( г ) [ 1TnTh(n)2m(n)r=root(T)тогдаTимеет красно-черную окраску с ровноb(r)черными узлами на каждом пути от корня до листа.b(r)[12h(r),m(r)]Tb(r)

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

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

По определению красно-черного дерева, корень черный. Пусть узел с черным родителем p такой, что b ( p ) [ 1np. Тогдаb(n)=b(p)-1,h(n)=h(p)-1иh(n)m(n)m(p)-1.b(p)[12h(p),m(p)]b(n)=b(p)1h(n)=h(p)1h(n)m(n)m(p)1

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

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

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

Отметим, что по тем же соображениям, если , то иn,и потомокnудовлетворяют индуктивному предположению. Поэтомуnможет иметь любой цвет.b(n)(12h(r),m(r))nnn

Каролис Юоделе
источник
@Aryabhata, любой обход в порядке, если родитель виден перед своими детьми. У меня нет написанного формального доказательства, но у меня есть представление о том, как оно будет выглядеть. Я постараюсь написать что-нибудь, когда смогу.
Каролис Юоделе
@ Арьябхата, я добавил доказательство. Извини, что так долго.
Каролис Юоделе
@Aryabhata, идея состоит в том, что если некоторого узла p находится в пределах определенных границ, у ребенка или внука c из p может быть b ( c ) в этих же пределах. Наличие b ( n ) в этих границах может соответствовать n, являющемуся черным. Большая часть доказательств касается ограничения h и m ребенка или внука, учитывая h и m родителя или деда. Ваше дерево, безусловно, раскрашено. б ( г о о тb(p)pcpb(c)b(n)nhmhm , левый дочерний элемент черного цвета, а правый дочерний элемент красного цвета, путь длины 16 - b r b r b r , путь длины 8 - b b b b b b b b b , пути 9 и 12 могут иметь несколько действительных расцветок. b(root)=8brbrbrbbbbbbbb
Каролис Юоделе
Есть вопрос об этом ответе .
Дэвид Ричерби
2

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

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

Учитывая дерево, для каждого узла вы создаете два набора: S R ( n ) и S B ( n ), которые содержат возможные высоты черного для поддерева с корнем в n . S R ( n ) содержит высоты черного цвета, предполагая, что n окрашен в красный цвет, а S B ( n ), предполагая, что n окрашен в черный цвет.nSR(n)SB(n)nSR(n)nSB(n)n

Теперь даны наборы для и н . R i g h t (то есть прямые потомки n ), мы можем вычислить соответствующие множества для n , взяв соответствующие пересечения и объединения (и увеличивая при необходимости).n.Leftn.Rightnn

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

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