Árvores binárias de busca (BSTs)

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

Árvores binárias de busca (BSTs) servem para implementar TSs ordenadas, ou seja, TSs cujas chaves são comparáveis.  BSTs combinam as vantagens das implementações elementares SequentialSearchST e BinarySearchST:  elas podem ser vistas como uma maneira de implementar busca binária em uma lista ligada.

O que é uma árvore binária?

• Antes das BSTs, precisamos discutir algo mais geral:  as BTs  [detesto siglas!].
• BT = binary tree = árvore binária.
• Cada nó tem no máximo dois filhos: um esquerdo e um direito.

  

• Exemplo: uma BT com 256 nós.
• Uma árvore binária na natureza:

  

• Definição de um nó de uma árvore binária:

     private class Node {
        private Node left, right;
     }
  

• A raiz (root) é o único nó que não é filho de outro.  A árvore é vazia se root == null.

     private Node root; 
  

• BTs são estruturas recursivas: cada nó da BT é raiz de uma sub-BT.
• A profundidade (depth) de um nó de uma BT é o número de links no caminho que vai da raiz até o nó.
• A altura (height) de uma BT é o máximo das profundidades dos nós, ou seja, a profundidade do nó mais profundo.
• Uma BT com N nós, tem altura  no máximo  N−1  e  no mínimo  ⌊lg N⌋ .  Se a altura estiver perto de lg N, a BT é balanceada.
• Exemplos:

  

• O comprimento interno (internal path length) de uma BT é a soma das profundidades dos seus nós, ou seja, a soma dos comprimentos de todos os caminhos que levam da raiz até um nó.    (Esse conceito é usado para estimar o desempenho esperado de TSs implementadas com BSTs).

Exercícios 1

1. Para cada das BTs que aparecem nas figuras desta página, escolha um nó no meio da árvore e diga qual a profundidade do nó.

   

2. Qual a altura da árvore da figura?  Qual a profundidade do nó M? Qual a altura da sub-árvore cuja raiz é M?
3. Dê a altura e o comprimento interno de cada uma das BTs que aparecem nas figuras desta página.
4. Prove que a profundidade de um nó em uma BT com N nós é no máximo N−1 e no mínimo 0.
5. Prove que a altura de toda BT com N nós é no máximo N−1 e no mínimo ⌊lg N⌋.
6. Tamanho.  Escreva um método recursivo que devolva o número de nós de uma árvore binária.
7. (SW 3.2.6, p.416)  Altura.  Escreva um método (recursivo) que calcule a altura de uma árvore binária. Sua implementação deve ser do tipo preguiçoso. (Não é preciso calcular as profundidades antes.)
8. Acrescente a Node um campo depth para armazenar a profundidade do nó. Escreva um método setDepthField() que defina o valor do campo depth de todos os nós.
9. (SW 3.2.7)  Escreva um método internalPathLength que calcule o comprimento interno de uma BT (árvore binária).
10. Qual o valor máximo e o mínimo do comprimento interno de uma BT com N nós?
11. Percursos (traversals).  Escreva um método que imprima as chaves de uma BT em in-ordem (ou seja, na ordem esquerda-raiz-direita); use recursão.  Repita para pós-ordem (ordem esquerda-direita-raiz). Repita para pré-ordem (ordem raiz-esquerda-direita). Use uma fila para armazenar as chaves antes de imprimir.

O que é uma árvore binária de busca?

• Uma árvore binária de busca (binary search tree) é um tipo especial de BT:  para cada nó x, todos os nós na subárvore esquerda de x têm chave menor que  x.key  e todos os nós na subárvore direita de x têm chave maior que  x.key.
• BST = binary search tree = árvore binária de busca.
• As chaves de uma BST precisam ser comparáveis.
• Nosso exemplo padrão:

  

• Exemplo: Duas BSTs que representam o mesmo conjunto de chaves:

  

• Busca (get) numa BST: o processo é muito parecido com a busca binária em um vetor ordenado:

  

• Inserção (put) em uma BST: o processo é muito mais barato que a inserção em um vetor ordenado, pois não envolve movimentação de dados. [Ignore os dizeres and increment counts na figura].

  

• Veja a animação da busca e inserção em uma BST.

Exercícios 2

