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

1. Introdução

O módulo bs-tree permite a criação de árvores binárias de busca através da inserção de um número qualquer de elementos numa ordem aleatória. Os elementos em questão são números inteiros. As árvores são criadas principalmente para que sua altura e IPL sejam calculados.

Também permitimos a inserção de elementos passados através de um vetor pelo programa cliente, na ordem em que aparecem. Isso pode ser usado em conjunto com as funções que geram desenhos de árvores utilizando o formato do pacote PStricks, disponível para L^{A}TEX ou TEX, para gerar uma árvore específica.

O pacote disponibiliza o seguinte conjunto de funções. Veja suas definições para dados mais detalhados.

• init bst . Cria uma árvore vazia e retorna um ponteiro para ela.

• destroy bst . Destrói uma árvore criada com a função acima, liberando a memória que ocupa.

• get bst height . Calcula a altura da árvore.

• get bst ipl . Calcula o IPL da árvore.

• gen random bst . Gera uma árvore binária de busca através da inserção de uma permutação dos elementos do vetor a = (0, 1, …, N − 1), onde N é o número de nós internos da árvore a ser gerada.

• insert array . Insere os elementos de um vetor numa árvore de busca binária, na ordem crescente de seus índices.

• draw bst . Desenha uma árvore de busca binária utilizando a convenção do pacote PStricks.

⟨ bs-tree.h 1 ⟩ ≡

⟨ Typedefs 6 ⟩

⟨ Funções exportadas 16 ⟩

2. A estrutura geral do módulo é a seguinte:

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

#define FALSE 0

#define TRUE¬ FALSE

⟨ Estruturas de dados 4 ⟩

⟨ Variáveis globais 12 ⟩

⟨ Funções de manipulação de árvores 7 ⟩ ⟨ Funções privadas 17 ⟩ ⟨ Funções exportadas 16 ⟩ ⟨ Geração de árvores binárias de busca 19 ⟩ ⟨ Geração de desenhos 28 ⟩ Gerador de Árvores Binárias de Busca – Módulo bs-tree 2

3. Estruturas de dados

Vamos permitir que o programa cliente manipule várias árvores binárias de busca de tamanhos diferentes. Como o objetivo principal do módulo é permitir a geração de estatísticas sobre árvores binárias de busca, devemos também permitir que uma determinada árvore seja reutilizada diversas vezes com eficiência.

4. A representação que escolhemos é a usual para árvores binárias de busca. Nesta representação, um nó interno é uma estrutura que carrega um número inteiro (sua informação) e dois ponteiros para sua subárvore esquerda e direita. Um nó externo é um ponteiro nulo (Λ). ⟨ Estruturas de dados 4 ⟩ ≡

typedef struct node ∗link; struct node {

int info; /∗ Informação carregada pelo nó, que também é a chave ∗/ link left ; /∗ Ponteiro para a raiz da subárvore esquerda ∗/ link right ; /∗ Ponteiro para a raiz da subárvore direita ∗/

};

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

5. Uma árvore para o programa cliente não será um simples ponteiro para um nó, mas sim uma estrutura mais complicada, que guarda mais informações, como altura e IPL.

Para aumentarmos a eficiência na reutilização das árvores, não vamos permitir que nós internos sejam adicionados durante a execução. Isso significa que o número de nós internos da árvore deve ser conhecido durante sua criação. Desta forma, podemos alocar todos os nós internos necessários durante a inicialização, o que torna o programa mais eficiente. ⟨ Estruturas de dados 4 ⟩ +≡

typedef struct tree { link root ; /∗ Raiz da árvore ∗/ int N; /∗ Número máximo de nós internos ∗/ int height ; /∗ Altura da árvore ∗/ int ipl ; /∗ IPL da árvore ∗/ int free index ; /∗ Índice do primeiro nó livre em vertex array ∗/ link vertex array ; /∗ Essencial para a alocação/liberação da memória ∗/

} ∗bs tree;

6. O programa cliente vai ter acesso às nossas árvores binárias através de um ponteiro para struct tree, bs tree. Este é o único tipo exportado pelo módulo. ⟨ Typedefs 6 ⟩ ≡

typedef struct tree ∗bs tree;

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

