|
Interface: AVLTree_In Arquivos: avltree_in.h Última atualização: 24/06/2005 Autor: Luiz Henrique Shigunov |
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 |
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).
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;
int AVLTree_In_Add(AVLTree_In_Tree *tree, AVLTree_In_Node *node);
Esta função adiciona o nodo node na árvore tree.
unsigned int AVLTree_In_Count(const AVLTree_In_Tree *tree);
Esta função retorna a quantidade de elementos na árvore tree.
AVLTree_In_Node *AVLTree_In_Find(const AVLTree_In_Tree *tree, const void *info);
Esta função procura a informação info na árvore tree.
Utilize as macros IS_PTR_ERROR e PTR_TO_ERROR para saber se ocorreu erro e para obter o erro respectivamente.
AVLTree_In_Node *AVLTree_In_FindAdd(AVLTree_In_Tree *tree, AVLTree_In_Node *node);
Esta função procura o nodo node na árvore tree e se não encontrar adiciona o elemento na árvore.
Utilize as macros IS_PTR_ERROR e PTR_TO_ERROR para saber se ocorreu erro e para obter o erro respectivamente.
AVLTree_In_Node *AVLTree_In_FindClose(const AVLTree_In_Tree *tree, const void *info);
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.
Utilize as macros IS_PTR_ERROR e PTR_TO_ERROR para saber se ocorreu erro e para obter o erro respectivamente.
int AVLTree_In_Free(AVLTree_In_Tree *tree, void (*freeFunc)(AVLTree_In_Node *node));
Esta função percorre a árvore tree e, para cada elemento, chama a função freeFunc para liberar o nodo node.
int AVLTree_In_IsEmpty(const AVLTree_In_Tree *tree);
Esta função verifica se a árvore tree está vazia.
AVLTree_In_Node *AVLTree_In_Remove(AVLTree_In_Tree *tree, const void *info);
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.
Utilize as macros IS_PTR_ERROR e PTR_TO_ERROR para saber se ocorreu erro e para obter o erro respectivamente.
int AVLTree_In_Walk(const AVLTree_In_Tree *tree, void (*walkFunc)(AVLTree_In_Node *info, void *param1, void *param2), void *param1, void *param2);
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.