Gerador de Árvores Binárias – Módulo bin-tree 1

1. Introdução

O módulo bin-tree disponibiliza várias funções que podem ser utilizadas com árvores binárias, as principais podendo ser utilizadas para computar parâmetros sobre árvores binárias geradas aleatóriamente.

Outro conjunto de funções pode ser utilizado em conjunto com o pacote PStricks, disponível para L^{A}TEX ou TEX. Estas funções podem ser utilizadas para criar figuras das árvores binárias geradas pelo módulo.

2. Instruções. Para que o módulo seja utilizado por um programa, basta incluir neste o arquivo bin-tree.h e compilar o arquivo bin-tree.c juntamente com o restante do programa. O módulo faz uso da biblioteca de funções matemáticas.

Antes de poder utilizar qualquer função disponibilizada pelo módulo, deve-se chamar a função init bin tree gen passando como argumento o maior número de nós que uma árvore a ser gerada pelo módulo vai possuir. Apenas árvores com esta quantidade de nós ou menos poderão ser geradas.

Antes de encerrar seu funcionamento, o programa principal deverá chamar a função deinit bin tree gen para liberar a memória alocada pelo módulo.

Além destas funções, o módulo oferece outras duas funções, que são rapidamente descritas abaixo. Para maiores instruções de uso, veja as seções adequadas.

• random tree params . Calcula a altura e o IPL de uma árvore binária de N nós internos gerada aleatóriamente.

• draw random tree. Gera código compatível com o pacote PStricks do L^{A}TEX ou TEX que representa uma árvore binária de N nós internos gerada aleatóriamente. Também retorna a altura e o IPL da árvore gerada.

⟨ bin-tree.h 2 ⟩ ≡

⟨ Funções exportadas 12 ⟩

3. Memória. O uso de memória para iniciar o gerador pode ser grande, especialmente para valores grandes de N, o número de nós internos das árvores a serem geradas. No total, alocaremos N + 1 ponteiros e

∑_{i=2}^{N} i = \frac{N^{2} + N − 2}{2} = Θ(N^{2})

variáveis do tipo double. Se N = 5000, sizeof (void ∗) = 4 bytes e sizeof (double) = 8 bytes, a memória alocada totalizaria 95.40mb. Entretanto, se não procedermos dessa maneira, o tempo de processamento seria muito elevado, inviabilizando o uso do gerador para números grandes.

4. A estrutura geral do módulo se encontra abaixo.

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

#define FALSE 0

#define TRUE¬ FALSE

⟨ Variáveis globais 6 ⟩

⟨ Funções privadas 16 ⟩

⟨ Funções exportadas 12 ⟩

⟨ Geração de árvores binárias 7 ⟩ Gerador de Árvores Binárias – Módulo bin-tree 2

5. Geração de árvores binárias

Para que todas as árvores binárias tenham a mesma probabilidade de serem geradas por nosso algoritmo, ele deve de alguma forma levar em consideração a probabilidade de uma árvore binária de N nós internos possuir L nós em sua subárvore esquerda e R nós em sua subárvore direita.

Sabemos que a quantidade de árvores binárias com N nós internos é dada pela seguinte expressão:

C_{N} = \frac{1}{N + 1} ( \begin{matrix}2N \\ N \end{matrix} )

Então, a probabilidade de uma árvore com N nós internos ter em sua subárvore esquerda L nós internos e em sua subárvore direita R nós internos seria

P_{N}(L) = \frac{C_{L}C_{R}}{C_{N}} ,  (1)

onde R = N − 1 − L.

Utilizando a aproximação de Stirling, podemos concluir que, para L ≠ 0 e L ≠ N − 1,

P_{N}(L) ≈ \frac{(N + 1)\sqrt{πN}}{4π(L + 1)(R + 1)\sqrt{LR}}.

Agora, fazendo ρ = \sqrt{π}/4π = 0.141047396..., teríamos

P_{N}(L) ≈ ρ · \frac{(N + 1)\sqrt{N}}{(L + 1)(R + 1)\sqrt{LR}}.  (2)

