Biblioteca Arvore23

Descrição

Esta biblioteca de rotinas em C implementa uma coleção ordenada de objetos, apontados por (void *), disponibilizados em uma árvore B balanceada de ordem 3 (isto é, até 2 nós e três filhos). As funcionalidades disponibilizadas lembram a classe TreeMap da linguagem de programação Java. O custo de todas as operações que dependem da altura da árvore será O(lg n), onde lg n é o logaritmo de n na base 2, e n a quantidade de elementos presentes na árvore. A altura da árvore é definida como a quantidade de passos para se chegar a um nó no último nível. Dessa forma, nós no último nível (folha) tem altura 0, e uma árvore vazia tem altura -1 por definição. A altura máxima da árvore sempre é menor que lg(n + 1). Como cada nó pode ter dois elementos, o número máximo de comparações para encontrar um elemento específico será 2 * lg(n) + O(1). Na prática, a quantidade média de comparações para acesso a um elemento da árvore é muito próxima de lg(n). Existem outras bibliotecas conhecidas que implementam estruturas de árvores balanceadas, sendo inclusives mais completas que esta. Resolvi implementar esta porque queria algo realmente livre, em português, e que pudesse ser compilado facilmente simplesmente com "make" em vez de ter de tentar entender longos documentos CWEB em que sequer aparece o código fonte pronto para ser compilado.

Instalação

Código fonte: Arvore23.zip Para compilar a biblioteca: No Windows, executar "make all". No linux, executar "make all -f Makefile.linux". Em outros sistemas, adaptar o arquivo Makefile se necessário, ou compilar manualmente cada um dos arquivos .c para um .o correspondente, e no final gerar uma biblioteca libArvore23.a usando o programa ar ou equivalente. Após a compilação, copiar libArvore23.a para o diretório de bibliotecas (por exemplo, /usr/lib no linux, ou C:\MinGW\lib no Windows), e o arquivo Arvore23.h para o diretório de arquivos de cabeçalho (por exemplo, /usr/include no linux, ou C:\MinGW\include no Windows). Versões pré-compiladas: Windows (MinGW) Linux

Desinstalação

Para desinstalar, basta apagar todo o diretório Arvore23 e os arquivos libArvore23.a e Arvore23.h.

Tipos de dados

O tipo de dado NODE_23_T é o tipo de cada nó da árvore. Os valores que contém as chaves de busca estão apontados em v[0..1], e os nós filhos em f[0..2]. A subárvore em f[0] contém elementos menores que v[0], a subárvore em f[1] contém elementos entre v[0] e v[1], e a subárvore em f[2] contém elementos maiores que v[1]. Caso não haja elemento em v[1], também não haverá f[2].

typedef struct ST_NODE_23 { const void *v[2]; struct ST_NODE_23 *f[3]; } NODE_23_T;

O tipo de dado ARVORE_23_T é um apontador para uma árvore 23 criada com Arvore23Criacao().

typedef struct ST_TREE_23_T { NODE_23_T *tree; /* a árvore em si, a partir de seu nó raiz */ int (*cmp)(const void *, const void *); /* função de comparação de elementos */ unsigned long n; /* quantidade atual de elementos na árvore */ } TREE_23_ST; typedef TREE_23_ST *ARVORE_23_T;

Comparações de valores e registros

A árvore armazena apontadores para registros que podem ser dados primitivos ou estruturas complexas. Cada registro é ordenado segundo uma chave, segundo uma ordem definida por uma função de comparação que deverá ser fornecida no momento da criação da árvore (ver função Arvore23Criacao). Para evitar complicações desnecessárias na ordenação de tipos simples de dados, a chave de ordenação é armazenada no próprio registro, de forma a poder mencionar simplesmente a ordem entre registros, e não apenas suas chaves de busca. A desvantagem dessa abordagem é a necessidade de se criar um registro de mesmo tipo de dado a ser buscado, para armazenar apenas a chave a ser utilizada na busca. A linguagem Java cuida dessa questão implementando classes distintas, TreeMap (chave + registro) ou TreeSet (chave é o próprio registro).