7. Apenas árvores com um número máximo de nós internos maior que ZERO podem ser inicializadas. A função de inicialização recebe o número máximo de nós internos que a árvore poderá ter. Ela retorna um ponteiro para a nova árvore se tudo correr bem, Λ caso contrário. ⟨ Funções de manipulação de árvores 7 ⟩ ≡

bs tree init bst (int n)

{ bs tree new tree; /∗ Conterá o ponteiro de retorno ∗/ Gerador de Árvores Binárias de Busca – Módulo bs-tree 3

if (n ≤ 0) return Λ; ⟨ Aloca e inicializa estrutura tree 8 ⟩ ⟨ Aloca nós internos 9 ⟩ return new tree;

}

Veja também as seções 10, 13, 14 e 15. Este código é usado na seção 2.

8. ⟨ Aloca e inicializa estrutura tree 8 ⟩ ≡

{ new tree = malloc(sizeof (struct tree)); if (new tree ≡ Λ) return Λ; new tree root = Λ; new tree N = n; new tree height = new tree ipl = 0;

}

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

9. Alocaremos os nós internos em blocos, através da função calloc, o que torna o programa mais eficiente. Guardaremos o ponteiro retornado em vertex array . ⟨ Aloca nós internos 9 ⟩ ≡

{ link temp = calloc(n, sizeof (struct node)); if (temp ≡ Λ) return Λ; new tree vertex array = temp; new tree free index = 0;

}

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

10. A inserção na árvore é feita através de uma simples função recursiva. Utilizamos variáveis globais para aumentar a profundidade máxima da recursão.

Durante a inserção, já atualizamos o IPL e a altura da árvore. Para isso, utilizamos o argumento depth, que contém a altura da raiz sendo considerada. Inicialmente, deve ser igual a ZERO. ⟨ Funções de manipulação de árvores 7 ⟩ +≡

static link insertR(link root , int depth) {

if (root ≡ Λ) ⟨ Insere novo nó e o retorna 11 ⟩ if (root info > ins num) root left = insertR(root left , depth + 1); else root right = insertR(root right , depth + 1); return root ;

}

11. ⟨ Insere novo nó e o retorna 11 ⟩ ≡

{ link new node = ins bst vertex array + ins bst free index ; Gerador de Árvores Binárias de Busca – Módulo bs-tree 4

ins bst free index {+ \atop +}; /∗ O próximo nó livre ∗/ new node info = ins num; new node left = new node right = Λ; if (ins bst height ≤ depth) ins bst height = depth + 1; ins bst ipl += depth; return new node;

}

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

12. Vamos agora definir as variáveis globais utilizadas pela função insertR. A variável ins bst é um ponteiro para a árvore na qual está sendo inserido o elemento, contido na variável ins num. ⟨ Variáveis globais 12 ⟩ ≡

bs tree ins bst ; /∗ Árvore sendo considerada na inserção ∗/ int ins num; /∗ Elemento sendo inserido ∗/

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

13. Precisaremos também de um pequeno envelope para a função insertR, o que facilitará seu uso. ⟨ Funções de manipulação de árvores 7 ⟩ +≡

static void insert (bs tree bst , int num) {

ins bst = bst ;

ins num = num;

bst root = insertR(bst root , 0); }

14. Com o esquema de alocação que utilizamos, liberar a memória ocupada por uma árvore fica simples: basta liberar o vetor apontado por vertex array e a estrutura tree em si. ⟨ Funções de manipulação de árvores 7 ⟩ +≡

void destroy bst (bs tree bst ) {

free(bst vertex array );

free(bst ); }

15. Para que o programa cliente possa conhecer a altura e o IPL de uma árvore, disponibilizamos duas pequenas funções. ⟨ Funções de manipulação de árvores 7 ⟩ +≡

int get bst height (bs tree bst ) {

return bst height ; } int get bst ipl (bs tree bst ) {

return bst ipl ; } Gerador de Árvores Binárias de Busca – Módulo bs-tree 5

16. ⟨ Funções exportadas 16 ⟩ ≡ extern bs tree init bst (int); extern void destroy bst (bs tree); extern int get bst height (bs tree); extern int get bst ipl (bs tree);

Veja também as seções 25 e 33. Este código é usado nas seções 1 e 2.

17. ⟨ Funções privadas 17 ⟩ ≡ static link insertR(link, int); static void insert (bs tree, int);

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

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

18. Geração de árvores binárias de busca