1. (SW 3.2.1, p.416) Importante!  Insira as chaves  E A S Y Q U E S T I O N,  nesta ordem, numa BST inicialmente vazia. Associe valor i com a i-ésima chave. Desenhe a BST resultante. Em quantos nós você tocou (ou seja, quantas comparações você fez) para construir a BST?
2. (SW 3.2.4) Suponha que as chaves de uma BST são números inteiros entre 1 e 10.  Quais das sequências abaixo não podem ser as sequências de chaves examinadas em uma busca pla chave 5?
   • 10, 9, 8, 7, 6, 5
   • 4, 10, 8, 6, 5
   • 1, 10, 2, 9, 3, 8, 4, 7, 6, 5
   • 2, 7, 3, 8, 4, 5
   • 1, 2, 10, 4, 8, 5
3. Desenhe as seis BSTs que resultam da inserção de cada uma das seis permutações das chaves  A B C  numa árvore inicialmente vazia.
4. Insira as palavras de tinyTale.txt, em ordem, numa BST inicialmente vazia. (Associe o valor i com a i-ésima chave.) Desenhe a BST resultante. Compare seu desenho com o resultado do cliente de teste de BST.java, que imprime os nós por níveis.
5. Escreva um método checkBST() que receba uma BT e verifique se ela é ou não uma BST. Seu método deve ser recursivo.

Implementação de TS com BST

• [Algoritmo 3.3]  A seguinte classe BST implementa uma tabela de símbolos em uma BST. Para definir um nó da árvore, acrescentamos campos key e val aos nós de uma BT.

  public class BST <Key extends Comparable<Key>, Value> {
  
     private Node root;
   
     private class Node {
        private Key key;
        private Value val;
        private Node left, right;
        public Node(Key key, Value val) {
           this.key = key;
           this.val = val;
        }
     }
  
     public Value get(Key key) {
        return get(root, key);
     }
  
     private Value get(Node x, Key key) {
        // Considera apenas a subárvore que tem raiz x
        if (x == null) return null;
        int cmp = key.compareTo(x.key);
        if      (cmp < 0) return get(x.left, key);
        else if (cmp > 0) return get(x.right, key);
        else return x.val;
     }
  
     public void put(Key key, Value val) {
        root = put(root, key, val);
     }
  
     private Node put(Node x, Key key, Value val) {
        // Considera apenas a subárvore com raiz x
        // Devolve a raiz da nova subárvore
        if (x == null) return new Node(key, val);
        int cmp = key.compareTo(x.key);
        if      (cmp < 0) x.left = put(x.left, key, val);
        else if (cmp > 0) x.right = put(x.right, key, val);
        else x.val = val;
        return x;
     }
  }
  

• Exemplo: Rastreamento da inserção das chaves  S E A R C H E X A M P L E ,  nessa ordem:

  

• Qualquer busca (get) que termina em um nó x de profundidade p visita 1 + p nós.  O mesmo vale para inserção (put).

Exercícios 3

1. Método size.  Considere um método auxiliar size() que devolve o número de nós da árvore. Você já implementou o método num dos exercícios acima. Aquela implementação é conhecida como preguiçosa (lazy): ela examina a árvore toda e assim consome tempo proporcional ao número de nós da árvore.  Escreva uma implementação mais eficiente usando a seguinte ideia: acrescente a cada nó x um campo N onde ficará registrado o número de nós da subárvore cuja raiz é x. Essa ideia leva a uma implementação conhecida como ansiosa (eager). A execução da versão ansiosa de size() consome tempo constante (ou seja, independente do número de nós da árvore), mas há um preço a pagar: toda operação de inserção precisa atualizar o campo N de todos os nós. Além de escrever o código ansioso de size(), faça as alterações necessárias no código de put().
2. (SW 3.2.6, p.416)  Acrescente um campo inteiro h a cada nó e escreva uma versão ansiosa do método que calcula a altura da árvore binária.
3. (SW 3.2.7)  Acrescente um campo inteiro ipl a cada nó e escreva uma versão ansiosa de um método internalPathLength() que calcule o comprimento interno de uma BT.

Desempenho no pior caso

• Toda operação de busca ou inserção visita  1 + p nós,  sendo p a profundidade do último nó visitado.
• Logo, o número de nós visitados não passa de  1 + h,  sendo h a altura da BST.
• (Proposição E)  No pior caso, todas as operações sobre uma BST consomem tempo proporcional à altura da árvore.
• Infelizmente, uma BST pode não estar balanceada:  sua altura pode estar bem mais perto de N que de lg N. 

  

