Rubro-negra esquerdista (LLRB)

A árvore rubro-negra convencional garante altura , mas a sua inserção e, principalmente, a sua remoção têm muitos casos e casos espelhados. Em 2008, Robert Sedgewick propôs uma variante com uma regra a mais, que elimina os casos espelhados: a árvore rubro-negra esquerdista, ou LLRB (do inglês left-leaning red-black tree). Com ela, a inserção e a remoção são escritas com três operações elementares e uma única função de correção.

Esta é a árvore balanceada que vamos implementar na disciplina.

Definição

Toda LLRB é, em particular, uma árvore rubro-negra, então ela herda o teorema da altura: .

Duas consequências diretas da propriedade 6, que vamos usar mais adiante:

Em particular, um nó sem filho esquerdo também não tem filho direito: é uma folha. Isso vai simplificar a remoção do menor.

O TAD

A interface é a mesma da ABB e da AVL (pares chave e valor, com chaves únicas), mais uma operação pública nova, removeMenorArvore. O nó troca a altura da AVL por uma cor:

typedef enum { VERMELHO, PRETO } Cor;

typedef struct no {
    Chave chave;
    Valor valor;
    Cor cor;            /* cor do nó (NULL conta como preto) */
    struct no *esq;
    struct no *dir;
} No;

Quase todas as decisões da árvore perguntam "esse filho é vermelho?". A função noEhVermelho responde false para NULL, que é a propriedade 3 (folhas NULL são pretas) traduzida em código. Com ela, podemos perguntar sobre r->esq->esq sem testar antes se r->esq existe, desde que r->esq seja vermelho (e, portanto, não nulo) ou que saibamos por outro motivo que ele não é NULL.

/* NULL conta como preto (as folhas NULL são pretas) */
static bool noEhVermelho(const No *r) {
    return r != NULL && r->cor == VERMELHO;
}

Para imprimir a árvore deitada (raiz à esquerda e SAD em cima), cada chave aparece seguida de (V) ou (P), a sua cor.

Rotações

As rotações são as mesmas da AVL e são nomeadas da mesma forma, pela direção: na rotação à esquerda em , o filho direito sobe; na rotação à direita em , o filho esquerdo sobe. A diferença é que, na LLRB, a rotação também move a cor: é sempre vermelho, sobe e herda a cor que tinha, e desce pintado de vermelho.

/* Rotação à esquerda em A: o filho direito B (vermelho) sobe */
static No *rotacaoEsquerda(No *A) {
    No *B = A->dir;
    A->dir = B->esq;
    B->esq = A;
    B->cor = A->cor;        /* B herda a cor de A */
    A->cor = VERMELHO;      /* A desce e fica vermelho */
    return B;
}

/* Rotação à direita em A: o filho esquerdo B (vermelho) sobe */
static No *rotacaoDireita(No *A) {
    No *B = A->esq;
    A->esq = B->dir;
    B->dir = A;
    B->cor = A->cor;
    A->cor = VERMELHO;
    return B;
}

A rotação à esquerda transforma um "vermelho à direita" em um "vermelho à esquerda", e a rotação à direita faz o contrário. É assim que a LLRB move os vermelhos de um lado para o outro.

A hipótese de vermelho é essencial: se fosse preto, os caminhos até perderiam um preto. Em todos os usos da LLRB, a rotação é aplicada justamente para mover um vermelho, e a hipótese vale. O que a rotação pode fazer é criar, temporariamente, dois vermelhos seguidos ou um vermelho à direita, que as outras operações corrigem.

Inversão de cores

A terceira operação inverte a cor de um nó e a dos seus dois filhos.

static void trocaCor(No *r) {
    r->cor = r->cor == VERMELHO ? PRETO : VERMELHO;
}

/* Inverte a cor do nó e a dos seus dois filhos */
static void inverteCorNo(No *r) {
    trocaCor(r);
    if (r->esq != NULL)
        trocaCor(r->esq);
    if (r->dir != NULL)
        trocaCor(r->dir);
}

Na inserção, a inversão é aplicada a um nó preto com dois filhos vermelhos, "empurrando" o vermelho para cima. Na remoção, ela é usada no sentido contrário, para trazer um vermelho para baixo. Em ambos os casos, ela tem efeitos colaterais: pode criar dois vermelhos seguidos (se o pai de for vermelho) e pode pintar a raiz de vermelho.

Inserção

Como na rubro-negra convencional, o novo nó entra vermelho, no lugar de um NULL, para não mudar nenhuma altura negra. Os problemas que ele pode criar são locais, e são corrigidos na volta da recursão, em cada nó do caminho, por três testes nesta ordem:

1. vermelho à direita (e preto à esquerda): viola a propriedade 6. Rotação à esquerda;
2. dois vermelhos seguidos à esquerda: viola a propriedade 4. Rotação à direita;
3. os dois filhos vermelhos: inversão de cores, que empurra o vermelho para o pai.

