Árvores rubro-negras

A árvore rubro-negra convencional, suas cinco propriedades, a altura negra e a demonstração de que a altura é sempre O(log n).

A árvore AVL evita a degeneração da árvore de busca com um critério rígido: em todo nó. A árvore rubro-negra resolve o mesmo problema de outra forma. Cada nó recebe uma cor, vermelha ou preta, e algumas regras sobre as cores garantem que nenhum caminho da raiz até uma folha seja mais do que duas vezes mais longo que qualquer outro. Isso basta para a altura ser .

Esta página trata da árvore rubro-negra convencional: o que ela é, suas propriedades e por que elas garantem o balanceamento. A implementação que vamos estudar é a de uma variante mais simples, a árvore rubro-negra esquerdista, que é o assunto da próxima página.

Definição

Definição 1(Árvore rubro-negra)

Uma árvore rubro-negra é uma árvore binária de busca em que cada nó tem, além da chave e dos dois ponteiros, uma cor, vermelha ou preta, e que satisfaz as cinco propriedades:

todo nó é vermelho ou preto;
a raiz é preta;
toda folha NULL é preta;
se um nó é vermelho, os seus dois filhos são pretos (não há dois vermelhos seguidos em nenhum caminho);
para cada nó, todos os caminhos desse nó até as folhas NULL abaixo dele passam pelo mesmo número de nós pretos.

O nome vem da cor dos nós (rubro é vermelho). Em inglês, a árvore é chamada de red-black tree, e também aparece em português como árvore vermelho-preta.

As folhas `NULL`

A propriedade 3 trata os ponteiros NULL como se fossem folhas de verdade, todas pretas. Elas importam na hora de contar os nós pretos de um caminho (propriedade 5). Como todo nó sem filhos termina em dois NULL, costumamos omiti-las nos desenhos: as duas representações abaixo são a mesma árvore.

A mesma árvore rubro-negra desenhada duas vezes. A raiz 10 é preta; os filhos 5 e 15 são vermelhos; os netos 2, 7, 12 e 20 são pretos. Em (a), cada um dos quatro netos tem dois quadradinhos pretos pendurados, que são as folhas NULL; em (b), as folhas NULL não aparecem — Uma árvore rubro-negra (a) com as folhas NULL, desenhadas como quadradinhos pretos, e (b) sem elas.

Nas figuras desta página e da próxima, a aresta que chega a um nó vermelho também é desenhada em vermelho. Isso vai ajudar a ler a variante esquerdista.

Altura negra

A propriedade 5 dá origem a uma medida importante.

Definição 2(Altura negra)

A altura negra de um nó , denotada (do inglês black height), é o número de nós pretos em um caminho de até uma folha NULL, sem contar o próprio e contando a folha NULL. A altura negra de uma folha NULL é 0, e a altura negra da árvore é a da raiz.

Pela propriedade 5, esse número não depende do caminho escolhido, então está bem definida para todo nó. Na árvore abaixo, a altura negra de cada nó está anotada ao lado dele.

Árvore rubro-negra com as folhas NULL e a altura negra anotada em cada nó. Raiz 7 preta, com bh igual a 2. À esquerda, 3 preto, com bh 1. À direita, 18 vermelho, com bh 2; 18 tem os filhos pretos 10 e 22, ambos com bh 1; 10 tem os filhos vermelhos 8 e 11, e 22 tem só o filho direito vermelho 26, todos com bh 1 — Uma árvore rubro-negra com a altura negra de cada nó. A altura negra da árvore é 2.

Confira as propriedades: a raiz 7 é preta; nenhum vermelho (18, 8, 11 e 26) tem filho vermelho; e todo caminho da raiz até uma folha NULL passa por exatamente dois nós pretos abaixo da raiz. Por exemplo, NULL passa pelo 3 e pela folha, e NULL passa pelo 10 e pela folha.

Rubro-negra não exige |fb| ≤ 1

Na árvore acima, a SAE da raiz (só o 3) tem altura 0, e a SAD (com raiz 18) tem altura 2. O fator de balanceamento da raiz é : a árvore não é uma AVL e, mesmo assim, é uma rubro-negra válida. É o que vimos na página de árvores balanceadas: estar balanceada é ter a altura garantidamente , e cada família usa um critério diferente para garantir isso.

Questão

Na árvore da figura, o que acontece se o nó 26 for pintado de preto?

Árvores que não são rubro-negras

Cada árvore abaixo viola uma condição diferente. As folhas NULL estão desenhadas porque fazem diferença na contagem dos pretos.

