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.

Resumo:

Pré-requisitos:

BSTs rubro-negras

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

Rotações

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ó

Inversão de cores (color flip)

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

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.

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

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

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 104, 105, e 106, 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


Red-Black tree example no YouTube


Valid CSS! Valid HTML 4.01 Strict