Questao 6(ii) da primeira prova

[Armando Ramos Gouveia <armando@ime.usp.br>]

Ola', pesoALL.

Na aula de hoje ficou aquela duvida sobre a pergunta da Andrea: 
na questao 6(ii), 
   era para considerar que a altura h era a do pior caso 
ou era para considerar o pior caso com altura h?

De qualquer modo, mesmo na hipotese de que a arvore montada seja
a do pior caso (arvore em que nao existem os filhos esquerdos)
devemos notar que, nao necessariamente n == h, 
pois pode haver palavras repetidas.

Embora uma palavras repetida nao seja inserida na arvore, 
freq_ABB executa comparacoes ate' encontra'-la. No caso de ser
encontrada so' nas folhas, pode haver h+1 comparacoes.

Portanto, tambem nesse caso, o unico limitante superior que
podemos garantir para o total e'
                                   n(h+1) comparacoes.
Alguem da' mais?  :-)

Abracos a todos!

Armando
22/out/98.