Jump to content
Sign in to follow this  
AprendizZ

Factor de equilibrio de uma árvore AVL.

Recommended Posts

AprendizZ

Poderão esclarecer-me o que é o factor de equilíbrio de uma árvore AVL. E como se efectua o seu calculo.

Obrigado.

Share this post


Link to post
Share on other sites
pedrosorio

http://en.wikipedia.org/wiki/AVL_tree

"The balance factor of a node is the height of its left subtree minus the height of its right subtree (sometimes opposite) and a node with balance factor 1, 0, or −1 is considered balanced."

O factor de equilíbrio de um nó é a altura da sua sub-árvore esquerda menos a altura da sua sub-árvore direita. Um nó com factor de equilíbrio de 1, 0 ou -1 considera-se equilibrado.

Edit: Aqui estava disparate - não sei o que é o factor de equilíbrio de uma árvore AVL, apenas encontro a definição para cada nó.

Penso que com a definição de factor de equilíbrio não deves ter problemas em calculá-lo para um dado nó. Se calhar devias ter colocado esta pergunta em Algoritmia e Lógica, a menos que tenhas dúvidas específicas sobre C.


Não respondo a dúvidas por mensagem.

Share this post


Link to post
Share on other sites
AprendizZ

A dúvida é mesmo em C.

Ou seja o factor de equilíbrio de uma árvora será o máximo dos factores da cada nó, não?

(Fe = Altura da Esquerda - Altura da Direita).

Share this post


Link to post
Share on other sites
pedrosorio

A dúvida é mesmo em C.

Ou seja o factor de equilíbrio de uma árvora será o máximo dos factores da cada nó, não?

(Fe = Altura da Esquerda - Altura da Direita).

Eu diria não o máximo, mas sim o factor de equilíbrio com o maior valor absoluto. (I.e. se tiveres uma árvore com nós que têm F.e. -2,-1,0,1 o factor de equilíbrio seria -2).

Se a dúvida é mesmo em C, isso significa que não tens dúvidas no algoritmo (i.e. sabes um algoritmo para calcular a altura de uma árvore, e aplicando esse algoritmo às árvores esquerda e direita de um nó consegues calcular o seu Fe), qual é a tua dúvida na implementação?


Não respondo a dúvidas por mensagem.

Share this post


Link to post
Share on other sites
AprendizZ

Já consegui. Aqui fica uma possível solução:

int equilibrio (Tree t)
{
int balanco;
balanco = abs(tree_altura(t->child[0]) - tree_altura(t->child[1]));
return balanco;
}

int fator_eq (Tree t)
{
int eq_pai, eq_filhos, result;
if (t != NULL)
{
	eq_pai = equilibrio(t);
	eq_filhos = max(fator_eq(t->child[0]),fator_eq(t->child[1]));
	result = max(eq_pai,eq_filhos);
}
else
	result = 0;
return result;
}

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
Sign in to follow this  

×
×
  • Create New...

Important Information

By using this site you accept our Terms of Use and Privacy Policy. We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.