Quatro árvores, cada uma com uma violação anotada. (a) Raiz 10 vermelha, com os filhos pretos 3 e 15: viola a propriedade 2. (b) Raiz 7 preta, com os filhos vermelhos 3 e 18, e 22 vermelho como filho direito de 18: 18 e 22 são vermelhos seguidos, propriedade 4. (c) A mesma forma, com 22 preto: o caminho até as folhas de 22 tem um preto a mais que os outros, propriedade 5. (d) Raiz 7 preta, com 15 preto à esquerda, 18 preto à direita e 2 vermelho como filho direito de 18: as cores estão corretas, mas 15 está à esquerda de 7 e 2 à direita de 18, então não é árvore de busca — Quatro árvores que não são rubro-negras.

A árvore (d) lembra que a rubro-negra é, antes de tudo, uma árvore binária de busca: as cores se somam às regras de ordem, não as substituem.

Pergunta

Uma árvore rubro-negra pode ter apenas nós pretos? Se puder, o que a propriedade 5 diz sobre a forma dessa árvore?

Ver respostaEsconder resposta

Pode. Nenhuma propriedade exige nós vermelhos. Mas, sem vermelhos, o número de nós pretos de um caminho é o número de nós do caminho, e a propriedade 5 passa a exigir que todos os caminhos da raiz até uma folha NULL tenham o mesmo comprimento. Ou seja, todas as folhas estão no mesmo nível: a árvore é cheia. Os nós vermelhos são o que dá flexibilidade à rubro-negra para ter qualquer número de nós.

Por que as cores garantem o balanceamento

As propriedades 4 e 5, juntas, limitam o quanto um caminho pode ser mais longo que outro. Na figura, o caminho mais curto até uma folha NULL só passa por nós pretos, e o mais longo alterna pretos e vermelhos.

Árvore rubro-negra com raiz 10 preta, filho esquerdo 5 preto e filho direito 20 vermelho; 20 tem os filhos pretos 15 e 25, e 25 tem o filho direito vermelho 30. Em azul, o caminho mais curto: 10, 5 e a folha NULL esquerda de 5, com 2 pretos abaixo da raiz. Em amarelo, o caminho mais longo: 10, 20, 25, 30 e uma folha NULL de 30, com 2 pretos e 2 vermelhos — O caminho mais curto e o mais longo da raiz até uma folha NULL têm o mesmo número de pretos.

Proposição 1

Em uma árvore rubro-negra, nenhum caminho da raiz até uma folha NULL tem mais que o dobro de arestas de outro.

Demonstraçãotente antes de abrir

Seja . Todo caminho da raiz até uma folha NULL passa, abaixo da raiz, por exatamente nós pretos (propriedade 5, contando a folha). Os demais nós do caminho são vermelhos, e cada vermelho é seguido, no caminho, por um filho preto (propriedade 4), que pode ser a própria folha NULL. Então há no máximo um vermelho para cada preto, e o caminho tem entre e nós abaixo da raiz, isto é, entre e arestas. Logo, o mais longo tem no máximo arestas, e o mais curto, no mínimo .

Daqui sai a altura logarítmica. Primeiro, mostramos que uma altura negra grande obriga a árvore a ter muitos nós.

Lema 1

A subárvore com raiz em um nó tem pelo menos nós (sem contar as folhas NULL).

Demonstraçãotente antes de abrir

Por indução na altura de . Se é uma folha NULL, então e a subárvore tem nós.

Se é um nó de verdade, cada filho de (que pode ser NULL) satisfaz se é preto e se é vermelho. Em todo caso, . Como tem altura menor que a de , a hipótese de indução diz que a subárvore de tem pelo menos nós. Somando as duas subárvores e o próprio :

Teorema 1(Altura da árvore rubro-negra)

Uma árvore rubro-negra com nós tem altura

Em particular, , e a família das árvores rubro-negras é balanceada.

Demonstraçãotente antes de abrir

Considere o nó mais fundo da árvore, na profundidade , e uma das suas folhas NULL. O caminho da raiz até essa folha tem arestas, ou seja, nós abaixo da raiz, o último deles a folha NULL, que é preta. Como na Proposição 1, cada vermelho desse caminho é seguido por um preto, então pelo menos metade desses nós são pretos, e . Pelo Lema 1,

isto é, , e .

