MAC338 Análise de Algoritmos

BCC - 1o. Semestre de 2000

Altura de ABBs Aleatórias

Inicialmente, veja o exercício 31(ii) de nossa lista de exercícios do semestre. Um teorema de Luc Devroye determina a constante em questão naquele exercício. Esta constante de Devroye é aproximadamente 4.31107... Veja aqui [gamma.tex.gz | gamma.dvi.gz | gamma.ps.gz | gamma.pdf.gz]

Entretanto, parece que determinar esta constante empiricamente, gerando ABBs aleatórias, não dá muito certo. Pelo menos, ABBs pequenas não parecem sugerir o valor correto para esta constante.

Este desafio. Neste desafio/exercício estendido, você deve elaborar testes empíricos que confirmem o resultado teórico de Devroye. O ideal seria que você também explicasse a razão de teste empíricos menos sofisticados não serem suficientes.

Referências bibliográficas

1. MR87i:68009 Devroye, L. A note on the height of binary search trees. J. Assoc. Comput. Mach. 33 (1986), no. 3, 489--498. 68P10
   
2. MR88j:68022 Devroye, L. Branching processes in the analysis of the heights of trees. Acta Inform. 24 (1987), no. 3, 277--298. 68P05 (68P10)
   

Last modified: Fri Jul 2 08:49:22 BRT 2010