Colorir uma árvore binária para ser uma árvore vermelho-preta

Uma pergunta comum da entrevista é fornecer um algoritmo para determinar se uma árvore binária é equilibrada em altura (definição de árvore AVL).

Eu queria saber se podemos fazer algo semelhante com árvores vermelho-pretas.

Dada uma árvore binária arbitrária e sem cor (com nós NULL), existe um algoritmo "rápido" que pode determinar se podemos colorir (e encontrar uma coloração) os nós Vermelho / Preto para que eles satisfaçam todas as propriedades de uma árvore Vermelho-Preto (definição como nesta pergunta )?

Um pensamento inicial era que podemos apenas remover os nós NULL e tentar verificar recursivamente se a árvore resultante pode ser uma árvore vermelho-preta, mas isso não pareceu levar a lugar algum.

Eu fiz (uma breve) pesquisa na web de artigos, mas não consegui encontrar nenhum que pareça lidar com esse problema.

É possível que eu esteja perdendo algo simples.

algorithms data-structures binary-trees search-trees Aryabhata
fonte

Tenho certeza de que uma árvore pode ser de cor vermelho-preto se cada nó for o caminho mais longo para um nó NULL, não mais que duas vezes mais que o menor. Isso é rápido o suficiente?

precisa saber é o seguinte

Respostas:

Se, para cada nó de uma árvore, o caminho mais longo para um nó folha não for mais do que duas vezes maior que o menor, a árvore terá uma coloração vermelho-preta.

Aqui está um algoritmo para descobrir a cor de qualquer nó 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

Aqui n.black-quotaestá o número de nós pretos que você espera ver indo para uma folha, do nó ne n.min-heighté a distância para a folha mais próxima.

Para uma brevidade da notação, sejam , e . $b(n) =$ n.black-quota $h(n) =$ n.height $m(n) =$ n.min-height

Teorema: Fixar uma árvore binária . Se para cada nó , e para o nó , $T$ $n \in T$ $h(n) \leq 2m(n)$ $r = \text{root}(T)$ entãotem uma coloração vermelho-preta com exatamentenós pretos em todos os caminhos, da raiz às folhas. $b(r) \in [\frac{1}{2}h(r), m(r)]$ $T$ $b(r)$

Prova: Indução sobre . $b(n)$

Verifique se todas as quatro árvores de altura uma ou duas satisfazem o teorema com . $b(n) = 1$

Por definição de árvore vermelho-preta, a raiz é preta. Seja um nó com um pai preto tal que $n$ $p$ . Então $b(p) \in [\frac{1}{2}h(p), m(p)]$ , e . $b(n) = b(p) -1$ $h(n) = h(p)-1$ $h(n) \geq m(n) \geq m(p)-1$

Suponha que o teorema seja válido para todas as árvores com raiz , . $r$ $b(r) < b(q)$

Se , então pode ser de cor vermelho-preto pela suposição indutiva. $b(n) = m(n)$ $n$

Se então $b(p) = \frac{1}{2}h(p)$ . não satisfaz a suposição indutiva e, portanto, deve ser vermelho. Sejaum filho de $b(n) = \lceil \frac{1}{2}h(n) \rceil - 1$ $n$ $c$ $n$ . e $h(c) = h(p)-2$ . Entãopode ser de cor vermelho-preto pela suposição indutiva. $b(c) = b(p)-1 = \frac{1}{2}h(p)-1 = \frac{1}{2}h(c)$ $c$

Observe que, pelo mesmo raciocínio, se , então e um filho de satisfazem a suposição indutiva. Portanto, poderia ter qualquer cor. $b(n) \in (\frac{1}{2}h(r), m(r))$ $n$ $n$ $n$

Karolis Juodelė
fonte

@Aryabhata, qualquer travessia é boa, desde que o pai seja visto antes de seus filhos. Não tenho uma prova formal escrita, mas tenho uma ideia de como ficaria. Vou tentar escrever algo quando puder.

usar o seguinte código

@Aryabhata, adicionei uma prova. Desculpa por demorar tanto.

usar o seguinte código

@Aryabhata, a idéia é que, se

de algum nó

estiver dentro de certos limites, um filho ou neto

pode ter

dentro desses mesmos limites. Tendo

nesses limites pode corresponder a

b (p)

$b(p)$

p

$p$

c

$c$

p

$p$

b (c)

$b(c)$

b (n)

$b(n)$

n

$n$ ser preto. A maior parte da prova é de cerca de delimitadora

de uma criança ou neto, dado

do pai ou avô. Sua árvore é certamente colorida.

h

$h$

m

$m$

h

$h$

m

$m$

, filho esquerdo é preto e filho direito é vermelho, o caminho do comprimento 16 é

, o caminho do comprimento 8 é

, os caminhos 9 e 12 podem ter vários corantes válidos.

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$

usar o seguinte código

Há uma pergunta sobre esta resposta .

precisa saber é o seguinte

Eu acredito que a resposta de Karolis está correta (e uma caracterização bastante agradável de árvores vermelho-pretas, fornecendo um algoritmo de tempo ), só queria adicionar outra resposta possível. $O(n)$

Uma abordagem é usar a programação dinâmica.

Dada uma árvore, para cada nó , você constrói dois conjuntos: e que contêm as possíveis alturas negras da subárvore enraizada em . contém as alturas pretas assumindo que é colorido de vermelho e assumindo que é colorido de preto. $n$ $S_R(n)$ $S_B(n)$ $n$ $S_R(n)$ $n$ $S_B(n)$ $n$

Agora, dados os conjuntos para e (isto é, filhos diretos de ), podemos calcular os conjuntos correspondentes para , fazendo interseções e uniões apropriadas (e incrementando conforme necessário). $n.Left$ $n.Right$ $n$ $n$

Acredito que isso seja um algoritmo de tempo . $O(n \log n)$

Aryabhata
fonte