Compare com o teorema da altura da AVL, que dá cerca de . A rubro-negra tolera árvores um pouco mais altas, porque o seu critério é mais relaxado; em troca, como veremos a seguir, precisa de menos reestruturações para manter as propriedades. Com um milhão de chaves, o teorema garante altura no máximo 38 na rubro-negra e 27 na AVL, contra 19 da árvore completa.

Inserção e remoção: manter as propriedades

As operações de busca, mínimo, máximo e percurso em ordem são exatamente as da ABB: as cores não interferem nelas. Já a inserção e a remoção precisam terminar com uma árvore que ainda satisfaça as cinco propriedades.

Inserção

A inserção começa como na ABB: o novo nó entra no lugar de um NULL. A pergunta é que cor ele deve receber.

À esquerda, a árvore com raiz 10 e os filhos 5 e 15, todos pretos, com altura negra 2. Em (a), o 20 entra como filho direito de 15, pintado de preto: os caminhos que passam pelo 20 ganham um preto a mais, violando a propriedade 5. Em (b), o 20 entra vermelho, e nenhuma altura negra muda — O novo nó entra vermelho: um nó preto mudaria a altura negra de alguns caminhos e não a de outros.

Um nó novo preto acrescentaria um preto apenas aos caminhos que passam por ele, violando a propriedade 5 em todos os ancestrais, um problema espalhado pela árvore inteira. Um nó novo vermelho não muda nenhuma altura negra. No máximo, ele viola a propriedade 2 (se for a raiz, basta pintá-lo de preto) ou a propriedade 4 (se o pai também for vermelho). Esse segundo problema é local, e é corrigido olhando o tio do novo nó (o irmão do pai):

Duas situações após inserir um nó X vermelho com pai P vermelho e avô G preto. (a) O tio T, outro filho de G, é vermelho: P e T ficam pretos e G fica vermelho, e as alturas negras não mudam; se o pai de G for vermelho, o problema se repete dois níveis acima. (b) O tio T é preto, aqui uma folha NULL: uma rotação à direita em G, seguida da troca das cores de P e G, deixa P preto na raiz da subárvore, com X e G vermelhos como filhos, e o problema termina ali — Os dois casos da inserção na rubro-negra convencional, conforme a cor do tio T.

se o tio é vermelho, basta recolorir: o pai e o tio ficam pretos e o avô fica vermelho. As alturas negras não mudam, mas o avô vermelho pode ter pai vermelho, e o problema sobe dois níveis;
se o tio é preto, uma ou duas rotações, com uma recoloração, resolvem o problema de vez.

Os dois casos têm versões espelhadas (com o pai à direita do avô), e o caso do tio preto tem uma variante com rotação dupla, como na AVL. A inserção faz no máximo duas rotações, mas a implementação precisa tratar todos esses casos.

Remoção

Remover um nó vermelho do fundo da árvore é inofensivo: nenhum caminho perde um preto. O problema é remover um nó preto.

À esquerda, a árvore com raiz 10 e os filhos 5 e 15, todos pretos, com as folhas NULL; o 5 está destacado. Depois de remover o 5, a raiz 10 tem uma folha NULL à esquerda e o 15 à direita: os caminhos pela esquerda passam por 1 preto abaixo de 10, e os pela direita por 2, violando a propriedade 5 — Remover um nó preto deixa os caminhos que passavam por ele com um preto a menos.

Os caminhos que passavam pelo nó removido ficam com um preto a menos, e a propriedade 5 deixa de valer. A remoção convencional compensa essa falta com recolorações e até três rotações, em vários casos e seus espelhos. É a operação mais trabalhosa da árvore, e é por isso que ela é a grande vantagem da variante da próxima página: na rubro-negra esquerdista, a remoção é feita com as mesmas poucas operações da inserção, e o nó removido é sempre vermelho.

Onde a rubro-negra aparece

A rubro-negra convencional é a árvore balanceada mais usada na prática: o std::map e o std::set do C++, o TreeMap do Java e várias estruturas do núcleo do Linux são árvores rubro-negras. O motivo é o número pequeno e limitado de rotações por operação.

Referências

T. H. Cormen, C. E. Leiserson, R. L. Rivest e C. Stein. Algoritmos: Teoria e Prática. 3ª ed. Elsevier, 2012. Capítulo 13.
A. Backes. Estrutura de Dados Descomplicada em Linguagem C. Elsevier, 2016.
R. Sedgewick e K. Wayne. Algorithms. 4ª ed. Addison-Wesley, 2011. Seção 3.3.
D. Galles. Visualização interativa da árvore rubro-negra. University of San Francisco.

Nesta página