• Embora BSTs desbalanceadas sejam fáceis de construir (basta inserir as chaves em ordem apoximadamente crescente), elas são raras entre as BSTs aleatórias.

Exercícios 4

1. (SW 3.2.25, p.419) Perfect balance. Escreva um programa que insira um conjunto de chaves (as chaves podem ser do tipo int) em uma BST inicialmente vazia de modo que a BST resultante seja equivalente à busca binária em vetor ordenado no seguinte sentido: a sequência de comparações produzida por um get() na BST seja igual à sequência de comparações que seria feita pela busca binária num vetor ordenado.
2. (SW 3.2.28) Sofware caching. Modifique a classe BST de modo a manter em uma variável de instância o nó devolvido por get() ou put() na chamada anterior. Isso pode economizar tempo se a próxima chamada de get() ou put() tiver a mesma chave como argumento.  (Esse tipo de truque é uma heurística:  não garante nada, mas pode ajudar na prática.)  (Veja o exercício SW 3.1.25.)

Desempenho esperado (= médio)

• BST típica construída com 256 chaves inseridas em ordem aleatória (quantos nós tem essa árvore?):

  

• Veja animação no website do livro.
• Analisar desempenho esperado de uma implementação é sempre difícil.
• Quantos nós são visitados, em média, durante uma busca em uma BST aleatória com N nós?
• Uma BST aleatória é uma BST que se obtém inserindo N chaves distintas em ordem aleatória numa árvore inicialmente vazia  (veja um dos exercícios acima).
• Qual a altura esperada de uma BST aleatória?  Resposta (calculada por L. Devroye):  aproximadamente  3 lg N  quando N é grande.
• Portanto, o número esperado de nós visitados durante uma busca em uma BST aleatória não passa de  3 lg N.
• O número esperado de nós visitados durante uma busca ou inserção em uma BST aleatória é menor que 3 lg N:  ele tende a  1.4 lg N  quando N aumenta  (veja Proposições C e D) no livro.

• Ideia da prova para buscas bem-sucedidas: Seja C o comprimento interno. O tempo esperado para buscar todas as chaves é (N + C)/N, ou seja, 1 + C/N.  Demonstra-se que C ≅ 2N ln N = 1.3862 N lg N.

• A experiência mostra que o número 1.4 lg N também é aproximadamente correto em muitas situações práticas.
• Exemplo: SW trocou ST por BST no programa-cliente FrequencyCounter e usou o programa para examinar as palavras com 8 ou mais letras do arquivo tale.txt.  O gráfico (copiado da p.405 do livro) mostra o número de nós visitados (= número de comparações feitas) por cada put(). Os pontos vermelhos dão a média corrente:

  

• 13.9 não fica longe de 1.4 lg N, que vale 17.6 .
• 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	18.6	17.5	21 191 455	534 580	23.4	22.1
  8 letras ou mais	14 350	5 737	17.6	13.9	4 239 597	299  593	22.7	21.4
  10 letras ou mais	4 582	2 260	15.4	13.1	1 610 829	165 555	20.5	19.3

Exercícios 5

1. Para N = 3, quantas BSTs há no nosso modelo de BST aleatória?  Quantas são diferentes entre si? Quantas cópias há de cada dessas árvores no modelo? Calcule a altura esperada e o comprimento interno esperado das BSTs aleatórias de 3 nós. (Veja um dos exercícios acima.)
2. Das 24 BSTs com 4 nós que estão no nosso modelo de BST aleatória, quantas cópias há de cada uma? Calcule a altura esperada e o comprimento interno esperado das BSTs aleatórias de 4 nós.
3. (SW 3.2.5)  Suponha que inserimos N chaves diferentes em uma BST inicialmente vazia e depois fazemos um grande número de buscas. Suponha que sabemos quão frequentemente cada chave será buscada.  Deveríamos ter inserido as chaves na árvore em ordem crescente? em ordem decrescente? em ordem descrescente da frequência esperada de busca? em alguma outra ordem?
4. Acrescente um método a BST 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.)
5. Acrescente um método a BST 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.)
6. (SW 3.2.38) Desenhos de árvores. Acrescente à classe BST um método draw() que faça um desenho da árvore. Dica: Use variáveis de instância para armazenar as coordenadas dos nós e use um método recursivo para atribuir valores a essas variáveis.

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

• Custos de operações em implementações básicas de tabelas de símbolos:

  	pior caso (tabela com N chaves)		caso médio (N chaves inseridas 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