Vamos disponibilizar funções para gerar uma árvore binária de busca a partir de uma permutação qualquer de um determinado número de chaves.

Também permitimos que uma árvore seja gerada a partir da inserção de uma determinada sequência de chaves na ordem em que aparecem.

19. Para gerarmos uma árvore de N nós internos, vamos criar uma permutação a′ do vetor a = (0, 1, …, N − 1) e inserir na árvore os elementos a′_{0}, a′_{1}, …, a′_{N−1}, nesta ordem. ⟨ Geração de árvores binárias de busca 19 ⟩ ≡

void gen random bst (bs tree bst )

{ ⟨ Limpeza da árvore 20 ⟩ ⟨ Criação e permutação do vetor a 21 ⟩ ⟨ Inserção dos elementos 22 ⟩

}

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

20. Antes de podermos inserir elementos na árvore, devemos limpá-la, ou seja, fazer com que o primeiro nó livre para inserção seja o primeiro do vetor vertex array e modificar o valor de sua altura e IPL para ZERO. Graças a maneira como alocamos os nós internos, isso é bem simples. ⟨ Limpeza da árvore 20 ⟩ ≡

{ bst root = Λ; bst height = bst ipl = 0; bst free index = 0;

}

Este código é usado nas seções 19 e 23.

21. Representaremos o vetor a no próprio vetor vertex array , ao invés de criar outro vetor temporário. ⟨ Criação e permutação do vetor a 21 ⟩ ≡

{ int i; link temp = bst vertex array ; for (i = 0; i < bst N; temp[i{+ \atop +}].info = i) ; for (i = 0; i < bst N; i{+ \atop +}) \{

int j = (int)((double) bst N ∗ rand ( )/(RAND_MAX + 1.0)); int d = temp[j].info; temp[j].info = temp[i].info; temp[i].info = d;

} }

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

22. Agora inserimos os elementos do vetor vertex array na ordem vertex array [0], …, vertex array [N − 1]. Note que, quando inserimos os elementos utilizando a função insertR, o primeiro elemento livre do vetor vertex array é utilizado pela função na inserção. Desta forma, não corremos o risco de perder dados.

Gerador de Árvores Binárias de Busca – Módulo bs-tree 7

⟨ Inserção dos elementos 22 ⟩ ≡

{ int i; link temp = bst vertex array ; for (i = 0; i < bst N; insert (bst , temp[i{+ \atop +}].info)) ;

}

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

23. Para inserirmos uma sequência de chaves, passada pelo programa cliente, na árvore, procedemos de maneira semelhante ao que é feito pela função gen random bst . ⟨ Geração de árvores binárias de busca 19 ⟩ +≡

void insert array (bs tree bst , int array size, int ∗array ) {

⟨ Limpeza da árvore 20 ⟩

⟨ Inserção do vetor array 24 ⟩ }

24. ⟨ Inserção do vetor array 24 ⟩ ≡

{ int i; for (i = 0; i < array size; insert (bst , array [i{+ \atop +}])) ;

}

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

25. ⟨ Funções exportadas 16 ⟩ +≡ extern void gen random bst (bs tree); extern void insert array (bs tree, int, int ∗); Gerador de Árvores Binárias de Busca – Módulo bs-tree 8

26. Geração de desenhos

As funções que disponibilizamos para gerar desenhos de árvores binárias geram, na verdade, código compatível com o pacote PStricks, disponível para L^{A}TEX ou TEX.

Várias opções do pacote podem ser utilizadas para personalizar as árvores desenhadas. Veja a documentação do pacote para maiores detalhes.

27. Vamos desenhar a árvore recursivamente, percorrendo-a em pré-ordem. Para aumentarmos o limite da profundidade de recursão, vamos utilizar algumas variáveis globais para controlar o processo. Estas variáveis vão conter, basicamente, os estilos dos nós a serem criados. ⟨ Variáveis globais 12 ⟩ +≡

static int dtree control seq ; /∗ Veja abaixo ∗/

static const char ∗dtree node type; /∗ Estilo do nó ∗/

static FILE ∗dtree output ; /∗ Stream para o qual será enviada a saída ∗/

28. A função que realmente desenha a árvore é uma função recursiva que a percorre em pré-ordem, imprimindo o código necessário. Esta é uma função interna, a função exportada é na verdade apenas um envelope.

