Dados gerais

Interface: AVLTree_In
Arquivos: avltree_in.h
Última atualização: 24/06/2005
Autor: Luiz Henrique Shigunov
Informações

Descrição
Estruturas
Funções

0x00 - Add - Adiciona um elemento
0x01 - Count - Retorna a quantidade de elementos na árvore
0x02 - Find - Encontra um elemento
0x03 - FindAdd - Tenta encontrar um elemento e se não encontrar adiciona-o
0x04 - FindClose - Tenta encontrar um elemento e se não encontrar retorna o mais próximo

0x05 - Free - Libera todos os elementos da árvore
0x06 - IsEmpty - Verifica se a estrutura está vazia
0x07 - Remove - Remove um elemento
0x08 - Walk - Percorre a árvore chamando uma função a cada nodo

Descrição

Esta página descreve a interface AVLTree_In que trata do acesso a um tipo de árvore AVL que utiliza uma estrutura exposta para permitir uma melhor utilização das estruturas, rapidez e economia de memória.

As funções desta interface que adicionam elementos na árvore, utilizam a função de comparação int (*cmpAddFunc)(const AVLTree_In_Node *addNode, const AVLTree_In_Node *node) definida na estrutura AVLTree_In_Tree.

Essa função compara o nodo addNode, que vai ser adicionado, com o nodo node que já está na árvore.

As demais funções utilizam a função de comparação int (*cmpFunc)(const void *info, const AVLTree_In_Node *node) que compara uma informação info com um nodo node da árvore.

Tanto uma como outra devem retornar:

Isso foi feito por causa da estrutura de dados usada. As informações estão no próprio nodo, logo abaixo da estrutura da árvore, por exemplo:

typedef struct {
    AVLTree_In_Node node;
    char *name;
    unsigned int ID;
} MinhaInfo;

Com isso, as funções que adicionam elementos na árvore, têm que utilizar uma função de comparação diferente da utilizada para procurar um nodo na árvore. Por exemplo, procurar name na estrutura acima.

A estrutura AVLTree_In_Tree deve ter os seguintes campos iniciados quando da iniciação da árvore por quem chama as funções da interface: root (iniciado com NULL), cmpFunc e cmpAddFunc.

Na hora de inserir um nodo, este também tem que ser iniciado com os dados a serem armazenados no nodo (name e ID no caso da estrutura MinhaInfo).

Estruturas

Esta interface usa a seguinte estrutura de dados para representar a raiz da árvore:

typedef struct {
    AVLTree_In_Node *root;
    int (*cmpFunc)(const void*,const AVLTree_In_Node*);
    int (*cmpAddFunc)(const AVLTree_In_Node*,const AVLTree_In_Node*);
    unsigned int count;
} AVLTree_In_Tree;

E a seguinte estrutura de dados para representar um nodo da árvore:

typedef struct AVLTree_In_Type_Node {
    struct AVLTree_In_Type_Node *left;
    struct AVLTree_In_Type_Node *right;
    signed char bal;
    char cache;
    char pad[2];
} AVLTree_In_Node;

0x00 - Add

Sintaxe

int AVLTree_In_Add(AVLTree_In_Tree *tree, AVLTree_In_Node *node);

Propriedades

Descrição

Esta função adiciona o nodo node na árvore tree.

Valor de retorno

0x01 - Count

Sintaxe

unsigned int AVLTree_In_Count(const AVLTree_In_Tree *tree);

Propriedades

Descrição

Esta função retorna a quantidade de elementos na árvore tree.

Valor de retorno

A quantidade de elementos.

0x02 - Find

Sintaxe

AVLTree_In_Node *AVLTree_In_Find(const AVLTree_In_Tree *tree, const void *info);

Propriedades

Descrição

Esta função procura a informação info na árvore tree.

Valor de retorno

Utilize as macros IS_PTR_ERROR e PTR_TO_ERROR para saber se ocorreu erro e para obter o erro respectivamente.

0x03 - FindAdd

Sintaxe

AVLTree_In_Node *AVLTree_In_FindAdd(AVLTree_In_Tree *tree, AVLTree_In_Node *node);

Propriedades

Descrição

Esta função procura o nodo node na árvore tree e se não encontrar adiciona o elemento na árvore.

Valor de retorno

Utilize as macros IS_PTR_ERROR e PTR_TO_ERROR para saber se ocorreu erro e para obter o erro respectivamente.

0x04 - FindClose

Sintaxe

AVLTree_In_Node *AVLTree_In_FindClose(const AVLTree_In_Tree *tree, const void *info);

Propriedades

Descrição

Esta função procura a informação info na árvore tree e se não encontrar retorna o mais próximo.

A função só falha se a árvore estiver vazia.

Valor de retorno

Utilize as macros IS_PTR_ERROR e PTR_TO_ERROR para saber se ocorreu erro e para obter o erro respectivamente.

0x05 - Free

Sintaxe

int AVLTree_In_Free(AVLTree_In_Tree *tree, void (*freeFunc)(AVLTree_In_Node *node));

Propriedades

Descrição

Esta função percorre a árvore tree e, para cada elemento, chama a função freeFunc para liberar o nodo node.

Valor de retorno

0x06 - IsEmpty

Sintaxe

int AVLTree_In_IsEmpty(const AVLTree_In_Tree *tree);

Propriedades

Descrição

Esta função verifica se a árvore tree está vazia.

Valor de retorno

0x07 - Remove

Sintaxe

AVLTree_In_Node *AVLTree_In_Remove(AVLTree_In_Tree *tree, const void *info);

Propriedades

Descrição

Esta função remove o elemento info da árvore tree.

Esta função apenas remove o elemento da árvore, não libera a sua memória.

Valor de retorno

Utilize as macros IS_PTR_ERROR e PTR_TO_ERROR para saber se ocorreu erro e para obter o erro respectivamente.

0x08 - Walk

Sintaxe

int AVLTree_In_Walk(const AVLTree_In_Tree *tree, void (*walkFunc)(AVLTree_In_Node *info, void *param1, void *param2), void *param1, void *param2);

Propriedades

Descrição

Esta função percorre a árvore tree e chama para cada nodo a função walkFunc passando como parâmetro o nodo info, param1 e param2.

Valor de retorno