/* Corrige r na volta da recursão. Três testes, nesta ordem. */
static No *balanceia(No *r) {
    if (noEhVermelho(r->dir) && !noEhVermelho(r->esq))     /* vermelho à direita */
        r = rotacaoEsquerda(r);
    if (noEhVermelho(r->esq) && noEhVermelho(r->esq->esq)) /* dois vermelhos seguidos */
        r = rotacaoDireita(r);
    if (noEhVermelho(r->esq) && noEhVermelho(r->dir))      /* dois filhos vermelhos */
        inverteCorNo(r);
    return r;
}

O nome balanceia é o mesmo da AVL, e o papel também: corrigir o nó na volta da recursão e devolver a raiz (talvez nova) da subárvore. São três if independentes, e não uma cadeia de else if, porque um caso pode produzir o seguinte no mesmo nó: a rotação do caso 2 sempre deixa um nó com dois filhos vermelhos, que é o caso 3. Esquecer isso é o erro do Programa 1.

Com balanceia pronta, a inserção tem a mesma estrutura da inserção da AVL:

1. 1

   Desça como na ABB#

   Compare a chave com a do nó atual e desça para a esquerda ou para a direita até encontrar um NULL. Se encontrar a própria chave, só troque o valor.

2. 2

   Crie o nó vermelho#

   No lugar do NULL, crie o novo nó, sempre vermelho.

3. 3

   Volte corrigindo#

   Na volta da recursão, cada nó do caminho passa por balanceia, que aplica os três testes e devolve a raiz da subárvore; o pai a guarda em r->esq ou r->dir.

4. 4

   Pinte a raiz de preto#

   A inversão de cores pode ter pintado a raiz de vermelho. Pintá-la de preto nunca quebra a propriedade 5: todos os caminhos passam pela raiz.

static No *insereNo(No *r, Chave chave, Valor valor, bool *novo) {
    if (r == NULL) {
        *novo = true;
        return criaNo(chave, valor);
    }
    if (chave < r->chave)
        r->esq = insereNo(r->esq, chave, valor, novo);
    else if (chave > r->chave)
        r->dir = insereNo(r->dir, chave, valor, novo);
    else
        r->valor = valor;               /* chave já existe: atualiza */
    return balanceia(r);                /* na volta da recursão */
}

void insereArvore(Arvore *arvore, Chave chave, Valor valor) {
    bool novo = false;
    arvore->raiz = insereNo(arvore->raiz, chave, valor, &novo);
    arvore->raiz->cor = PRETO;          /* a raiz é sempre preta */
    if (novo)
        arvore->tamanho++;
}

A função criaNo é a da ABB, com novo->cor = VERMELHO;.

A figura mostra a inserção de 1, 3, 6, 7 e 4, nessa ordem, em uma árvore vazia. Cada quadro é a árvore inteira logo depois de uma operação, e o contorno destaca o nó onde ela foi aplicada.

A inserção do 4 é a mais interessante, porque passa pelos três casos. O 4 entra à esquerda do 6, que já era vermelho. Na volta, nada acontece no 6. No 7, o filho esquerdo 6 e o neto 4 são vermelhos (caso 2): rotação à direita e, em seguida, no mesmo nó, os dois filhos vermelhos (caso 3): inversão de cores. O 6 sobe vermelho, e, na raiz 3, ele é um vermelho à direita (caso 1): rotação à esquerda.

Remoção

Remover um nó vermelho do fundo da árvore é inofensivo; remover um nó preto tira um preto dos caminhos que passavam por ele (a figura da página anterior). A estratégia da LLRB é evitar esse problema antes que ele aconteça: na descida, à procura do nó a ser removido, vamos "carregando" um vermelho para baixo, de modo que, ao chegar lá, o nó removido seja vermelho.

Concretamente, a descida mantém um invariante: ao chegar a um nó (abaixo da raiz), ele ou o seu filho esquerdo é vermelho. Antes de descer, se o filho para onde vamos não satisfaz isso, uma das duas operações auxiliares abaixo empresta um vermelho de perto. Essas correções deixam violações temporárias (vermelhos à direita, nós com dois filhos vermelhos), que a mesma balanceia da inserção desfaz na volta da recursão. A remoção corrige a árvore na ida e na volta.

Operações auxiliares

Mover um vermelho para a esquerda. Usada quando vamos descer para a esquerda e tanto r->esq quanto r->esq->esq são pretos: não há vermelho no caminho à frente. A função supõe que r é vermelho (ou é a raiz) e garante que, depois dela, r->esq ou um filho de r->esq seja vermelho.

/* r é vermelho (ou a raiz), e r->esq e r->esq->esq são pretos:
   torna r->esq ou um filho dele vermelho */