Para L = 0 ou R = 0, teríamos segundo a equação (1)

P_{N}(0) = \frac{N + 1}{4N − 2}.  (3)

Para fazermos um algoritmo de geração de árvores binárias, vamos utilizar as equações (2) e (3) para calcularmos as probabilidades necessárias. Manteremos estes valores em uma tabela, para evitarmos ter de recalculá-los.

6. Nossa tabela de probabilidades vai ser um vetor de N + 1 posições. Na i-ésima posição, teremos um ponteiro para um outro vetor de i posições. Na j-ésima posição deste último vetor, teremos o valor

F_{i}(j) = ∑_{k=0}^{j} P_{i}(k),  (4)

ou seja, o valor acumulado das probabilidades de uma árvore binária com i nós internos ter uma subárvore esquerda com uma quantidade de nós internos no intervalo [0, j] ∩ Z.

Os valores de P_{N}(L) são simétricos. Entretanto, para adicionarmos velocidade aos cálculos, não vamos utilizar esta propriedade para poupar espaço.

Para evitar ter de calcular raízes de muitos valores, manteremos também um vetor com as raízes de todos os números inteiros entre 0 e N. #define RHO 0.141047396 /∗ Utilizada na geração das probabilidades ∗/ ⟨ Variáveis globais 6 ⟩ ≡

static double ∗sqr = Λ; /∗ sqr [i] = \sqrt{i} ∗/

static double ∗∗prob table = Λ; /∗ Tabela de probabilidades ∗/ static int N = 0; /∗ Índice da última posição de prob table ∗/

Veja também as seções 17 e 24. Este código é usado na seção 4.

Gerador de Árvores Binárias – Módulo bin-tree 3

7. A tabela será alocada e gerada quando o módulo for inicializado. Para tanto, precisaremos conhecer seu tamanho, que será igual a N + 1. Poderemos então gerar árvores aleatórias com até N nós internos.

A função init bin tree gen devolve TRUE se tudo correr bem e FALSE se houver algum erro. ⟨ Geração de árvores binárias 7 ⟩ ≡

int init bin tree gen(int n) {

if (n < 2) return FALSE; ⟨ Aloca espaço para prob table e sqr 8 ⟩ ⟨ Preenche sqr 9 ⟩ ⟨ Preenche tabela de probabilidades 10 ⟩ free(sqr ); /∗ Não utilizaremos as raízes para mais nada ∗/ sqr = Λ; N = n; return TRUE;

}

Veja também as seções 11, 13, 18, 20 e 25. Este código é usado na seção 4.

8. ⟨ Aloca espaço para prob table e sqr 8 ⟩ ≡

{ int i; sqr = malloc((n + 1) ∗ sizeof (double)); if (sqr ≡ Λ) return FALSE; prob table = malloc((n + 1) ∗ sizeof (double ∗)); if (prob table ≡ Λ) return FALSE; for (i = 2; i ≤ n; i{+ \atop +}) \{

prob table[i] = malloc(i ∗ sizeof (double));

if (prob table[i] ≡ Λ) return FALSE; }

}

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

9. ⟨ Preenche sqr 9 ⟩ ≡

{ int i; sqr [0] = 0; sqr [1] = 1; for (i = 2; i ≤ n; sqr [i{+ \atop +}] = sqrt (i)) ;

}

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

10. As primeiras duas posições de prob table existem apenas para facilitar a manipulação de índices. Não as utilizamos de qualquer outra maneira. ⟨ Preenche tabela de probabilidades 10 ⟩ ≡

{ int i; for (i = 2; i ≤ n; i{+ \atop +}) \{

int j, max = i − 1;

double rho = RHO ∗ (i + 1) ∗ sqr [i]; /∗ Constante modificada para diminuir cálculos ∗/ Gerador de Árvores Binárias – Módulo bin-tree 4

prob table[i][0] = (double)(i + 1)/(4 ∗ i − 2);

for (j = 1; j < max ; j{+ \atop +})

prob table[i][j] = prob table[i][j − 1] + (rho/((j + 1) ∗ (i − j) ∗ sqr [j] ∗ sqr [i − 1 − j])); prob table[i][max ] = 2.0; /∗ Evita erros de aproximação e é utilizado como sentinela ∗/

} }

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

