𝅘𝅥𝅮 Uma vez flamengo… ð… 

Chegamos, finalmente, na árvore red black! Para começar deixe-me mostrar as relações diretas entre um nó de uma árvore 2,3,4 e nós de uma árvore red black: Nós “simplex”, com apenas uma chave, são sempre pretos. Nós “duplex”, com duas chaves, contém uma chave “central”, raiz, e uma lateral e podem ser configurados de duas formas, como mostro abaixo. E os nós “triplex” (obviamente com três chaves) têm, necessariamente, uma chave raiz e duas laterais… Chaves “laterais” são sempre vermelhas.

Nós com 1, 2 ou 3 chaves e as equivalentes na red black
Nós com 1, 2 ou 3 chaves e as equivalentes na red black

O fato da chave raiz de um nó de uma árvore 2,3,4 ser preto, numa árvore red black, nos leva para a primeira regra:

  • O nó raiz é sempre preto!

Outra semelhança com árvores 2,3,4 é quanto à “promoção” de uma chave raiz de um nó triplex para um nó acima deste… Ao tentar inserir uma nova chave num triplex, temos que “subir” a chave raiz para o nó superior, abrindo espaço para a nova chave… Numa árvore red black é fácil observar que “subir” um nó preto (raiz do nó triplex) para um nó simplex ou duplex é questão de apenas mudar a cor de preto para vermelho e mudar os nós laterais para pretos. Eis um exemplo usando um duplex como nó superior:

up1

Diferente do artigo anterior (aqui), vou usar chaves vermelhas e pretas nos nós de árvores 2,3,4 da mesma maneira que numa árvore red black. Quer dizer, o nó preto é a raiz da sub árvore que compõe o nó e as vermelhas são as laterais…

O exemplo acima é simples, mas poderíamos ter algo um pouco diferente (repare a ordem nas chaves no nó duplex!):

up2

Se subirmos a chave 4, ela será uma chave lateral e teríamos duas chaves vermelhas no triplex superior… Isso não pode acontecer! Essa é a segunda regra para as árvores red black:

  • Não podemos ter nós vermelhos consecutivos.

Um nó vermelho não pode ser filho (ou pai) de outro nó vermelho…

Obviamente que se tivermos um nó pai simplex não precisamos nos preocupar com rotações, e basta mudar as cores do nó triplex, abaixo deste… Mas, e se o nó pai for triplex? Ora, dai teremos que fazer a “decomposição” do nó, como mostrei no artigo anterior… A decomposição de um nó triplex em três simplexes não poderia deixar de ser mais simples: Basta mudar as cores dos nós filhos do nó raiz do nó triplex para pretos!

Outra regra fundamental das árvores red black:

  • O número de nós pretos em quaisquer “caminhos” da árvore têm que ser igual!

Ou seja, do lado esquerdo de uma sub árvore qualquer temos que ter o mesmo número de nós pretos que têm no lado direito. contando com o nó raiz…  Surpreendentemente essa regra é seguida “automaticamente” pelo algoritmo de inserção nas árvores red black, como veremos…

Inserindo chaves em nós 2,3,4, ao estilo red black:

Para exemplificar a construção desse tipo de árvore (2,3,4), vou inserir itens em sequência (1,2,3,4,5,6…).

Numa árvore binária não balanceada isso nos daria uma configuração de lista de encadeamento simples (como mostrei aqui). É esperado que, numa árvore “balanceada”, isso não aconteça… A técnica para emular uma árvore 2,3,4 com uma árvore binária do tipo red black vai ser inserir sempre nós vermelhos e mudar a cor dos outros nós seguindo algumas regras básicas.

Numa árvore vazia vamos, primeiro, inserir 1, 2 e depois 3… a coisa fica assim:

red-black - adding 1, 2 and 3

Claramente que o nó 1 terá que ser transformado de vermelho para preto para respeitar a primeira regra das árvores red black.

Inserir uma chave nova num nó simplex também é simples… Ele vai do lado esquerdo (se seu valor for \leqslant que o nó preto) ou direito (se for menor)… Nada demais… Mas para transformar um nó duplex num triplex podemos ter que realizar uma rotação, seguindo a nossa última regra (dois nós vermelhos juntos não pode!)…

O que acontece se tentarmos inserir o nó 4 nesse nó triplex é que teremos que decompô-lo, mudando a cor das chaves laterais:

red-black - decomposing

Dai, só precisaremos adicionar o nó 4 onde está o nó 3:

red-black - adding 4

Adicionar o nó 5 também é simples. Basta colocá-lo no nó “duplex” contendo 3 e 4, rotacionando-o (já que a chave 4 é vermelha!). Para inserir a chave 6 precisaremos “subir” a chave 4, dividindo o nó triplex e adicionar ao nó simplex contendo a chave 5 a nova chave 6:

red-black - adding 6

Repare nas cores das chaves do nó raiz… A operação acima, equivalente, esboçada numa árvore red black, é mostrada abaixo. Node que, essencialmente, fizemos uma rotação:

red-black - adding 6 (rb)

Guarde essa operação, a retomaremos quando virmos o algoritmo implementado…

O algoritmo é um pouco mais simples…

As árvores red black reais são um pouco mais fáceis de implementar: Sempre que toparmos com dois nós vermelhos em sequência, temos que realizar uma rotação semelhante a uma dessas:

small-rotation

