BSTs rubro-negras

Livro de Sedgewick e Wayne: sec.3.3, p.424.  Website do livro: resumo sec.3.3, slides.  Código fonte, documentação, e dados de teste de todos os programas do livro: veja algs4.cs.​princeton.edu/​code/.

Esta página trata de TSs (tabelas de símbolos) implementadas com BSTs (árvores binárias de busca) rubro-negras.  As BSTs rubro-negras são uma maneira de implementar árvores 2-3.

BSTs rubro-negras

• Uma BST rubro-negra (red-black BST), também conhecida como BST vermelho-preta, é uma BST que simula uma árvores 2-3.
• Cada nó duplo da árvore 2-3 é representado por dois nós simples ligados por um link rubro.
• Nossas BSTs são esquerdistas (left-leaning), pois os links rubros são sempre inclinados para a esquerda.  Há quem use a sigla ARNE (árvore rubro-negra esquerdista) para falar dessas BSTs.
• Representação de um nó duplo por meio de dois nós simples ligados por um link rubro:

  

• Definição: uma BST rubro-negra é uma BST cujos links são negros e rubros e têm as seguintes popriedades:
  • links rubros se inclinam para a esquerda;
  • nenhum nó incide em dois links rubros;
  • balanceamento negro perfeito: todo caminho da raiz até um link null tem o mesmo número de links negros.
• Se os links rubros forem desenhados horizontalmente e depois contraídos, teremos uma árvore 2-3:

  

• Todos as links null estão à mesma profundidade negra:

  

• A profundidade negra de um nó x é o número de links negros no caminho da raiz até x.  A altura negra da árvore é o máximo da profundidade negra de todos os nós.
• É inconveniente armazenar a cor de um link na estrutura de dados; é mais simples armazenar essa informação nos nós.  A cor de um nó é a cor do único link que entra nele.  A raiz é considerada negra.
• Representação dos nós de uma BST rubro-negra:

  

        private static final boolean RED = true;
        private static final boolean BLACK = false;
     
        private class Node {
           Key     key;
           Value   val;
           Node    left, right;
           int     N;             // número de nós nesta subárvore
           boolean color;         // cor do link que aponta para este nó
     
           Node(Key key, Value val, int N, boolean color) {
              this.key   = key;
              this.val   = val;
              this.N     = N;
              this.color = color;
           }
        }
  
        private boolean isRed(Node x) {
           if (x == null) return false;
           return x.color == RED;
        }
  

Exercícios 1

1. O que é balanceamento negro perfeito?
2. Dê um exemplo de uma BST cujas folhas têm todas a mesma profundidade, mas nem todo caminho da raiz até um link null tem o mesmo número de links negros.
3. Quantos nós tem a árvore da figura A red-black-tree… acima?
4. Seja x um nó de uma BST rubro-negra. Mostre que todos os caminho que levam de x até um link null têm o mesmo número de links pretos.
5. Suponha que x é um nó de uma BST rubro-negra. Suponha que x.right == null mas x.left != null. Prove que x.left.color == RED e x.left não tem filhos (ou seja, x.left.left == null e x.left.right == null).
6. Escreva métodos que calculem a altura (total) e a altura negra de uma BST rubro-negra.
7. Qual o número mínimo e o número máximo de links rubros numa BST rubro negra com N nós?  Qual o número máximo?

Buscas

• O código de busca (get) para BSTs rubro-negras é exatamente igual ao das BSTs comuns!

Rotações

• O código de inserção (put) é complicado;  ele depende de operações de rotação.
• Veja o video algs4.cs.​princeton.edu/​lectures/​33DemoRedBlackBST.mov de SW que ilustra a inserção da sequência de chaves S E A R C H E X A M P L E em uma BST rubro-negra.
• Durante uma operação de inserção, podemos ter, temporariamente, um link rubro inclinado para a direita ou dois links rubros incidindo no mesmo nó.  Para corrigir isso, usamos rotações.
• Rotação esquerda (ou anti-horária) em torno de um nó h:  o filho direito de h sobe e adota h como seu filho esquerdo. Continuamos tendo uma BST com os mesmos nós, mas raiz diferente:

  

           Node rotateLeft(Node h) {
              Node x = h.right;
              h.right = x.left;
              x.left = h;
              x.color = h.color;
              h.color = RED;
              x.N = h.N;
              h.N = 1 + size(h.left) + size(h.right);
              return x;
           }
  

  