11. O programa cliente deve informar ao módulo que a memória alocada para as tabelas deve ser desalocada antes do programa ser encerrado. Isso é feito através da função deinit bin tree gen. ⟨ Geração de árvores binárias 7 ⟩ +≡

void deinit bin tree gen( )

{ int i; for (i = 2; i ≤ N; free(prob table[i{+ \atop +}])) ; free(prob table); prob table = Λ; N = 0;

}

12. ⟨ Funções exportadas 12 ⟩ ≡ extern int init bin tree gen(int); extern void deinit bin tree gen( );

Veja também as seções 19 e 27. Este código é usado nas seções 2 e 4.

13. Agora apresentamos a função random tree paramsR, que calcula a altura e o IPL de uma árvore binária gerada aleatóriamente. A árvore não é de fato armazenada: a própria função de geração calcula seus parâmetros a medida que prossegue, fazendo isso de forma recursiva.

Esta função não é visível ao programa cliente, sendo acessada através de um envelope que será mostrado mais a frente.

Os argumentos recebidos são a profundidade da raiz da árvore sendo gerada e o número de nós que possui. A profundidade deve ser ZERO na primeira chamada. ⟨ Geração de árvores binárias 7 ⟩ +≡

static void random tree paramsR(int n, int depth)

{ ⟨ Executa base da recursão 14 ⟩ rtree ipl += depth; /∗ Atualizamos apenas o IPL, a altura atualizamos na base ∗/ ⟨ Sorteia tamanho das subárvores e executa recursão 15 ⟩

}

14. ⟨ Executa base da recursão 14 ⟩ ≡ if (n ≡ 0) return; else if (n ≡ 1) {

if (depth + 1 > rtree height ) rtree height = depth + 1;

rtree ipl += depth;

return; }

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

Gerador de Árvores Binárias – Módulo bin-tree 5

15. Para fazermos o sorteio do tamanho das subárvores nos aproveitamos do fato de prob table estar arranjada como dado pela equação (4). Podemos então utilizar um algoritmo rápido de busca binária para determinar o tamanho da subárvore esquerda. ⟨ Sorteia tamanho das subárvores e executa recursão 15 ⟩ ≡

{ int i = 0, j = n − 1, m; double temp = (double) rand ( )/RAND_MAX; while (i < j) { m = (i + j)/2; if (prob table[n][m] ≡ temp) break; /∗ Altamente improvável, mas é uma possibilidade ∗/ else if (prob table[n][m] > temp) j = m − 1; else i = m + 1;

}

if (i < j) i = m; /∗ O improvável aconteceu! ∗/

else if (prob table[n][i] < temp) i{+ \atop +};

random tree paramsR(i, depth + 1); /∗ Subárvore esquerda ∗/ random tree paramsR(n − 1 − i, depth + 1); /∗ Subárvore direita ∗/

}

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

16. ⟨ Funções privadas 16 ⟩ ≡ static void random tree paramsR(int, int);

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

17. Antes de apresentarmos o envelope para a função random tree paramsR, definimos as variáveis globais que assumimos em seu desenvolvimento. ⟨ Variáveis globais 6 ⟩ +≡

static int rtree height = 0; /∗ Altura da árvore sendo gerada ∗/ static int rtree ipl = 0; /∗ IPL da árvore sendo gerada ∗/

18. Finalmente, o evelope. As variáveis apontadas por height e ipl conterão no retorno estes parâmetros. ⟨ Geração de árvores binárias 7 ⟩ +≡

void random tree params (int n, int ∗height , int ∗ipl )

{ rtree height = 0; rtree ipl = 0; random tree paramsR(n, 0); ∗height = rtree height ; ∗ipl = rtree ipl ;

}

