1. Introdução

O programa tree-stat calcula estatísticas sobre vários tipos de árvores binárias. Ele pode ser utilizado para:

• Calcular a altura e o IPL médios de árvores binárias geradas aleatóriamente;

• Criar figuras de árvores binárias geradas aleatóriamente;

• Calcular a altura e o IPL médios de árvores de busca binárias geradas a partir da inserção de uma permutação qualquer de um conjunto de elementos;

• Criar figuras de árvores binárias de busca geradas a partir do método acima.

Os módulos utilizados pelo programa são bin-tree, que possui funções capazes de gerar árvores binárias ao acaso, e bs-tree, que possui funções capazes de manipular árvores binárias de busca.

2. Linha de comando. A linha de comando geral do programa é como segue:

tree-stat {bp} -[dch] -[srN]número -[ltn]string

As opções b ou p são obrigatórias, devem comparecer logo após o nome do programa e apenas uma deve ser usada. A opção b faz com que o programa compute estatísticas sobre árvores binárias geradas ao acaso e a opção p faz com que as estatísticas sendo computadas sejam sobre árvores binárias de busca. As demais opções estão detalhadamente explicadas abaixo.

d. Se presente, faz com que o programa gere apenas uma árvore e envie para a saída padrão o código que a representa segundo a convenção do pacote PStricks, disponível para L^{A}TEXou TEX.

h. Envia para saída padrão dados sobre a distribuição da altura e do IPL das árvores geradas. Os dados são dados na forma de uma tabela de frequências.

s. Deve ser seguida de um número, especificando a semente a ser utilizada para iniciar o gerador de números aleatórios.

r. Especifica o número de experimentos que devem ser feitos para a determinação das estatísticas. Não tem efeito se utilizado com a opção -d. O valor padrão é 1000.

N. Número de nós internos das árvores a serem geradas. Se não especificado, são geradas árvores com 100 nós internos.

l. Tem efeito apenas se utilizado em conjunto com a opção -d. Especifica então a separação entre dois níveis da árvore a ser gerada. Uma string como 2pt ou 2cm deve vir em seguida. O padrão é 5mm.

t. Como a anterior, só que especifica a distâcia entre duas subárvores. O padrão é 5mm.

n. Tipo de nó interno que será utilizado. Apenas tem efeito em conjunto com a opção -d. O valor padrão é

     \Tc*{2pt} ^{1}.

c. Especifica que a sequência dada para o tipo de nó interno contém uma sequência de controle, que será utilizada para imprimir o conteúdo do nó de uma árvore binária de busca.

3. A estrutura geral do programa é a seguinte:

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include "bin-tree.h"
#include "bs-tree.h"

#define FALSE 0

#define TRUE¬ FALSE

⟨ Função principal 4 ⟩ Estatísticas sobre Árvores 2

1Veja a documentação do pacote PStricks.

4. ⟨ Função principal 4 ⟩ ≡ int main(int argc, char ∗argv [ ]) {

⟨ Variáveis locais 6 ⟩ ⟨ Procura pelos argumentos de linha de comando 5 ⟩ ⟨ Executa opções dadas na linha de comando 8 ⟩ return 0;

}

Este código é usado na seção 3.

5. ⟨ Procura pelos argumentos de linha de comando 5 ⟩ ≡

{ int i; if (argc < 2 ∨ (argc ≥ 2 ∧ (argv [1][0] ≠ 'b' ∧ argv [1][0] ≠ 'p'))) {

fprintf (stderr , "Uso:␣tree-stat␣{bp}␣-[dch]␣-[srN]número␣-[ltn]string\n");

return 1; } for (i = 2; i < argc; i{+ \atop +}) \{

if (argv [i][0] ≠ '-') {

  fprintf (stderr , "Uso:␣tree-stat␣{b]}␣-[dch]␣-[srN]número␣-[ltn]string\n");

return 1; } if (argv [i][1] ≡ 'd') {

draw tree = TRUE;

continue; } else if (argv [i][1] ≡ 'h') {

gen tables = TRUE;

continue; } else if (argv [i][1] ≡ 'c') {

control seq = TRUE;

continue; } else if (¬argv [i][2]) continue; switch (argv [i][1]) { case 's': sscanf (argv [i] + 2, "%d", &seed );

break; case 'r': sscanf (argv [i] + 2, "%d", &rep);

break; case 'N': sscanf (argv [i] + 2, "%d", &N);

break; case 'l': sscanf (argv [i] + 2, "%s", level sep);

break; case 't': sscanf (argv [i] + 2, "%s", tree sep);

break; case 'n': sscanf (argv [i] + 2, "%s", node type);

break;

default: fprintf (stderr , "Uso:␣tree-stat␣{bp}␣-[dch]␣-[srN]número␣-[ltn]string\n");

return 1; }

} }

