Referência ao Ficheiro treemap.h

Descrição Detalhada

Implementação de uma árvore binária de pesquisa equilibrada.

Esta biblioteca disponibiliza um conjunto de funções que permitem manipular uma árvore binária de pesquisa equilibrada.

Na criação de uma árvore é necessário especificar a função que compara as chaves.

int keyComp(void* key1,void* key2)
(usada pelas funções treeInsert, treeRemove e treeGet); deve devolver um valor menor do que 0 se key1 for menor do que key2, um valor maior do que 0 se key1 for maior do que key2 e 0 caso contrário; pode ser alterada através da função treeSetKComp. 

int keyComp(void* key1,void* key2)
{
  if(key1&&key2) return strcmp((char*)key1,(char*)key2);
  else return 0;
}

Autor:
Rui Carlos A. Gonçalves <rcgoncalves.pt@gmail.com>
Versão:
2.0.2
Data:
02/2009

Definido no ficheiro treemap.h.

Ir para o código fonte deste ficheiro.

Estruturas de Dados

struct  STreeNode
 Estrutura do nodo da árvore. Mais...
struct  STreeMap
 Estrutura de uma árvore. Mais...

Definições de Tipos

typedef STreeNode * TreeNode
 Definição do apontador para os nodos da árvore.
typedef STreeMap * TreeMap
 Definição da árvore.

Enumerações

enum  BFactor { L, E, R }
 Tipo que indica para onde uma árvore está balanceada.

Funções

TreeMap newTree (int(*keyComp)(void *, void *))
 Cria uma árvore.
int treeSetKComp (TreeMap tree, int(*keyComp)(void *, void *))
 Altera a função que compara as chaves de uma árvore.
void treeDelete (TreeMap tree)
 Elimina uma árvore.
int treeInsert (TreeMap tree, void *key, void *value, int replace)
 Insere um par chave/valor numa árvore.
int treeRemove (TreeMap tree, void *key, void **value, void(*del)(void *))
 Remove um elemento de uma árvore.
int treeGet (TreeMap tree, void *key, void **value)
 Procura um elemento numa árvore.
int treeIsAVL (TreeMap tree)
 Verifica se uma árvore está equilibrada.
int treeHeight (TreeMap tree)
 Determina a altura de uma árvore.
int treeSize (TreeMap tree)
 Determina o número de elementos de uma árvore.
int treeInOrder (TreeMap tree, void(*fun)(void *, void *))
 Efectua uma travessia In-Order de uma árvore.
int treePreOrder (TreeMap tree, void(*fun)(void *, void *))
 Efectua uma travessia Pre-Order de uma árvore.
int treePosOrder (TreeMap tree, void(*fun)(void *, void *))
 Efectua uma travessia Pos-Order de uma árvore.
Iterator treeKeys (TreeMap tree)
 Cria um iterador a partir das chaves de uma árvore.
Iterator treeValues (TreeMap tree)
 Cria um iterador a partir dos valores associados às chaves de uma árvore.

Documentação das Funções

TreeMap newTree ( int(*)(void *, void *)  keyComp  ) 

Cria uma árvore.

Se não for possível criar a árvore devolve NULL. Tem que ser especificada a função que compara chaves. Esta função pode ser alterada a qualquer momento, utilizando a função treeSetKComp.

(Ver descrição das funções)

Parâmetros:
keyComp função que compara duas chaves.
Retorna:
árvore inicializada ou NULL.

Definido na linha 281 do ficheiro treemap.c.

void treeDelete ( TreeMap  tree  ) 

Elimina uma árvore.

Atenção:
apenas liberta a memória referente à estrutura da árvore; não liberta o espaço ocupado pelos elementos nela contidos.
Parâmetros:
tree árvore.

Definido na linha 329 do ficheiro treemap.c.

int treeGet ( TreeMap  tree,
void *  key,
void **  value 
)

Procura um elemento numa árvore.

Devolve o valor associado a uma chave, se esta existir. Se a chave não existir é colocado o valor NULL em value.

Atenção:
esta função coloca em value o endereço do valor pretendido; depois de executar esta função é aconselhável fazer uma cópia do mesmo e passar a trabalhar com a cópia para que não haja problemas de partilha de referências.
Parâmetros:
tree árvore.
key chave que procuramos.
value endereço onde é colocado o resultado.
Retorna:
0 se o elemento existir;
1 se o elemento não existir.

Definido na linha 591 do ficheiro treemap.c.

int treeHeight ( TreeMap  tree  ) 

Determina a altura de uma árvore.

Parâmetros:
tree árvore.
Retorna:
altura da árvore.

Definido na linha 671 do ficheiro treemap.c.

int treeInOrder ( TreeMap  tree,
void(*)(void *, void *)  fun 
)