19. ⟨ Funções exportadas 12 ⟩ +≡ extern void random tree params (int, int ∗, int ∗);

20. Para criarmos figuras das árvores a medida que as geramos utilizamos basicamente uma cópia da função anterior, também colocando o código de geração. Pouca coisa precisa ser mudada para tanto.

Gerador de Árvores Binárias – Módulo bin-tree 6

⟨ Geração de árvores binárias 7 ⟩ +≡ static void draw random treeR(int n, int depth) {

⟨ Se n ≡ 1 ou n ≡ 0, cria uma folha ou nó externo 22 ⟩ rtree ipl += depth; /∗ Atualizamos apenas o IPL, a altura atualizamos na base ∗/ fprintf (dtree output , "\\pstree{%s}{\n", dtree nodetype); ⟨ Sorteia tamanho das subárvores e as gera recursivamente 21 ⟩ fprintf (dtree output , "\n}");

}

21. ⟨ Sorteia tamanho das subárvores e as gera recursivamente 21 ⟩ ≡

{ int i = 0, j = n − 1, m; double temp = (double) rand ( )/RAND_MAX; while (i < j) {

m = (i + j)/2;

if (prob table[n][m] ≡ temp) break; /∗ Altamente improvável, mas é uma possibilidade ∗/ else if (prob table[n][m] > temp) j = m − 1; else i = m + 1;

} if (i < j) i = m; /∗ O improvável aconteceu! ∗/ else if (prob table[n][i] < temp) i{+ \atop +}; draw random treeR(i, depth + 1); /∗ Subárvore esquerda ∗/ draw random treeR(n − 1 − i, depth + 1); /∗ Subárvore direita ∗/

}

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

22. Os nós externos são “impressos” como nós nulos, que apenas ocupam espaço. Nenhum nó nulo é gerado para folhas, que são explicitamente impressas. ⟨ Se n ≡ 1 ou n ≡ 0, cria uma folha ou nó externo 22 ⟩ ≡

if (n ≡ 0) { fprintf (dtree output , "\\Tn␣"); return;

} else if (n ≡ 1) {

if (depth + 1 > rtree height ) rtree height = depth + 1; fprintf (dtree output , "%s␣", dtree nodetype); rtree ipl += depth; return;

}

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

23. ⟨ Funções privadas 16 ⟩ +≡ static void draw random treeR(int, int);

24. Para que a função funcione, são necessárias duas variáveis globais que guardam informações sobre a saída desejada. Vamos definí-las agora. ⟨ Variáveis globais 6 ⟩ +≡

static const char ∗dtree nodetype = Λ; /∗ Tipo do nó ∗/ static FILE ∗dtree output = Λ; /∗ Stream para o qual será mandada a saída ∗/ Gerador de Árvores Binárias – Módulo bin-tree 7

25. O envelope da função draw random treeR é ligeiramente diferente do envelope da função random tree params . Algumas configurações da saída devem ser conhecidas de início e impressas junto a raiz da árvore, portanto, a raiz é processada explicitamente.

Os argumentos levelsep, treesep e nodetype são obrigatórios. Eles definem a distância entre dois níveis da árvore, a distância entre duas subárvores e o tipo do nó que será utilizado, repectivamente. O valor esperado é uma sequência de caracteres como "2cm", por exemplo. No caso de nodetype, o argumento é algo como "\\Tc*{2pt}"^{1}, por exemplo. O argumento output é um ponteiro para o stream para o qual será jogada a saída. ⟨ Geração de árvores binárias 7 ⟩ +≡

void draw random tree(int n, int ∗height , int ∗ipl , const char ∗levelsep, const char ∗treesep, const char

∗nodetype, FILE ∗output )

{ rtree height = 0; rtree ipl = 0; dtree output = output ; dtree nodetype = nodetype; fprintf (output , "\\pstree[levelsep=%s,␣treesep=%s]{%s}{\n", levelsep, treesep, nodetype); ⟨ Sorteia tamanho das subárvores e chama a função draw random treeR 26 ⟩ fprintf (output , "\n}"); ∗height = rtree height ; ∗ipl = rtree ipl ;

}