Este código é usado na seção 4.

Estatísticas sobre Árvores 3

6. Vamos agora definir as variáveis locais que utilizamos na seção acima para guardar os argumentos de linha de comando. Os valores de inicialização são os valores padrão. ⟨ Variáveis locais 6 ⟩ ≡

int draw tree = FALSE; /∗ Indica presença da opção -d ∗/ int control seq = FALSE; /∗ Indica a presença da opção -c ∗/ int gen tables = FALSE; /∗ Indica presença da opção -h ∗/ int seed = time(Λ); /∗ Semente do gerador ∗/ int rep = 1000; /∗ Número de repetições dos experimentos ∗/ int N = 100; /∗ Números de nós internos das árvores ∗/ char level sep[ ] = "5mm\0␣␣␣␣␣␣␣␣␣"; /∗ Separação entre os níveis ∗/ char tree sep[ ] = "5mm\0␣␣␣␣␣␣␣␣␣"; /∗ Separação entre subárvores ∗/ char node type[ ] = "\\Tc*{2pt}\0␣␣␣␣␣␣␣␣␣"; /∗ Estilo de nó interno ∗/

Veja também a seção 7. Este código é usado na seção 4.

7. Além dessas variáveis, vamos utilizar duas outras que servirão para guardar a altura e o IPL de uma árvore gerada. ⟨ Variáveis locais 6 ⟩ +≡

int height ; int ipl ;

8. ⟨ Executa opções dadas na linha de comando 8 ⟩ ≡ srand (seed ); if (argv [1][0] ≡ 'b') {

if (¬init bin tree gen(N)) {

    fprintf (stderr , "Erro␣ao␣inicializar␣módulo␣bin-tree\n");

return 1; } if (draw tree) {

draw random tree(N, &height , &ipl , level sep, tree sep, node type, stdout ); fprintf (stderr , "Altura:␣%d\n", height ); fprintf (stderr , "IPL:␣%d\n", ipl );

}

else ⟨ Calcula estatísticas sobre árvores binárias 9 ⟩

deinit bin tree gen( ); } else {

bs treebst ;

if ((bst = init bst (N)) ≡ Λ) {

    fprintf (stderr , "Erro␣ao␣inicializar␣módulo␣bs-tree\n");

return 1; } if (draw tree) {

gen random bst (bst );

draw bst (bst , control seq , node type, level sep, tree sep, stdout ); fprintf (stderr , "Altura:␣%d\n", get bst height (bst )); fprintf (stderr , "IPL:␣%d\n", get bst ipl (bst ));

}

else ⟨ Calcula estatísticas sobre árvores de busca binária 14 ⟩ destroy bst (bst );

}

Este código é usado na seção 4.

Estatísticas sobre Árvores 4

9. Estatísticas sobre árvores binárias

As estatísticas calculadas são basicamente a altura e o IPL médios. O EPL médio também é calculado, a partir do IPL médio, já que EPL = IPL + 2N para toda árvore binária com N nós internos. ⟨ Calcula estatísticas sobre árvores binárias 9 ⟩ ≡

{

if (gen tables ) { ⟨ Inicializa vetores que guardam as tabelas de frequência 11 ⟩ ⟨ Gera rep árvores binárias e cria as tabelas 12 ⟩ ⟨ Imprime as tabelas na saída padrão e as elimina 13 ⟩

}

else ⟨ Gera rep árvores binárias e calcula seus parâmetros médios 10 ⟩ }

Este código é usado na seção 8.

10. Primeiramente, vamos tratar do caso em que não se deseja gerar as tabelas com a distribuição de frequências para os parâmetros. ⟨ Gera rep árvores binárias e calcula seus parâmetros médios 10 ⟩ ≡