Funções

ARVORE_23_T Arvore23Criacao (int (cmp)(const void , const void *));

Devolde uma Árvore 23 vazia que usa comparador cmp. O comparador deve devolver os seguintes valores conforme a relação entre as os valores (na verdade, suas chaves de busca), conforme abaixo: int cmp (const void *e1, const void *e2) < 0 se e1 < e2 = 0 se e1 = e2 > 0 se e1 > e2 Exemplo:

struct st_registro { long id; char nome[1000]; };

Se elemento é do tipo struct st_registro acima, a função de comparação pode ser:

int Comparacao (const void *e1, const void *e2) { long v1, v2; v1 = ((struct st_registro *) e1)->id; v2 = ((struct st_registro *) e2)->id; if (v1 < v2) return -1; if (v1 == v2) return 0; return 1; }

Para criar a árvore:

ARVORE_23_T arvore23; arvore23 = Arvore23Criacao (Comparacao); if (arvore23 == NULL) { fprintf (stderr, "Erro ao criar arvore.\n"); } else { printf ("Arvore 23 criada com sucesso.\n"); }

unsigned long Arvore23Tamanho (ARVORE_23_T arvore23);

Devolve a quantidade de nós atual da árvore. É o mesmo que arvore23->n. Se arvore23 for NULL, devolve 0. Tempo de execução: O(1)

int Arvore23Altura (ARVORE_23_T arvore23);

Devolve a altura atual de arvore23. Se arvore23 for NULL, devolve -1. Árvore vazia tem altura -1. Nós folha tem altura 0, ou seja, a altura é a quantidade de níveis menos 1. Obs.: Esta função não faz uso da função arvore23->cmp. Tempo de execução: O(lg(n)), onde n é a quantidade de elementos na árvore.

const void Arvore23Insere (ARVORE_23_T arvore23, const void elemento);

Insere elemento em arvore23. Se um elemento já existir (isto é, mesma chave de busca), haverá substituição e o elemento anterior será devolvido pela função. Caso não haja elemento de mesma chave na árvore, a função devolverá NULL após a inserção. Tempo de execução: O(lg(n)), onde n é a quantidade de elementos na árvore. Exemplo:

struct st_registro registros[100]; ARVORE_23_T arvore23 = Arvore23Criacao (ComparacaoRegistros); for (i = 0; i < 100; i++) Arvore23Insere (arvore23, &registros[i]);

const void Arvore23Remove (ARVORE_23_T arvore23, const void elemento);

Remove de arvore23 elemento que contenha mesma chave do parâmetro elemento. A função devolve apontador para o elemento removido, ou NULL se não existia na árvore. Tempo de execução: O(lg(n)), onde n é a quantidade de elementos na árvore. Exemplo:

struct st_registro reg; struct st_registro *removido; reg.id = 123; removido = (struct st_registro *) Arvore23Remove (arvore23, &reg); if (removido != NULL) { printf ("Removido elemento de id %ld e nome %s\n", removido->id, removido->nome); } else { printf ("Nao havia elemento com chave %ld\n", reg.id); }

int Arvore23Contem (ARVORE_23_T arvore23, const void *elemento);

Verifica se existe elemento em arvore23 com chave igual ao elemento fornecido como parâmetro. Devolve 1 caso exista, e 0 caso contrário. Tempo de execução: O(lg(n)), onde n é a quantidade de elementos na árvore. Exemplo:

struct st_registro reg; reg.id = 123; if (Arvore23Contem (arvore23, &reg)) { printf ("Ha elemento com chave %ld\n", reg.id); } else { printf ("Nao ha elemento com chave %ld\n", reg.id); }

const void *Arvore23RecuperaPrimeiro (ARVORE_23_T arvore23);

Funções para recuperação do primeiro elemento de arvore23. Esta função não faz chamada à função de comparação arvore23->cmp. Tempo de execução: O(lg(n)), onde n é a quantidade de elementos na árvore. Exemplo:

struct st_registro *reg; reg = (struct st_registro *) Arvore23RecuperaPrimeiro (arvore23); printf ("Primeiro id = %ld\n", reg->id);

const void *Arvore23RecuperaUltimo (ARVORE_23_T arvore23);

Similar a Arvore23RecuperaPrimeiro, porém recupera o último elemento.

const void Arvore23Recupera (ARVORE_23_T arvore23, const void el);

Recupera na arvore23 elemento com chave igual ao do elemento fornecido. Se não houver, devolve NULL. Tempo de execução: O(lg(n)), onde n é a quantidade de elementos na árvore. Exemplo:

struct st_registro reg, *recuperado; reg.id = 123; recuperado = (struct st_registro *) Arvore23Recupera (arvore23, &reg); if (recuperado != NULL) { printf ("Recuperado Id = %ld, nome = %s\n", recuperado->id, recuperado->nome); } else { printf ("Nao ha elemento com chave %ld\n", reg.id); }

const void Arvore23RecuperaAnterior (ARVORE_23_T arvore23, const void elemento);

const void Arvore23RecuperaProximo (ARVORE_23_T arvore23, const void elemento);

const void Arvore23RecuperaChao (ARVORE_23_T arvore23, const void elemento);

const void Arvore23RecuperaTeto (ARVORE_23_T arvore23, const void elemento);

As funções de recuperação acima recuperam elemento da arvore23 com base no elemento fornecido, considerando as seguintes definições: - Anterior: maior elemento extritamente menor que o elemento fornecido. - Próximo: menor elemento extritamente maior que o elemento fornecido. - Chão: maior elemento menor ou igual ao elemento fornecido. - Teto: menor elemento maior ou igual ao elemento fornecido. Caso não exista elemento nas condições acima, é devolvido NULL. Tempo de execução: O(lg(n)), onde n é a quantidade de elementos na árvore. Exemplo:

struct st_registro reg, *recuperado; reg.id = 123; recuperado = (struct st_registro *) Arvore23RecuperaProximo (arvore23, &reg); if (recuperado != NULL) { printf ("Apos id = %ld, foi recuperado id = %ld, nome = %s\n", reg.id, recuperado->id, recuperado->nome); } else { printf ("Nao ha elemento com chave maior que %ld\n", reg.id); }

long Arvore23GeraLista (ARVORE_23_T arvore23, const void *lista[]);

Grava uma lista de elementos em lista[], que deve conter espaço suficiente para todos os elementos da árvore. Devolve a quantidade de elementos armazenada, ou -1 em caso de erro. Tempo de execução: Θ(n), onde n é a quantidade de elementos na árvore. Exemplo:

const void **lista; long ret; lista = (const void **) malloc (arvore23->n * sizeof (const void *)); ret = Arvore23GeraLista (arvore23, lista); if (ret >= 0) { for (i = 0; i < ret; i++) { printf ("%ld %s\n", ((struct st_registro *)lista[i])->id, ((struct st_registro *)lista[i])->nome); } } else printf ("Erro em Arvore23GeraLista\n");

void Arvore23Apagar (ARVORE_23_T arvore23);

Apaga todos os elementos da árvore, deixando-a vazia. A árvore continua alocada e pronta para novas inserções. Após excução, arvore23->n valerá 0, e arvore23->tree valerá NULL. Tempo de execução: Θ(n), onde n é a quantidade de elementos na árvore.

int Arvore23Valida (ARVORE_23_T arvore23);

Esta função confere a consistência da arvore23. A única forma de tornar a árvore inconsistente é alterar externamente a chave de acesso de algum nó já inserido na árvore. Nestes casos, a função poderá ajudar a identificar problema no programa fazendo uso da biblioteca. A função devolve 1 se a árvore for válida, e 0 caso contrário. Tempo de execução: Θ(n), onde n é a quantidade de elementos na árvore. Exemplo:

struct st_registro *reg; reg = (struct st_registro *) malloc (sizeof (struct st_registro)); reg->id = 100; strcpy (reg->nome, "Fulano"); Arvore23Insere (arvore23, reg); reg = (struct st_registro *) malloc (sizeof (struct st_registro)); reg->id = 200; strcpy (reg->nome, "Beltrano"); Arvore23Insere (arvore23, reg); reg->id = 50; /* Esta alteracao tornará a árvore inválida. Nunca se deve alterar a chave de acesso de registros já inseridos. */ if (! Arvore23Valida (arvore23)) { fprintf (stderr, "Erro: a árvore está inconsistente!\n"); exit (1); }

void Arvore23Destroi (ARVORE_23_T arvore23);

Apaga todos os elementos da árvore, e destrói a estrutura da árvore via desalocação de memória. A árvore destruída só poderá ser novamente usada após nova chamada a Arvore23Criacao(). Tempo de execução: Θ(n), onde n é a quantidade de elementos na árvore.

void Arvore23DestroiDesalocaDados (ARVORE_23_T arvore23);

Apaga todos os elementos da árvore, e destrói a estrutura da árvore via desalocação de memória. Além disso, desaloca cada elemento inserido na árvore usando chamada a free(). Por isso esta função só pode ser usada quando a alocação dos elementos foi feita dinamicamente com malloc(). A árvore destruída só poderá ser novamente usada após nova chamada a Arvore23Criacao(). Tempo de execução: Θ(n), onde n é a quantidade de elementos na árvore.

Exemplo de uso

Neste exemplo, há a utilização das funções descritas acima, em um programa interativo em que é possível verificar o conteúdo da árvore.

Licença de uso

As funcionalidades desta biblioteca podem ser utilizadas em quaisquer programas, incluindo alterações e utilização em softwares comerciais, desde que haja concordância com a ausência de garantias descrita abaixo: Esta biblioteca é distribuída originalmente sem custo, portanto não há qualquer tipo de garantia: AUSÊNCIA DE GARANTIAS UMA VEZ QUE O PROGRAMA É LICENCIADO SEM ÔNUS, NÃO HÁ QUALQUER GARANTIA PARA O PROGRAMA. EXCETO QUANDO EXPRESSADO DE FORMA ESCRITA, OS DETENTORES DOS DIREITOS AUTORAIS E/OU TERCEIROS DISPONIBILIZAM O PROGRAMA "NO ESTADO", SEM QUALQUER TIPO DE GARANTIAS, EXPRESSAS OU IMPLÍCITAS, INCLUINDO, MAS NÃO LIMITADO A, AS GARANTIAS IMPLÍCITAS DE COMERCIALIZAÇÃO E AS DE ADEQUAÇÃO A QUALQUER PROPÓSITO. O RISCO TOTAL COM A QUALIDADE E DESEMPENHO DO PROGRAMA É SEU. SE O PROGRAMA SE MOSTRAR DEFEITUOSO, VOCÊ ASSUME OS CUSTOS DE TODAS AS MANUTENÇÕES, REPAROS E CORREÇÕES. EM NENHUMA OCASIÃO, OS DETENTORES DOS DIREITOS AUTORAIS, OU QUALQUER OUTRA PARTE QUE POSSA MODIFICAR E/OU REDISTRIBUIR O PROGRAMA CONFORME PERMITIDO ACIMA, SERÃO RESPONSABILIZADOS POR VOCÊ POR DANOS, INCLUINDO QUALQUER DANO EM GERAL, ESPECIAL, ACIDENTAL OU CONSEQUENTE, RESULTANTES DO USO OU INCAPACIDADE DE USO DO PROGRAMA (INCLUINDO, MAS NÃO LIMITADO A, A PERDA DE DADOS OU DADOS TORNADOS INCORRETOS, OU PERDAS SOFRIDAS POR VOCÊ OU POR OUTRAS PARTES, OU FALHAS DO PROGRAMA AO OPERAR COM QUALQUER OUTRO PROGRAMA), MESMO QUE TAL DETENTOR OU PARTE TENHAM SIDO AVISADOS DA POSSIBILIDADE DE TAIS DANOS.

Contato

Em caso de problemas, dúvidas ou sugestões, entrar em contato com "José Eduardo G. Carvalho" E-mail