Efectua uma travessia In-Order de uma árvore.

Aplica a função fun a todos os elementos da árvore.
A função fun tem que ser do tipo: void fun(void*,void*).

Parâmetros:
tree árvore.
fun função a ser aplicada.
Retorna:
0 se a árvore não estiver vazia;
1 se a árvore estiver vazia.

Definido na linha 703 do ficheiro treemap.c.

int treeInsert ( TreeMap  tree,
void *  key,
void *  value,
int  replace 
)

Insere um par chave/valor numa árvore.

Caso a chave já exista, a variável replace determina se o valor antigo é ou não substituído (caso seja não há substituição, caso tenha outro valor o novo elemento é inserido).

Parâmetros:
tree árvore.
key chave.
value valor associado à chave.
replace variável que determina se os elementos já existentes são ou não substituídos.
Retorna:
0 se o elemento for inserido;
1 se a árvore já possuia a chave indicada;
2 caso não seja possível alocar memória para o novo elemento.

Definido na linha 435 do ficheiro treemap.c.

int treeIsAVL ( TreeMap  tree  ) 

Verifica se uma árvore está equilibrada.

Considera-se que a árvore está equilibrada se a diferença entre a altura das subárvores esquerda e direita (em todos os nodos) não for superior a 1.

Parâmetros:
tree árvore.
Retorna:
0 se a árvore não estiver equilibrada;
1 caso contrário.

Definido na linha 641 do ficheiro treemap.c.

Iterator treeKeys ( TreeMap  tree  ) 

Cria um iterador a partir das chaves de uma árvore.

Faz uma travessia In-Order da árvore e "coloca" as referências para as chaves num iterador. Se ocorrer algum erro a função devolve NULL.

Ver Também:
Iterator
Parâmetros:
tree árvore.
Retorna:
iterador criado ou NULL.

Definido na linha 799 do ficheiro treemap.c.

int treePosOrder ( TreeMap  tree,
void(*)(void *, void *)  fun 
)

Efectua uma travessia Pos-Order de uma árvore.

Aplica a função fun a todos os elementos da árvore.
A função fun tem que ser do tipo: void fun(void*,void*).

Parâmetros:
tree árvore.
fun função a ser aplicada.
Retorna:
0 se a árvore não estiver vazia;
1 se a árvore estiver vazia.

Definido na linha 763 do ficheiro treemap.c.

int treePreOrder ( TreeMap  tree,
void(*)(void *, void *)  fun 
)

Efectua uma travessia Pre-Order de uma árvore.

Aplica a função fun a todos os elementos da árvore.
A função fun tem que ser do tipo: void fun(void*,void*).

Parâmetros:
tree árvore.
fun função a ser aplicada.
Retorna:
0 se a árvore não estiver vazia;
1 se a árvore estiver vazia.

Definido na linha 733 do ficheiro treemap.c.

int treeRemove ( TreeMap  tree,
void *  key,
void **  value,
void(*)(void *)  del 
)

Remove um elemento de uma árvore.

Permite devolver o valor removido, caso o valor de value seja diferente de NULL. Se a chave não existir ou o elemento não for removido é colocado o valor NULL em value.

Atenção:
esta função não liberta o espaço ocupado pelo valor associado à chave; já o espaço ocupado pela chave removida, se del for diferente de NULL, será libertado.
Parâmetros:
tree árvore.
key chave que queremos remover.
value endereço onde é colocado o elemento removido (ou NULL).
del função que elimina uma chave (ou NULL).
Retorna:
0 se o elemento for removido;
1 se a chave não existir;

Definido na linha 576 do ficheiro treemap.c.

int treeSetKComp ( TreeMap  tree,
int(*)(void *, void *)  keyComp 
)

Altera a função que compara as chaves de uma árvore.

O valor de keyComp não pode ser NULL.

Parâmetros:
tree árvore.
keyComp nova função.
Retorna:
1 se keyComp for NULL (não é efectuada qualquer alteração);
0 caso contrário.

Definido na linha 300 do ficheiro treemap.c.

int treeSize ( TreeMap  tree  ) 

Determina o número de elementos de uma árvore.

Devolve o valor do campo size da árvore.

Parâmetros:
tree árvore.
Retorna:
número de elementos da árvore.

Definido na linha 679 do ficheiro treemap.c.

Iterator treeValues ( TreeMap  tree  ) 

Cria um iterador a partir dos valores associados às chaves de uma árvore.

Faz uma travessia In-Order da árvore e "coloca" as referências para os "valores" num iterador. Se ocorrer algum erro a função devolve NULL.

Ver Também:
Iterator
Parâmetros:
tree árvore.
Retorna:
iterador criado ou NULL.

Definido na linha 838 do ficheiro treemap.c.

LibRCG © 2004-2009   Rui Carlos A. Gonçalves