Árvore binária

Nesta versão do programa contador de palavras é utilizado como contentor de palavras uma árvore binária de utilização genérica.

Uma árvore binária é um caso particular de contentor de pares chave/valor. Quando balanceada apresenta custo de pesquisa de ordem \(log_2 N\).

O elemento de dado é a struct word. A chave de ordenação é o texto da própria palavra contida nesta struct.

struct word {
	char *text;
	int counter;
};
Listagem 106 Programa contador de palavras baseado em árvore binária (wcounter_tree.c)
 1int main(int argc, char *argv[]) {
 2	FILE *fd = fopen(argv[1], "r");
 3	int nwords = 0;
 4	struct tree_node *words = NULL;
 5	unsigned initial_timepoint = get_time();
 6	char *word_text;
 7	while ((word_text = read_word(fd, separators)) != NULL) {
 8		nwords++;
 9		struct word key = {.text = word_text};
10		struct tree_node *node = tree_search(words, &key, word_cmp_text);
11		if (node != NULL) {
12			struct word *word = tree_data(node);
13			word->counter++;
14		}
15		else {
16			struct word *word = malloc(sizeof *word);
17			word->counter = 1;
18			word->text = strdup(word_text);
19			words = tree_insert(words, word, word_cmp_text);
20		}
21	}
22	unsigned duration = get_time() - initial_timepoint;
23	printf("Total de palavras = %d; "
24		"Palavras diferentes = %ld; Time = %d ms\n",
25		nwords, tree_size(words), duration);
26	fclose(fd);
27	tree_foreach(words, free_word);
28	tree_destroy(words);
29}

A fase de leitura e contabilização de palavras processa-se entre as linhas 7 e 21. Depois da leitura (linha 7), a palavra é procurada na árvore com a função tree_search. Se a palavra já existir (node != NULL), o respetivo contador é incrementado (linha 13). Se a palavra ainda não exitir, é necessário alocar memória para um novo objeto struct word (linha 16), preenchê-lo com a informação da palavra (linhas 17 e 18) e por fim inseri-lo no contentor de palavras (linha 19).

Terminda a recolha de palavras, e depois de apresentados os resultados (linhas 22 a 25), são libertados os recursos alocados. No que respeita ao contentor de palavras, primeiro percorre-se a àrvore e eliminam-se os objectos com a informação das palavras – todas as struct word (linha 27). Em seguida, elimina-se a própria àrvore – todas as struct tree (linhas 28).

Criação da árvore

A árvore binária genérica é formada por nós do tipo struct tree_node.

struct tree_node {
	struct tree_node *left, *right;
	void *data;
};

Os campos left e right apontam, respetivamente, para as sub-árvores esquerda e direita. O campo data aponta para os dados de utilização.

A associação chave-valor é baseada nos dados de utilização.

Uma árvore é representada por um ponteiro para o nó raíz. Uma árvore vazia não contém qualquer nó. Por isso, uma árvore vazia é representada pelo valor NULL (linha 4).

Procura da palavra

A operação de procura da palavra é realizada pela função tree_search. Esta função recebe a chave de informação a procurar (&key) e a função de comparação word_cmp_text.

key é uma variável local, pois serve apenas para a operação de procura. Porque é que o ponteiro word_text, que aponta para a palavra acabada de ler, não é utilizada diretamente como chave de procura? – Para se reutilizar a mesma função de comparação utilizada na inserção de palavra (word_cmp_text).

Inserção da palavra

tree_insert

A operação de inserção engloba a procura do local de inserção. Nessa procura, a palavra que se pretende inserir (parâmetro data) é comparada com as palavras já inseridas. A comparação é realizada por uma função específica, fornecida pelo código de utilização, no parâmetro compare (linha 11).

Se a palavra já existir, caso em que a função de comparação devolve zero, é retornado o ponteiro para o nó corrente e não é inserido novo nó. Caso contrário, é realizada uma invocação recursiva na direção da inserção ordenada. Quando se chega ao ponto em que já não há mais nós descendentes (root == NULL) é altura de criar um novo nó (linhas 4 a 9).

O estabelecimento da ligação de um nó para o nó descendente é realizado na intância de chamada anterior à instância de criação do novo nó (linhas 13 ou 15).

Listagem 108 Inserir nó na árvore (tree.c)
 1struct tree_node *tree_insert(struct tree_node *root, void *data,
 2					int (*compare)(const void*, const void*)) {
 3	if (NULL == root) {
 4		struct tree_node *new_node = malloc(sizeof *new_node);
 5		if (NULL == new_node)
 6			return NULL;
 7		new_node->left = new_node->right = NULL;
 8		new_node->data = data;
 9		return new_node;
10	}
11	int cmp_result = compare(root->data, data);
12	if (cmp_result < 0)
13		root->right = tree_insert(root->right, data, compare);
14	else if (cmp_result > 0)
15		root->left = tree_insert(root->left, data, compare);
16	return root;
17}

Nota

A função de procura tree_search e a função de inserção tree_insert têm ambas como parâmetro a função de comparação. Esta caraterística de interface permite utilizar funções de comparação diferentes. Compete ao utilizador garantir a compatibilidade das funções a fim de evitar inconsistências.

Como alternativas de desenho da interface, a função de comparação poderia ser intrínseca à própria árvore e definida no momento da sua criação/inicialização da árvore.

Eliminação da árvore

Quando os dados na árvore e a própria árvore não são mais necessários, deve-se libertar os recursos de memória associados. Essa libertação decorre em duas fases, a libertação dos elementos de dados e a eliminação da própria árvore. A primeira deve ser realizada no contexto de utilização, na Listagem 106, linha 27, são percorridas todas as posições da árvore, invocando em callback a função free_word. A segunda é realizada pela função tree_destroy (Listagem 106, linha 28).

tree_destroy

A função tree_destroy liberta a memória para o nó corrente, em cada instância de chamada, depois de ter percorrido recursivamente as sub-árvores esquerda e direita.

1void tree_destroy(struct tree_node *node) {
2	if (NULL == node)
3		return;
4	tree_destroy(node->left);
5	tree_destroy(node->right);
6	free(node);
7}