static No *moveVermelhoParaEsquerda(No *r) {
    inverteCorNo(r);
    if (noEhVermelho(r->dir->esq)) {
        r->dir = rotacaoDireita(r->dir);
        r = rotacaoEsquerda(r);
        inverteCorNo(r);
    }
    return r;
}

A inversão de cores em r desce o vermelho para os dois filhos. Isso basta quando o irmão à direita não tem filho esquerdo vermelho (a). Quando tem, a inversão deixaria dois vermelhos seguidos à direita; nesse caso, um nó do lado direito é "emprestado": rotação à direita no irmão, rotação à esquerda em r e uma nova inversão de cores (b).

Mover um vermelho para a direita. Usada quando vamos descer para a direita e tanto r->dir quanto r->dir->esq são pretos. É o espelho da anterior, com uma simplificação: como os vermelhos ficam à esquerda, o vermelho que sobra do lado esquerdo está em r->esq->esq, e basta uma rotação à direita em r para trazê-lo.

/* r é vermelho (ou a raiz), e r->dir e r->dir->esq são pretos:
   torna r->dir ou um filho dele vermelho */
static No *moveVermelhoParaDireita(No *r) {
    inverteCorNo(r);
    if (noEhVermelho(r->esq->esq)) {
        r = rotacaoDireita(r);
        inverteCorNo(r);
    }
    return r;
}

No caso (b), o 15 termina como filho direito vermelho do 10, uma violação da propriedade 6 que existe só durante a descida: na volta, balanceia a corrige.

Remover o nó com a menor chave

Antes da remoção geral, vale estudar o caso mais simples: remover o nó com a menor chave, que é o nó mais à esquerda. A descida só vai para a esquerda, então só precisamos de moveVermelhoParaEsquerda.

1. 1

   Chegou ao menor?#

   Se r->esq é NULL, r é o menor. Pela Proposição 1, ele também não tem filho direito, e, pelo invariante da descida, ele é vermelho: basta liberá-lo e devolver NULL.

2. 2

   Prepare o caminho#

   Se r->esq e r->esq->esq são pretos, não há vermelho à frente: chame moveVermelhoParaEsquerda(r).

3. 3

   Desça#

   Remova o menor da SAE: r->esq = removeMenor(r->esq).

4. 4

   Volte corrigindo#

   Devolva balanceia(r). No fim, a função pública pinta a raiz de preto.

static No *removeMenor(No *r) {
    if (r->esq == NULL) {               /* o menor: é uma folha vermelha */
        free(r);
        return NULL;
    }
    if (!noEhVermelho(r->esq) && !noEhVermelho(r->esq->esq))
        r = moveVermelhoParaEsquerda(r);
    r->esq = removeMenor(r->esq);
    return balanceia(r);
}

void removeMenorArvore(Arvore *arvore) {
    if (arvore->raiz == NULL)
        return;
    arvore->raiz = removeMenor(arvore->raiz);
    if (arvore->raiz != NULL)
        arvore->raiz->cor = PRETO;
    arvore->tamanho--;
}

A figura mostra a remoção do menor na árvore obtida ao inserir as chaves de 1 a 7 (a da pergunta da seção anterior, toda preta).

Na descida, as duas inversões de cores (b e c) carregam o vermelho da raiz até o 1, que é removido sem mexer em nenhuma altura negra. Na volta, as duas rotações à esquerda (e e f) corrigem os vermelhos que ficaram à direita.

Remover uma chave qualquer

A remoção de uma chave qualquer combina o que já vimos. Se a chave está à esquerda, a descida é a mesma de removeMenor. Se está à direita, ou é a do próprio nó, a descida usa moveVermelhoParaDireita, depois de trazer para a direita um vermelho que esteja à esquerda.

1. 1

   Chave à esquerda#

   Se a chave é menor que a de r, prepare o caminho como em removeMenor (com moveVermelhoParaEsquerda, se preciso) e continue na SAE.

2. 2

   Traga o vermelho para a direita#

   Senão, se r->esq é vermelho, aplique uma rotação à direita em r: o vermelho passa para o lado por onde vamos descer.

3. 3

   Achou, sem filho direito#

   Se a chave é a de r e r não tem filho direito, r é uma folha vermelha (pela Proposição 1 e pelo invariante): libere-a.

4. 4

   Prepare o caminho à direita#

   Se r->dir e r->dir->esq são pretos, chame moveVermelhoParaDireita(r).

5. 5

   Achou, com filho direito#

   Se a chave é a de r, copie para r o par do sucessor (o menor nó da SAD) e remova o sucessor com removeMenor(r->dir). Senão, continue a remoção na SAD.

6. 6

   Volte corrigindo#

   Em todos os casos, devolva balanceia(r).

