Á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.

[Computer Science trees grow from the root down]

Resumo:

Pré-requisitos:

O que é uma árvore binária?

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ó.

    [BST]

  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?

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

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

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)

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

 


Perguntas e respostas


Valid CSS! Valid HTML 4.01 Strict