• Rotação direita (ou horária) em torno de um nó h:  o filho esquerdo de h sobe e adota h como seu filho direito. Continuamos tendo uma BST com os mesmos nós, mas raiz diferente:

  

           Node rotateRight(Node h) {
              Node x = h.left;
              h.left = x.right;
              x.right = h;
              x.color = h.color;
              h.color = RED;
              x.N = h.N;
              h.N = 1 + size(h.left) + size(h.right);
              return x;
           }
  

  

• As operações de rotação são locais (só envolvem um nó e seus vizinhos). Depois de uma rotação, continuamos tendo uma BST com balanceamento negro perfeito. Mas a operação pode ter criado um link rubro inclinado para a lado errado ou dois links rubros seguidos. (Isso será corrigido mais adiante.)

Exercícios 2

1. (SW 3.3.38, p.452) Teorema fundamental das rotações. Mostre que qualquer BST pode ser transformada em qualquer outra sobre o mesmo conjunto de chaves por uma sequência apropriada de rotações.

Inserção de novo nó

• Um novo nó sempre se liga à árvore por um link rubro.
• Exemplo: Suponha que a árvore só tem a raiz. Se o novo nó é pendurado à esquerda da raiz, não é preciso fazer mais nada. Se o novo nó é pendurado à direita da raiz, é preciso fazer uma rotação para a esquerda (anti-horária) em torno da raiz (ou seja, root = rotateLeft(root)) para que a árvore fique esquerdista:

  

• Caso 1: Pendurar um novo nó em um nó simples (ou seja, um nó que não incide em link rubro):

  

• Caso 2: Pendurar um novo nó em um dado nó duplo (isto é, em um par de nós ligados por um link rubro).  Dependendo da chave, o novo nó pode ser pendurado em três lugares. Em cada caso, pendure por um link rubro e depois use rotações e inversão de cores (veja abaixo) para restabelecer as propriedades que caracterizam a árvore rubro-negra:

  

• Resumindo: toda inserção de um novo nó precisa de zero, uma, ou duas rotações seguidas de uma inversão de cores.

Inversão de cores (color flip)

• A inversão de cores implementa a divisão de um nó triplo temporário na árvore 2-3.
• Inversão de cores em um nó h: a cor rubra é retirada dos dois links que partem de h e passa para o link que entra em h. Dizemos que a cor rubra passa para cima:

  

           void flipColors(Node h) {
              h.color = RED;
              h.left.color = BLACK;
              h.right.color = BLACK;
           }
  

  

• A operação é local (só envolve um nó e seus vizinhos) e preserva o balanceamento negro perfeito (embora possa ter criado dois links rubros incidentes no mesmo nó).  A altura negra da árvore aumenta em 1 se e somente se h é a raiz da árvore.
• Exemplo: inserção em um nó duplo:

  

• Resumo do algoritmo de inserção: Se filho direito é rubro e filho esquerdo negro, rode para a esquerda.  Se filho esquerdo e neto esquerdo-esquerdo são rubros, rode para a direita.  Se dois filhos são rubros, faça inversão de cores.
• Mais um exemplo de inserção:

  

Exercícios 3

1. Nas figuras que descrevem a inversão de cores, o link que entra no nó h antes da inversão pode ser rubro? Por que?
2. (SW 3.3.10)  Desenhe a sequência de BSTs rubro-negras que resulta da inserção das chaves  E A S Y Q U T I O N,  nesta ordem, em uma árvore inicialmente vazia.  (Desenhe apenas a BST no final de cada put();  não desenhe as BSTs temporárias que aparecem durante a operação.)  Ao lado de cada BST rubro-negra, desenhe a correspondente árvores 2-3.
3. (SW 3.3.11)  Desenhe a sequência de BSTs rubro-negras que resulta da inserção das chaves  Y L P M X H C R A E S,  nesta ordem, em uma árvore inicialmente vazia.  Desenhe ao lado a correspondente sequência de árvores 2-3.
4. (SW 3.3.17)  Gere duas BSTs rubro-negras aleatórias com 16 nós cada. Desenhe-as (à mão ou usando um programa). Compare-as com as BSTs comuns (não balanceadas) construídas com as mesmas chaves.

Implementação

