Estruturas de Dados - Programa 4
Deseja-se obter o desempenho médio de árvore binária de busca, em termos do número médio de comparações necessárias, para a localização de uma dada chave numa árvore de busca de n chaves. Considere cada uma das n! permutações de n chaves e faça a inserção das chaves de cada sequência obtida numa árvore de busca, inicialmente vazia. Obtenha o desempenho médio em número de comparações dessa árvore: somando-se os números de comparações para localizar cada chave e dividindo-se o total por n. Finalmente, obtenha o desempenho médio de todos os n! casos. (A sua resposta bate com o que foi visto em classe?)