Referência ao Ficheiro treemap.c

Efectua as rotações necessária a uma árvore que está balanceada para a esquerda.

Esta função destina-se a (sub)árvores cujo desiquilíbrio resulte do processo de inserção de um novo elemento.

Parâmetros:

tree

raiz da (sub)árvore que vamos equilibrar.

Retorna:

árvore equilibrada.

Definido na linha 76 do ficheiro treemap.c.

Efectua uma rotação à esquerda.

Parâmetros:

tree

raiz da (sub)árvore que vamos rodar.

Retorna:

nova árvore.

Definido na linha 19 do ficheiro treemap.c.

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.

Efectua as rotações necessária a uma árvore que está balanceada para a direita.

Esta função destina-se a (sub)árvores cujo desiquilíbrio resulte do processo de inserção de um novo elemento.

Parâmetros:

tree

raiz da (sub)árvore que vamos equilibrar.

Retorna:

árvore equilibrada.

Definido na linha 126 do ficheiro treemap.c.

Efectua uma rotação à direita.

Parâmetros:

tree

raiz da (sub)árvore que vamos rodar.

Retorna:

nova árvore.

Definido na linha 46 do ficheiro treemap.c.

Efectua as rotações necessária a uma árvore que está balanceada para a esquerda.

Esta função destina-se a (sub)árvores cujo desiquilíbrio resulte do processo de remoção de um novo elemento.

Parâmetros:

	tree	raiz da (sub)árvore que vamos equilibrar.
	h	indica se a altura da árvore foi alterada ou não.

Retorna:

árvore equilibrada.

Definido na linha 177 do ficheiro treemap.c.

Efectua as rotações necessária a uma árvore que está balanceada para a direita.

Esta função destina-se a (sub)árvores cujo desiquilíbrio resulte do processo de remoção de um novo elemento.

Parâmetros:

	tree	raiz da (sub)árvore que vamos equilibrar.
	h	indica se a altura da árvore foi ou não alterada.

Retorna:

árvore equilibrada.

Definido na linha 226 do ficheiro treemap.c.

Elimina um nodo de uma (sub)árvore e todos os seus descendentes.

Parâmetros:

tree

raiz da árvore.

Definido na linha 317 do ficheiro treemap.c.

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.

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.

Determina a altura de uma árvore.

Parâmetros:

tree

árvore.

Retorna:

altura da árvore.

Definido na linha 671 do ficheiro treemap.c.

Determina a altura de uma (sub)árvore.

Parâmetros:

tree

árvore.

Retorna:

altura da árvore.

Definido na linha 655 do ficheiro treemap.c.

Função auxiliar da função que efectua uma travessia In-Order da árvore.

Parâmetros:

	tree	árvore.
	fun	função que é aplicada aos elementos da árvore.

Definido na linha 691 do ficheiro treemap.c.

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.

Função auxiliar da função de inserção.

Parâmetros:

	tree	árvore onde vamos fazer a inserção.
	key	chave do elemento a inserir.
	val	valor associado à chave.
	replace	variável que indica se valores já existentes são ou não substituídos.
	h	variável que permite saber se a inserção aumentou o tamanho da árvore.
	comp	função que permite comparar duas chaves.

Retorna:

nova árvore.

Definido na linha 351 do ficheiro treemap.c.

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.

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.

Verifica se uma (sub)árvore está equilibrada na raiz e se todas as suas subárvores também estão.

Parâmetros:

tree

árvore.

Retorna:

-1 se não está equilibrada;
altura da árvore caso contrário.

Definido na linha 623 do ficheiro treemap.c.

Percorre uma (sub)árvore e adiciona as chaves a um iterador.

Parâmetros:

	tree	árvore.
	it	iterador onde são colocadas as chaves.

Retorna:

1 se ocorrer algum erro;
0 caso contrário.

Definido na linha 784 do ficheiro treemap.c.

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.

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.

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.

Função auxiliar da função que efectua uma travessia Pre-Order da árvore.

Parâmetros:

	tree	árvore.
	fun	função que é aplicada aos elementos da árvore.

Definido na linha 721 do ficheiro treemap.c.

Função auxiliar da função que efectua uma travessia Pos-Order da árvore.

Parâmetros:

	tree	árvore.
	fun	função que é aplicada aos elementos da árvore.

Definido na linha 751 do ficheiro treemap.c.

Função auxiliar da função de remoção.

Parâmetros:

	tree	árvore onde vamos fazer a inserção.
	key	chave do elemento a inserir.
	value	local onde será colocada a informação associada ao elemento removido.
	del	função que elimina um chave.
	h	variável que permite saber se a remoção aumentou o tamanho da árvore.
	comp	função que permite comparar duas chaves.

Retorna:

nova árvore.

Definido na linha 464 do ficheiro treemap.c.

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.

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.

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.

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.

Percorre uma (sub)árvore e adiciona os valores associados às chaves a um iterador.

Parâmetros:

	tree	árvore.
	it	iterador onde são colocadas os valores associados às chaves.

Retorna:

1 se ocorrer algum erro;
0 caso contrário.

Definido na linha 823 do ficheiro treemap.c.

Determina o nodo com maior chave na subárvores esquerda da árvore dada.

Parâmetros:

tree

árvore.

Retorna:

maior elemento da esquerda.

Definido na linha 271 do ficheiro treemap.c.