{ int i; double ave height = 0; /∗ Altura média ∗/ double ave ipl = 0; /∗ IPL médio ∗/ for (i = 0; i < rep; i{+ \atop +}) \{

random tree params (N, &height , &ipl );

ave height += height ;

ave ipl += ipl ; } fprintf (stdout , "Altura␣média:␣%f\n", ave height /rep); fprintf (stdout , "IPL␣médio:␣%f\n", ave ipl /rep); fprintf (stdout , "EPL␣médio:␣%f\n", ave ipl /rep + 2 ∗ N);

}

Este código é usado na seção 9.

11. Se a opção -h foi utilizada, devemos gerar tabelas contendo as alturas das árvores geradas e as frequências com que ocorrem árvores com estas alturas, fazendo algo semelhante para o IPL.

Isso pode consumir uma quantidade considerável de memória. Para uma árvore binária qualquer, sabemos que

N lg \frac{N}{4} ≤ IPL ≤ \frac{N(N − 1)}{2}.

Para uma árvore de 1000 nós internos, teríamos então 8000 ≤ IP L ≤ 499500. Considerando que o espaço que uma variável do tipo int ocupa é de 4 bytes, a tabela do IPL ocupara 1.90mb em memória, incluindo as 8000 posições iniciais que nunca serão utilizadas. Entretanto, estas posições ocupam apenas 31.25kb. Portanto, não vamos nos preocupar em economizar esta pequena quantidade de memória, o que vai aumentar a velocidade dos cálculos. ⟨ Inicializa vetores que guardam as tabelas de frequência 11 ⟩ ≡

int ∗height table = Λ; /∗ Tabela das alturas ∗/

int ∗ipl table = Λ; /∗ Tabela dos IPLs ∗/

if ((height table = calloc(N + 1, sizeof (int))) ≡ Λ) {

    fprintf (stderr , "Erro␣de␣alocaç~ao␣de␣memória\n");

return 1; } if ((ipl table = calloc(1 + (N ∗ (N − 1))/2, sizeof (int))) ≡ Λ) { Estatísticas sobre Árvores 5

fprintf (stderr , "Erro␣de␣alocaç~ao␣de␣memória\n");

return 1; }

Este código é usado nas seções 9 e 14.

12. ⟨ Gera rep árvores binárias e cria as tabelas 12 ⟩ ≡

{ int i; double ave height = 0; /∗ Altura média ∗/ double ave ipl = 0; /∗ IPL médio ∗/ for (i = 0; i < rep; i{+ \atop +}) \{

random tree params (N, &height , &ipl );

ave height += height ;

ave ipl += ipl ;

height table[height ]{+ \atop +};

ipl table[ipl ]{+ \atop +}; } fprintf (stdout , "Altura␣média:␣%f\n", ave height /rep); fprintf (stdout , "IPL␣médio:␣%f\n", ave ipl /rep); fprintf (stdout , "EPL␣médio:␣%f\n", ave ipl /rep + 2 ∗ N);

}

Este código é usado na seção 9.

13. Omitimos na impressão todas as entradas com frequência ZERO, para facilitar a leitura do resultado. ⟨ Imprime as tabelas na saída padrão e as elimina 13 ⟩ ≡

{ int i, max ;

fprintf (stdout , "Tabela␣de␣alturas\n");

for (i = 0, max = N + 1; i < max ; i{+ \atop +})

if (height table[i]) fprintf (stdout , "%d␣%d\n", i, height table[i]);

fprintf (stdout , "Tabela␣de␣IPLs\n");

for (i = 0, max = 1 + (N ∗ (N − 1))/2; i < max ; i{+ \atop +})

if (ipl table[i]) fprintf (stdout , "%d␣%d\n", i, ipl table[i]); free(height table); free(ipl table);

}

Este código é usado nas seções 9 e 14.

14. Para calcularmos estatísticas sobre árvores de busca binária vamos proceder de maneira semelhante. ⟨ Calcula estatísticas sobre árvores de busca binária 14 ⟩ ≡

{

if (gen tables ) { ⟨ Inicializa vetores que guardam as tabelas de frequência 11 ⟩ ⟨ Gera rep árvores de busca binária e cria as tabelas 15 ⟩ ⟨ Imprime as tabelas na saída padrão e as elimina 13 ⟩

} else ⟨ Gera rep árvores de busca binária e calcula seus parâmetros médios 16 ⟩

}

Este código é usado na seção 8.

Estatísticas sobre Árvores 6

15. ⟨ Gera rep árvores de busca binária e cria as tabelas 15 ⟩ ≡