26. ⟨ Sorteia tamanho das subárvores e chama a função draw random treeR 26 ⟩ ≡

{ int i; double temp = (double) rand ( )/RAND_MAX; for (i = 0; i < n; i{+ \atop +})

if (temp < prob table[n][i]) break; draw random treeR(i, 1); /∗ Subárvore esquerda ∗/ draw random treeR(n − 1 − i, 1); /∗ Subárvore direita ∗/

}

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

27. ⟨ Funções exportadas 12 ⟩ +≡ extern void draw random tree(int, int ∗, int ∗, const char ∗, const char ∗, const char ∗, FILE ∗); Gerador de Árvores Binárias – Módulo bin-tree 8 Índice Remissivo

1Veja a documentação do pacote PStricks

deinit bin tree gen: 2, \underline{11}, \underline{12}. depth: \underline{13}, 14, 15, \underline{20}, 21, 22. draw random tree: 2, \underline{25}, \underline{27}. draw random treeR: \underline{20}, 21, \underline{23}, 25, 26. dtree nodetype: 20, 22, \underline{24}, 25. dtree output : 20, 22, \underline{24}, 25. FALSE: \underline{4}, 7, 8. fprintf : 20, 22, 25. free: 7, 11. height : \underline{18}, \underline{25}. i: \underline{8}, \underline{9}, \underline{10}, \underline{11}, \underline{15}, \underline{21}, \underline{26}. init bin tree gen: 2, \underline{7}, \underline{12}. ipl : \underline{18}, \underline{25}. j: \underline{10}, \underline{15}, \underline{21}. levelsep: \underline{25}. m: \underline{15}, \underline{21}. malloc: 8. max : \underline{10}. N: \underline{6}. n: \underline{7}, \underline{13}, \underline{18}, \underline{20}, \underline{25}. nodetype: \underline{25}. output : \underline{25}. prob table: \underline{6}, 8, 10, 11, 15, 21, 26. rand : 15, 21, 26. RAND_MAX: 15, 21, 26. random tree params : 2, \underline{18}, \underline{19}, 25. random tree paramsR: \underline{13}, 15, \underline{16}, 17, 18. rho: \underline{10}. RHO: \underline{6}, 10. rtree height : 14, \underline{17}, 18, 22, 25. rtree ipl : 13, 14, \underline{17}, 18, 20, 22, 25. sqr : \underline{6}, 7, 8, 9, 10. sqrt : 9. temp: \underline{15}, \underline{21}, \underline{26}. treesep: \underline{25}. TRUE: \underline{4}, 7.

Gerador de Árvores Binárias – Módulo bin-tree 9

Listagem das seções

⟨ Aloca espaço para prob table e sqr 8 ⟩ Usado na seção 7. ⟨ Executa base da recursão 14 ⟩ Usado na seção 13.

⟨ Funções exportadas 12, 19, 27 ⟩ Usado nas seções 2 e 4. ⟨ Funções privadas 16, 23 ⟩ Usado na seção 4. ⟨ Geração de árvores binárias 7, 11, 13, 18, 20, 25 ⟩ Usado na seção 4.

⟨ Preenche tabela de probabilidades 10 ⟩ Usado na seção 7.

⟨ Preenche sqr 9 ⟩ Usado na seção 7.

⟨ Se n ≡ 1 ou n ≡ 0, cria uma folha ou nó externo 22 ⟩ Usado na seção 20. ⟨ Sorteia tamanho das subárvores e as gera recursivamente 21 ⟩ Usado na seção 20. ⟨ Sorteia tamanho das subárvores e chama a função draw random treeR 26 ⟩ Usado na seção 25. ⟨ Sorteia tamanho das subárvores e executa recursão 15 ⟩ Usado na seção 13.

⟨ Variáveis globais 6, 17, 24 ⟩ Usado na seção 4.

⟨ bin-tree.h 2 ⟩