#define MAX_BUFFER 255

⟨ Geração de desenhos 28 ⟩ ≡ static void draw bstR(link root ) {

static char buffer [MAX_BUFFER];

⟨ Se root aponta para uma folha ou nó externo, executa base da recursão 29 ⟩ ⟨ Imprime a raiz 30 ⟩ draw bstR(root left ); draw bstR(root right ); fprintf (dtree output , "}\n");

}

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

29. A base da recursão não ocorre simplesmente quando root ≡ Λ, mas também quando root ≠ Λ e root left ≡ root right ≡ Λ.

Fazemos isso pois queremos distinguir o caso em que estamos tratando de uma folha, situação na qual não fazemos a impressão de nós externos, e o caso em que estamos tratando de um nó externo, filho de algum nó interno que não é uma folha. Neste último caso, devemos imprimir o nó externo, para que o lay-out da árvore seja adequado. ⟨ Se root aponta para uma folha ou nó externo, executa base da recursão 29 ⟩ ≡

{

if (root ≡ Λ) { /∗ Se isso ocorre, root não é filho de uma folha ∗/ fprintf (dtree output , "\\Tn␣"); return;

}

else if (root left ≡ Λ ∧ root right ≡ Λ) {

if (dtree control seq ) { sprintf (buffer , dtree node type, root info); fprintf (dtree output , "%s␣", buffer );

}

else fprintf (dtree output , "%s␣", dtree node type); return;

} }

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

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

30. Se a base não foi executada, devemos imprimir a raiz da árvore em questão, para depois imprimirmos a subárvore esquerda e a subárvore direita. Permitimos que o programa cliente utilize, para espeficiar o tipo de nó a ser utilizado, as sequências de controle permitidas pela função sprintf . A variável dtree control seq indica se isso ocorre ou não. ⟨ Imprime a raiz 30 ⟩ ≡

{

if (dtree control seq ) { /∗ Devemos considerar sequências de controle ∗/ sprintf (buffer , dtree node type, root info); fprintf (dtree output , "\\pstree{%s}{\n", buffer );

}

else fprintf (dtree output , "\\pstree{%s}{\n", dtree node type); }

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

31. ⟨ Funções privadas 17 ⟩ +≡ static void draw bstR(link);

32. O envelope da função draw bstR faz um pouco mais do que simplesmente chamar a função recursiva, uma vez que algumas informações precisam ser impressas junto a raiz da árvore a ser impressa.

Os argumentos level sep e tree sep especificam a distância entre dois níveis da árvore e a distância entre duas subárvores. Os valores esperados são sequências de caracteres do tipo "2mm".

O parâmetro node type permite a especificação do tipo de nó interno a ser utilizado. O valor esperado é uma sequência do tipo "\\Tc*{2pt}". Como os nós contém informação, permitimos que esta informação seja impressa. Se o argumento control seq é verdadeiro, sequências de controle como as utilizadas pela função sprintf serão substituídas pela informação do nó.

Por exemplo, para imprimir o número associado a um nó dentro dele no desenho, pode-se utilizar em node type a sequência "\\Toval{%d}" e passar o argumento control seq como sendo verdadeiro.

Finalmente, output deve conter um ponteiro para o stream de saída. ⟨ Geração de desenhos 28 ⟩ +≡

void draw bst (bs tree bst , int control seq , const char ∗node type, const char ∗level sep, const char

∗tree sep, FILE ∗output )

{

if (control seq ) { char buffer [MAX_BUFFER]; sprintf (buffer , node type, bst root info);

      fprintf (output , "\\pstree[levelsep=%s,␣treesep=%s]{%s}{\n", level sep, tree sep, buffer );

}

else fprintf (output , "\\pstree[levelsep=%s,␣treesep=%s]{%s}{\n", level sep, tree sep, node type); dtree control seq = control seq ; dtree node type = node type; dtree output = output ; draw bstR(bst root left ); draw bstR(bst root right ); fprintf (output , "}\n");

}

33. ⟨ Funções exportadas 16 ⟩ +≡ extern void draw bst (bs tree, int, const char ∗, const char ∗, const char ∗, FILE ∗); Gerador de Árvores Binárias de Busca – Módulo bs-tree 10 Índice Remissivo

