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

16

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.

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:

12

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 , h ( n ) = e m ( n ) = .b(n)= n.black-quotah(n)= n.heightm(n)= n.min-height

Teorema: Fixar uma árvore binária . Se para cada nó n T , h ( n ) 2 m ( n ) e para o nó r = raiz ( T ) , b ( r ) [ 1TnTh(n)2m(n)r=root(T)entãoTtem uma coloração vermelho-preta com exatamenteb(r)nós pretos em todos os caminhos, da raiz às folhas.b(r)[12h(r),m(r)]Tb(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 p tal que b ( p ) [ 1np. Entãob(n)=b(p)-b(p)[12h(p),m(p)] , h ( n ) = h ( p ) - 1 e h ( n ) m ( n ) m ( p ) - 1 .b(n)=b(p)1h(n)=h(p)1h(n)m(n)m(p)1

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

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

Se entãob(n)=1b(p)=12h(p). nnão satisfaz a suposição indutiva e, portanto, deve ser vermelho. Sejacum filho denb(n)=12h(n)1ncn . e b ( c ) = b ( p ) - 1 = 1h(c)=h(p)2. Entãocpode ser de cor vermelho-preto pela suposição indutiva.b(c)=b(p)1=12h(p)1=12h(c)c

Observe que, pelo mesmo raciocínio, se , então n e um filho de n satisfazem a suposição indutiva. Portanto, n poderia ter qualquer cor.b(n)(12h(r),m(r))nnn

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ó p estiver dentro de certos limites, um filho ou neto c de p pode ter b ( c ) dentro desses mesmos limites. Tendo b ( n ) nesses limites pode corresponder a nb(p)pcpb(c)b(n)n ser preto. A maior parte da prova é de cerca de delimitadora e m de uma criança ou neto, dado h e m do pai ou avô. Sua árvore é certamente colorida. b ( r o o thmhm , filho esquerdo é preto e filho direito é vermelho, o caminho do comprimento 16 é b r b r b r , o caminho do comprimento 8 é b b b b b b b b b , os caminhos 9 e 12 podem ter vários corantes válidos. b(root)=8brbrbrbbbbbbbb
usar o seguinte código
Há uma pergunta sobre esta resposta .
precisa saber é o seguinte
2

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: S R ( n ) e S B ( n ) que contêm as possíveis alturas negras da subárvore enraizada em n . S R ( n ) contém as alturas pretas assumindo que n é colorido de vermelho e S B ( n ) assumindo que n é colorido de preto.nSR(n)SB(n)nSR(n)nSB(n)n

Agora, dados os conjuntos para e n . R i g h t (isto é, filhos diretos de n ), podemos calcular os conjuntos correspondentes para n , fazendo interseções e uniões apropriadas (e incrementando conforme necessário).n.Leftn.Rightnn

Acredito que isso seja um algoritmo de tempo .O(nlogn)

Aryabhata
fonte