MAC323/BCC TERCEIRO DESAFIO

ESTATÍSTICAS DE ÁRVORES BINÁRIAS

Y. KOHAYAKAWA

Neste desafio, você verificará empiricamente as afirmações que vimos em aula sobre a profundidade média dos nós em uma (i) árvore de busca binária gerada a partir de uma permutação aleatória de N chaves distintas e em uma (ii) árvore binária escolhida uniformemente ao acaso, dentre todas as árvores com N nós internos.

Árvores de busca binária aleatórias. Escreva um programa que, dado N ≥ 1, gera uma permutação aleatória dos inteiros 1, …, N, digamos ρ: [N] → [N], e que contrói uma ABB com estas chaves, inserindo-as na ordem

ρ(1), ρ(2), …, ρ(N).

• Execute seu programa para valores grandes de N, várias vezes, e compile estatísticas sobre as árvores geradas (possivelmente também fazendo alguns histogramas para ilustrar seus dados de forma intuitiva). Você pode calcular a altura média e os comprimentos interno e externo médios.

• Uma estatística um pouco diferente refere-se à eficiência de se contruir tais árvores: você pode verificar qual é o número médio de comparações que se faz para construir estas árvores com N nós.

Lembre que o resultado fundamental visto em aula (mas não demonstrado) é que tais árvores tem comprimento interno basicamente igual a 2N log N.

Árvores de busca binária uniformes. Escreva um programa que, dado N ≥ 1, gera uma árvore binária com N nós internos, com todas estas árvores equiprováveis. Você vai ter de pensar um pouco como fazer isto. Você pode usar o fato mencionado em sala que diz que o número de tais árvores é

t(N) = \frac{1}{N + 1}\binom{2N}{N}.

• Execute seu programa para valores grandes de N, várias vezes, e compile estatísticas sobre as árvores geradas (possivelmente também fazendo alguns histogramas). Você pode calcular a altura média e os comprimentos interno e externo médios.

Lembre que o resultado fundamental visto em aula (mas não demonstrado) é que tais árvores tem comprimento interno basicamente igual a N\sqrt{πN}.

Data: Versão de 6 de abril de 2001.

2 Y. KOHAYAKAWA

Observações. Você pode achar interessante consultar a página

               http://cgm.cs.mcgill.ca/~luc/trees.html

escrita por Luc Devroye, do Departamento de Ciência da Computação da Universidade de McGill.