/* Supõe que a chave está na subárvore de r */
static No *removeNo(No *r, Chave chave) {
    if (chave < r->chave) {
        if (!noEhVermelho(r->esq) && !noEhVermelho(r->esq->esq))
            r = moveVermelhoParaEsquerda(r);
        r->esq = removeNo(r->esq, chave);
    } else {
        if (noEhVermelho(r->esq))       /* leva o vermelho para a direita */
            r = rotacaoDireita(r);
        if (chave == r->chave && r->dir == NULL) {
            free(r);                    /* folha vermelha */
            return NULL;
        }
        if (!noEhVermelho(r->dir) && !noEhVermelho(r->dir->esq))
            r = moveVermelhoParaDireita(r);
        if (chave == r->chave) {
            /* dois filhos: o sucessor (mínimo da SAD) toma o lugar */
            No *suc = r->dir;
            while (suc->esq != NULL)
                suc = suc->esq;
            r->chave = suc->chave;
            r->valor = suc->valor;
            r->dir = removeMenor(r->dir);
        } else {
            r->dir = removeNo(r->dir, chave);
        }
    }
    return balanceia(r);
}

void removeArvore(Arvore *arvore, Chave chave) {
    if (buscaNo(arvore->raiz, chave) == NULL)
        return;                         /* removeNo supõe que a chave existe */
    arvore->raiz = removeNo(arvore->raiz, chave);
    if (arvore->raiz != NULL)
        arvore->raiz->cor = PRETO;
    arvore->tamanho--;
}

O TAD completo

O programa abaixo usa o TAD completo, com a mesma interface Arvore.h da ABB e da AVL mais removeMenorArvore. Ele insere 1, 3, 6, 7 e 4 (a sequência da figura), imprimindo a árvore depois de cada inserção, remove o menor e depois remove o 7. Na impressão deitada, a raiz fica à esquerda e a SAD em cima.

Altura na prática

O programa abaixo insere chaves numa LLRB vazia, primeiro em ordem crescente e depois em ordem aleatória, e compara a altura obtida com a mínima possível, , e com o limite do teorema.

Com chaves crescentes, que degeneram a ABB comum, a LLRB fica com a altura mínima, como a AVL. Com chaves aleatórias, ela fica um pouco mais alta, mas muito abaixo do limite do teorema.

Custos

A busca é a da ABB, sem nenhuma mudança. A LLRB pode fazer mais rotações que a rubro-negra convencional (que faz no máximo duas por inserção e três por remoção), mas em troca o seu código cabe em poucas funções, e a mesma balanceia serve à inserção e à remoção.

Exercícios

Encontre e corrija o erro

Os programas abaixo usam uma LLRB simplificada (só com chaves) e imprimem a árvore deitada, com a cor de cada nó. Compare a saída com as propriedades da LLRB e com as figuras desta página.

Programa 1

if (noEhVermelho(r->dir) && !noEhVermelho(r->esq))
    r = rotacaoEsquerda(r);
if (noEhVermelho(r->esq) && noEhVermelho(r->esq->esq))
    r = rotacaoDireita(r);
if (noEhVermelho(r->esq) && noEhVermelho(r->dir))
    inverteCorNo(r);

Programa 2

B->cor = A->cor;        /* B herda a cor de A */
A->cor = VERMELHO;      /* A desce e fica vermelho */

Programa 3

novo->cor = VERMELHO;

Programa 4

if (noEhVermelho(r->dir->esq)) {
    r->dir = rotacaoDireita(r->dir);
    r = rotacaoEsquerda(r);
    inverteCorNo(r);
}

Implemente

É uma LLRB? Implemente ehLLRB, que devolve true se a árvore é uma LLRB válida: uma árvore binária de busca (chaves estritamente crescentes na ordem simétrica), com a raiz preta, nenhum filho direito vermelho, nenhum vermelho com filho vermelho e o mesmo número de nós pretos em todos os caminhos da raiz até as folhas NULL. A árvore vazia é uma LLRB. A função deve fazer uma única passada pela árvore, em .

Nos testes, cada árvore é dada em pré-ordem, com cada chave seguida da sua cor (V ou P) e . para NULL: A 10P 5V . . . é a raiz preta 10 com o filho esquerdo vermelho 5. Uma linha G n s gera uma LLRB com chaves aleatórias (semente ), que pode ser alterada em seguida para deixar de ser LLRB.

Remover o maior. Implemente removeMaior, que remove o nó com a maior chave de uma subárvore não vazia e devolve a nova raiz da subárvore. As demais funções do TAD, incluindo moveVermelhoParaDireita e balanceia, estão prontas, e removeMaiorArvore chama a sua função e pinta a raiz de preto. Os testes conferem todas as propriedades da LLRB depois das remoções, inclusive removendo o maior até esvaziar árvores com dezenas de milhares de chaves.

Referências

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