A primeira é uma rotação corriqueira: O nó pivot é o pai do novo nó (2). Este será transformado no novo nó raiz da sub árvore… O nó avô (pai do pai, o nó 1) será colocado mais à esquerda, ou melhor, na posição onde o menor dos itens entraria na sub árvore. E já que o nó pivot tornou-se o nó raiz, ele é pintado de preto. O nó que “desceu” (1) é pintado de vermelho.

A outra rotação é chamada de zig-zag. Isso porque os nós 2 e 3 são rotacionados para a direita (zig), o que nos fornece exatamente a sub árvore anterior, que é rotacionada para a esquerda (zag).

Mas, repare: A rotação só é necessária se tivermos dois nós vermelhos consecutivos ou quando queremos “subir” uma chave para um nó duplex! O código para inserção de uma chave k numa árvore T é este:

struct node_s { 
  int key; 
  int red; /* 0=preto, 1=vermelho. */ 
  struct node_s *left, *right; 
};

void RedBlackInsert(struct rbtree_s *T, int k)
{
  struct node_s *n,      /* nó atual. */
                *p, *pp; /* nós pai e avô. */

  /* Insere nó vermelho na árvore. */
  n = TreeInsert(T,k);
  n->red = 1;

  /* Obtém o nó pai e avô do novo nó */
  p = parent(n);
  pp = parent(p);

  /* Se o nó não é raiz da árvore T e
     o nó pai for vermelho, transformações
     são necessárias! */
  while (pp && p->red)
  {
    /* Se o nó pai está à direita do avô... */
    if (p == pp->right)
    {
      struct node_s *tmp;

      /* ... e se o nó à esquerda do nó avô for vermelho... */
      tmp = pp->left;
      if (tmp && tmp->red)
      {
        /* "sobe" o nó avô. */
        p->red = 0;
        tmp->red = 0;
        pp->red = 1;

        /* Acabamos aqui. "Sobe" um nível na árvore. */
        n = p;
      }
      else /* ... mas, se o nó à esquerda do avô for preto... */
      {
        /* Se o novo nó estiver à esquerda do nó pai,
           faz "zig"... */
        if (n == p->left)
          RotateRight(T,p);
        
        /* "sobe" o nó avô. */        
        p->red = 0;
        pp->red = 1;

        /* Faz 'zag'... */
        RotateLeft(T, pp);

        /* Acabamos aqui. "Sobe" um nível na árvore. */
        n = p;
      }
    }
    else
    {
      /* Mesma coisa que o bloco acima, mas
         'left' e 'right' são trocados por
         causa da simetria. Ou seja, o nó pai
         estará à esquerda do avô. */
      if (p == pp->left)
      {
        struct node_s *tmp;

        tmp = pp->right;
        if (tmp && tmp->red)
        {
          p->red = 0;
          tmp->red = 0;
          pp->red = 1;

          n = p;
        }
        else
        {
          if (n == p->right)
            RotateLeft(T,p);
        
          p->red = 0;
          pp->red = 1;

          RotateRight(T, pp);

          n = p;
        }
      }
    }

    /* Já que 'n' subiu, pega os nós
       pai e avô, de novo. */
    p = parent(n);
    pp = parent(p);
  }

  /* Certifica-se que o nó raiz seja sempre preto. */
  T->root->red = 0;
}

A rotina insere, com sucesso, até três nós sem fazer quaisquer tratamentos especiais. Somente quando vamos inserir o quarto nó é que os ponteiros p e pp tornam-se válidos (pp será diferente de NULL).

As rotinas auxiliares TreeInsert e parent são triviais. A rotina TreeInsert simplesmente insere um item (vermelho) numa árvore binária comum, não balanceada. Já parent devolve o ponteiro para o nó pai de um nó dado ou NULL se o nó não tem um parente (se for o nó raiz). Ela pode ser implementada de duas maneiras: Podemos percorrer a árvore desde o nó raiz até achar um nó comum dos links (left ou right) apontando para o nosso nó n; ou podemos manter um ponteiro parent em cada um dos nós apontando para o nó imediatamente acima… Essa segunda implementação dificulta um pouco as coisas quando as rotações forem necessárias, mas pode ser uma boa idéia.

E, falando em rotações, elas são simples e fazem o que a figura abaixo sugere, onde o pivot é o nosso nó pai (p) e o root é o nosso nó avô (pp):

Tree_rotation_animation_250x250

As rotinas de rotação devem levar em conta se estamos tentando rotações à partir do nó raiz e atualizar o ponteiro root da estrutura rbtree_s, se for o caso…

Voltando ao exemplo da inserção do nó 6, seguindo o algoritmo acima temos:

algorithm

No primeiro passo, inserimos o nó n e achamos o nó pai (p) e avô (pp). O nó p é vermelho e o nó à esquerda de pp é vermelho também, então vamos “subir” a chave 4 mudando a cor para vermelha e mudando suas filhas para pretas… Daí. subimos n em um nível e repetimos o processo. Agora temos uma nó p vermelho e o nó à esquerda de pp preto. Precisamos rotacionar esses dois nós à esquerda e, voilà! Acabamos com uma árvore exatamente como queríamos.

A criação da árvore está ai, bem como a explicação de como ela funciona… Resta-nos ver como apagar um nó da árvore, mantendo a estrutura de controle coerente (as cores dos nós)… Deixo isso para outra oportunidade…

Anúncios