• Algoritmo 3.4: classe RedBlackBST (com destaque para o método de inserção):

  public class RedBlackBST<Key extends Comparable<Key>, Value> {
  
     private Node root;
     
     private class Node               // veja acima
  
     private boolean isRed(Node h)    // veja acima
  
     private Node rotateLeft(Node h)  // veja acima
  
     private Node rotateRight(Node h) // veja acima
  
     private void flipColors(Node h)  // veja acima
  
     private int size()               // veja na página sobre BSTs
  
     public void put(Key key, Value val) { 
        root = put(root, key, val);
        root.color = BLACK;
     }
  
     private Node put(Node h, Key key, Value val) {
        if (h == null) 
           return new Node(key, val, 1, RED);
  
        int cmp = key.compareTo(h.key);
        if      (cmp < 0) h.left  = put(h.left, key, val);
        else if (cmp > 0) h.right = put(h.right, key, val);
        else              h.val   = val;
  
        if (isRed(h.right) && !isRed(h.left))      h = rotateLeft(h);
        if (isRed(h.left)  &&  isRed(h.left.left)) h = rotateRight(h);
        if (isRed(h.left)  &&  isRed(h.right))     flipColors(h);
        h.N = size(h.left) + size(h.right) + 1;
        return h;
     }
  }
  

• O código de put() é recursivo. A operação desce pela árvore até achar o nó certo e depois volta, desempilhando as chamadas recursivas e fazendo as rotações e inversões de cores que forem necessárias.
• Cuidado com a implementação de size()!  Como esse método é chamado muitas vezes em cada execução de put(), a implementação deve ser eficiente. Use uma implementação ansiosa (que simplesmente lê o campo N dos Nodes).  Uma implementação preguiçosa produziria um defeito de desempenho (performance bug): o seu programa ficaria dramaticamente mais lento.   (É bem verdade, entretanto, que todas as invocações de size() têm por finalidade atualizar o campo N dos nós, que nunca é usado pelas operações de busca, inserção, rotação e inversão de cores!  O campo N é usado apenas pelas operações delete(), select() e rank(), que são abordadas nos exercícios.)
• (Veja o código completo em algs4/RedBlackBST.java.)
• Exemplo: Passo-a-passo da construção de uma BST rubro-negra (na coluna direita, as chaves entram em ordem alfabética).  Compare com a figura correspondente para árvore 2-3.

  

• Veja novamente o video algs4.cs.​princeton.edu/​lectures/​33DemoRedBlackBST.mov de SW.

Exercícios 4

1. (Sugestão de Leonardo Pereira Macedo e Ian Elmôr Lang): Considere o código de put(). Mostre que h.left é diferente de null sempre que a linha  if (isRed(h.left) && isRed(h.left.left))  é executada.
2. Escreva um método que coloque todas as chaves da BST rubro-negra em ordem crescente. Escreva o código como se o método fizesse parte de RedBlackBST.java.  (A sua maneira de resolver o problema tem algum nome bem conhecido?).
3. Escreva o código do método de um iterador keys() que itera sobre as chaves da árvore rubro-negra.

Remoção, mínimo, máximo, piso, teto, etc.

• Além das operações fundamentais put() e get() podemos pensar em operações adicionais:  remoção, mínimo, piso, etc.
• A operação de remoção, método delete(), é tão complicada quanto put() e será relegada aos exercícios.
• Os métodos min(), max(), floor() e ceiling() são exatamente os mesmos das BSTs ordinárias!

Exercícios 5

1. (SW 3.3.39-41) Delete. Escreva um método para remover um nó de uma BST rubro-negra. (É claro que o resultado da remoção deve ser uma BST rubro-negra.) Sua implementação deve consumir tempo limitado por lg N (veja a Proposição G).
2. (SW 3.3.37) As árvores lembram de sua história. Mostre que BSTs rubro-negras lembram de sua história. Por exemplo, se você inserir uma chave que é menor que todas as chaves da árvore e logo em seguida remover o mínimo da árvore, você pode obter uma árvore diferente da original.

Comportamento de pior caso de BSTs rubro-negras

• Proposition G: A altura de uma BST rubro-negra com N nós não passa de  2 lg N.  (Estamos falando da altura total, não da altura negra.)
• Esboço da prova: Pior caso é uma árvore 2-3 que só tem nós duplos no caminho que desce pela borda esquerda da árvore. Como nenhum nó incide em dois links rubros, esse caminho pela borda extrema esquerda é apenas duas vezes mais longo que os caminhos que só passam por nós simples.
• Em cada operação sobre uma BST rubro-negra com N nós, o número de comparações entre chaves é limitado por lg N multiplicado por uma constante pequena.  Assim, o consumo de tempo de cada operação é logarítmico, mesmo no pior caso.

Exercícios 6