array : \underline{23}, 24. array size: \underline{23}, 24. bs tree: \underline{5}, \underline{6}, 7, 12, 13, 14, 15, 16, 17, 19, 23,

25, 32, 33. bst : \underline{13}, \underline{14}, \underline{15}, \underline{19}, 20, 21, 22, \underline{23}, 24, \underline{32}. buffer : \underline{28}, 29, 30, \underline{32}. calloc: 9. control seq : \underline{32}. d: \underline{21}. depth: \underline{10}, 11. destroy bst : 1, \underline{14}, \underline{16}. draw bst : 1, \underline{32}, \underline{33}. draw bstR: \underline{28}, \underline{31}, 32. dtree control seq : \underline{27}, 29, 30, 32. dtree node type: \underline{27}, 29, 30, 32. dtree output : \underline{27}, 28, 29, 30, 32.

FALSE: \underline{2}.

fprintf : 28, 29, 30, 32. free: 14. free index : \underline{5}, 9, 11, 20. gen random bst : 1, \underline{19}, 23, \underline{25}. get bst height : 1, \underline{15}, \underline{16}. get bst ipl : 1, \underline{15}, \underline{16}. height : \underline{5}, 8, 11, 15, 20. i: \underline{21}, \underline{22}, \underline{24}. info: \underline{4}, 10, 11, 21, 22, 29, 30, 32. init bst : 1, \underline{7}, \underline{16}. ins bst : 11, \underline{12}, 13. ins num: 10, 11, \underline{12}, 13. insert : \underline{13}, \underline{17}, 22, 24. insert array : 1, \underline{23}, \underline{25}. insertR: \underline{10}, 12, 13, \underline{17}, 22. ipl : \underline{5}, 8, 11, 15, 20. j: \underline{21}. left : \underline{4}, 10, 11, 28, 29, 32. level sep: \underline{32}. link: \underline{4}, 5, 9, 10, 11, 17, 21, 22, 28, 31. malloc: 8.

MAX_BUFFER: \underline{28}, 32.

N: \underline{5}. n: \underline{7}. new node: \underline{11}. new tree: \underline{7}, 8, 9. node: \underline{4}, 9. node type: \underline{32}. num: \underline{13}. output : \underline{32}. rand : 21.

RAND_MAX: 21.

right : \underline{4}, 10, 11, 28, 29, 32. root : \underline{5}, 8, \underline{10}, 13, 20, \underline{28}, 29, 30, 32. sprintf : 29, 30, 32. temp: \underline{9}, \underline{21}, \underline{22}.

tree: \underline{5}, 6, 8, 14.
tree sep: \underline{32}.

                                                   TRUE: \underline{2}.

vertex array : \underline{5}, 9, 11, 14, 20, 21, 22.

Gerador de Árvores Binárias de Busca – Módulo bs-tree 11

Listagem das seções

⟨ Aloca e inicializa estrutura tree 8 ⟩ Usado na seção 7. ⟨ Aloca nós internos 9 ⟩ Usado na seção 7. ⟨ Criação e permutação do vetor a 21 ⟩ Usado na seção 19. ⟨ Estruturas de dados 4, 5 ⟩ Usado na seção 2. ⟨ Funções de manipulação de árvores 7, 10, 13, 14, 15 ⟩ Usado na seção 2.

⟨ Funções exportadas 16, 25, 33 ⟩ Usado nas seções 1 e 2. ⟨ Funções privadas 17, 31 ⟩ Usado na seção 2.

⟨ Geração de árvores binárias de busca 19, 23 ⟩ Usado na seção 2. ⟨ Geração de desenhos 28, 32 ⟩ Usado na seção 2.

⟨ Imprime a raiz 30 ⟩ Usado na seção 28.

⟨ Inserção do vetor array 24 ⟩ Usado na seção 23. ⟨ Inserção dos elementos 22 ⟩ Usado na seção 19. ⟨ Insere novo nó e o retorna 11 ⟩ Usado na seção 10.

⟨ Limpeza da árvore 20 ⟩ Usado nas seções 19 e 23.

⟨ Se root aponta para uma folha ou nó externo, executa base da recursão 29 ⟩ Usado na seção 28.

⟨ Typedefs 6 ⟩ Usado na seção 1. ⟨ Variáveis globais 12, 27 ⟩ Usado na seção 2.

⟨ bs-tree.h 1 ⟩