{ int i; double ave height = 0; /∗ Altura média ∗/ double ave ipl = 0; /∗ IPL médio ∗/ for (i = 0; i < rep; i{+ \atop +}) \{

gen random bst (bst );

height = get bst height (bst );

ipl = get bst ipl (bst );

ave height += height ;

ave ipl += ipl ;

height table[height ]{+ \atop +};

ipl table[ipl ]{+ \atop +}; } fprintf (stdout , "Altura␣média:␣%f\n", ave height /rep); fprintf (stdout , "IPL␣médio:␣%f\n", ave ipl /rep); fprintf (stdout , "EPL␣médio:␣%f\n", ave ipl /rep + 2 ∗ N);

}

Este código é usado na seção 14.

16. ⟨ Gera rep árvores de busca binária e calcula seus parâmetros médios 16 ⟩ ≡

{ int i; double ave height = 0; /∗ Altura média ∗/ double ave ipl = 0; /∗ IPL médio ∗/ for (i = 0; i < rep; i{+ \atop +}) \{

gen random bst (bst );

ave height += get bst height (bst ); ave ipl += get bst ipl (bst );

} fprintf (stdout , "Altura␣média:␣%f\n", ave height /rep); fprintf (stdout , "IPL␣médio:␣%f\n", ave ipl /rep); fprintf (stdout , "EPL␣médio:␣%f\n", ave ipl /rep + 2 ∗ N);

}

Este código é usado na seção 14.

Estatísticas sobre Árvores 7 Índice Remissivo

argc: \underline{4}, 5. argv : \underline{4}, 5, 8. ave height : \underline{10}, \underline{12}, \underline{15}, \underline{16}. ave ipl : \underline{10}, \underline{12}, \underline{15}, \underline{16}. bs tree: 8. bst : 8, 15, 16. calloc: 11. control seq : 5, \underline{6}, 8. deinit bin tree gen: 8. destroy bst : 8. draw bst : 8. draw random tree: 8. draw tree: 5, \underline{6}, 8.

FALSE: \underline{3}, 6.

fprintf : 5, 8, 10, 11, 12, 13, 15, 16. free: 13. gen random bst : 8, 15, 16. gen tables : 5, \underline{6}, 9, 14. get bst height : 8, 15, 16. get bst ipl : 8, 15, 16. height : \underline{7}, 8, 10, 12, 15. height table: \underline{11}, 12, 13, 15. i: \underline{5}, \underline{10}, \underline{12}, \underline{13}, \underline{15}, \underline{16}. init bin tree gen: 8. init bst : 8. ipl : \underline{7}, 8, 10, 12, 15. ipl table: \underline{11}, 12, 13, 15. level sep: 5, \underline{6}, 8. main: \underline{4}. max : \underline{13}. N: \underline{6}. node type: 5, \underline{6}, 8. random tree params : 10, 12. rep: 5, \underline{6}, 10, 12, 15, 16. seed : 5, \underline{6}, 8. srand : 8. sscanf : 5. stderr : 5, 8, 11. stdout : 8, 10, 12, 13, 15, 16. time: 6. tree sep: 5, \underline{6}, 8. TRUE: \underline{3}, 5.

Estatísticas sobre Árvores 8

Listagem das seções

⟨ Calcula estatísticas sobre árvores binárias 9 ⟩ Usado na seção 8. ⟨ Calcula estatísticas sobre árvores de busca binária 14 ⟩ Usado na seção 8. ⟨ Executa opções dadas na linha de comando 8 ⟩ Usado na seção 4. ⟨ Função principal 4 ⟩ Usado na seção 3. ⟨ Gera rep árvores binárias e calcula seus parâmetros médios 10 ⟩ Usado na seção 9. ⟨ Gera rep árvores binárias e cria as tabelas 12 ⟩ Usado na seção 9. ⟨ Gera rep árvores de busca binária e calcula seus parâmetros médios 16 ⟩ Usado na seção 14. ⟨ Gera rep árvores de busca binária e cria as tabelas 15 ⟩ Usado na seção 14. ⟨ Imprime as tabelas na saída padrão e as elimina 13 ⟩ Usado nas seções 9 e 14. ⟨ Inicializa vetores que guardam as tabelas de frequência 11 ⟩ Usado nas seções 9 e 14. ⟨ Procura pelos argumentos de linha de comando 5 ⟩ Usado na seção 4.

⟨ Variáveis locais 6, 7 ⟩ Usado na seção 4.