1. (SW 3.3.24) Pior caso para BSTs rubro-negras. Mostre como construir uma BST rubro-negra com N nós para mostrar que, no pior caso, quase todos os caminhos da raiz até um link null têm comprimento 2 lg N.
2. (SW 3.3.22)  Encontre uma sequência de chaves para inserir em uma BST comum e uma BST rubro-negra de modo que a altura da BST comum seja menor que a altura (total) da BST rubro-negra, ou mostra que uma tal sequência não existe.
3. Qual a altura mínima de uma BST rubro-negra com N nós?
4. A altura de uma BST rubro-negra com N nós fica entre lg N e 2 lg N.  A altura de uma árvore 2-3 com N nós fica entre 0.63 lg N e lg N.  Por que a diferença?  Afinal, BSTs rubro-negras e árvore 2-3 são equivalentes.
5. Qual a menor e maior altura negra que uma BST rubro-negra com N nós pode ter?

Comportamento médio de BSTs rubro-negras

• Exemplo: SW trocou ST por RedBlackBST no programa-cliente FrequencyCounter e usou o programa para examinar as palavras com 8 ou mais letras do arquivo tale.txt.  O gráfico mostra o número de nós visitados (= número de comparações feitas) por cada chamada de put(). Os pontos vermelhos dão a média corrente:

  

• Compare com o gráfico análogo para BST, BinarySearchST e SequentialSearchST.
• Resultado de experimentos análogos para palavras de vários comprimentos nos arquivos tale.txt e leipzig1M.txt:

  	tale.txt				leipzig1M.txt
  	total palavras	palavras distintas	nós visitados em cada put()		total palavras	palavras distintas	nós visitados em cada put()
  			teoria	prática			teoria	prática
  todas palavras	135 635	10 679	13.6	13.5	21 191 455	534 580	19.4	19.1
  8 letras ou mais	14 350	5 737	12.6	12.1	4 239 597	299  593	18.7	18.4
  10 letras ou mais	4 582	2 260	11.4	11.5	1 610 829	165 555	17.5	17.3

• (Por algum motivo que não sei explicar, o 12.1 da tabela é diferente do 12 do gráfico acima.)  Compare com a tabela análoga para tabela para BST.
• Property H. O comprimento médio de um caminho da raiz até um nó qualquer de uma BST rubro-negra com N nós tende a 1.0 lg N quando N é grande.
• Exemplo: Uma BST rubro-negra construída com chaves aleatórias (links nulos foram omitidos):

  

• Exemplo: Uma BST rubro-negra construída com chaves inseridas em ordem crescente (links nulos foram omitidos):

  

Exercícios 7

1. Acrescente um método a RedBlackBST que calcule o custo médio de uma busca bem-sucedida, supondo que cada chave tem a mesma probabilidade de ser buscada. (O custo da busca é o número de comparações de chaves.)
2. Acrescente um método a RedBlackBST que calcule o custo médio de uma busca malsucedida sob a hipótese de hashing uniforme. (O custo da busca é o número de comparações de chaves.)
3. (SW 3.3.43) Gráficos de custo. Aparelhe a classe RedBlackBST de SW para produzir gráficos que mostrem o custo de cada put() ao longo da computação. (Veja Exercício SW 3.1.38.)
4. (SW 3.3.46, p.456) Altura. Aparelhe seus program do exercício SW 3.3.43 para fazer um gráfico da altura (total) de BSTs rubro-negras. Discuta os resultados.
5. (SW 3.3.42) Contagem de nós rubros. Escreva um programa que calcule a percentagem de nós rubros em uma BST rubro-negra. Para N igual a 10⁴, 10⁵, e 10⁶, insira N chaves aleatórias em uma árvore inicialmente vazia.  Repita cada experimento pelo menos 100 vezes. Invente uma boa maneira de apresentar seus resultados. Formule uma hipótese sobre o percentagem de nós rubros.

Resumo das 4 implementações de TSs vistas até aqui

• A tabela dá o número de comparações entre chaves numa TS com N chaves:

  	pior caso (tabela com N chaves)		caso médio (N chaves em ordem aleatória)
  	busca	inserção	busca bem-sucedida	inseção
  busca sequencial em lista ligada	N	N	N/2	N
  busca binária em vetor ordenado	lg N	N	lg N	N/2
  busca binária em BST	N	N	1.4 lg N	1.4 lg N
  BST rubro-negra	2 lg N	2 lg N	1.0 lg N	1.0 lg N