INF1010 3WB – L2: Árvores..

INF1010 3WB – Lista 2: Árvores.

Exercícios

  1. Verifique quais das árvores abaixo são binárias de busca. Caso não seja justifique porque.
    2. Abb a
    Abb b
    Abb c
  2. Seja S = {s1, s2, ..., s7} e si<si+1, i<7
    1. Desenhe uma ABB construída pelo algoritmo de inserção impondo a seguinte ordem das chaves: s3, s7, s1, s2, s6, s5, s4.
    2. Em que ordens das chaves a ABB tem altura máxima?
    3. Em que ordem tem a altura mínima?
  3. Dado como entrada um conjunto de chaves ordenado, escreva um algoritmo de inserção em uma ABB que resultante numa altura mínima.
  4. 4. Suponha que tenhamos números de 1 a 1000 armazenados numa ABB e que estejamos buscando o nó com o número 363. Quais das sequencias abaixo não poderia ser a sequencia de nós visitados?
    1. 2, 252, 401, 398, 330, 344, 397, 363.
    2. 924, 220, 911, 244, 898, 248, 362, 363.
    3. 925, 202, 911, 240, 912, 245, 363.
    4. 2, 399, 387, 219, 266, 382, 381, 278, 363.
    5. 935, 278, 347, 621, 299, 392, 358, 363.
  5. Dada a ABB mostrada na figura abaixo, mostre como ela ficaria se:
    1. O nó 16 fosse removido, ou
    2. O nó 22 fosse removido, ou
    3. O nó 15 fosse removido, ou
    4. O nó 9 fosse inserido.
Abb