Arvores AVL

[VictorCacciari 42]

Boas pessoal, estou desenvolvendo um template para uma arvore AVL.

Mas estou com algumas dúvidas em como checar desequilibrios, para efetuar as roações.

 

A estrutura que estou utilizando para o template é:

template<class T>
class AVLTree
{
	public:	
		struct _AVLNODE
		{
			T value;
			//int _height;
			struct _AVLNODE* right;
			struct _AVLNODE* left;
		};
//... resto da classe...

Agora vem o problema:

É preferivel manter a altura de cada vertticie (ou nó, se você preferir) na propria estrutura, e conforme percorro a arvore para adicionar um novo verticie eu atualizo as alturas, e então checo por uma diferença >= 2 nas alturas e vejo se é preciso rodar, ou não.

 

Ou eu computo todas as alturas on-the-fly, ao adicionar um nó...

Esse segundo método é de maior complexidade, mas economiza 4 bytes em cada nó...

 

Qual optar?

[omar.pessoa 1]

Boas pessoal, estou desenvolvendo um template para uma arvore AVL.

Mas estou com algumas dúvidas em como checar desequilibrios, para efetuar as roações.

 

A estrutura que estou utilizando para o template é:

template<class T>
class AVLTree
{
	public:	
		struct _AVLNODE
		{
			T value;
			//int _height;
			struct _AVLNODE* right;
			struct _AVLNODE* left;
		};
//... resto da classe...

Agora vem o problema:

É preferivel manter a altura de cada vertticie (ou nó, se você preferir) na propria estrutura, e conforme percorro a arvore para adicionar um novo verticie eu atualizo as alturas, e então checo por uma diferença >= 2 nas alturas e vejo se é preciso rodar, ou não.

 

Ou eu computo todas as alturas on-the-fly, ao adicionar um nó...

Esse segundo método é de maior complexidade, mas economiza 4 bytes em cada nó...

 

Qual optar?

Por que 4 bytes em cada nó? Se você teria um BYTE para controle de diferença, onde o valor dele poderia ser 0, 1, 2 e 3; 0 - balanceado, 1 - fazer rotação para direita, 2 - rotacionar a esquerda, e 3 - rotação dupla...

 

Algo aproximado...

 

Trabalhei com AVL em um projeto de Banco de Dados próprio da empresa! Tem alguns exemplos no google... Dê uma olhada no CodeProject, achei bem legal o artigo.

 

Se precisar, tenho alguns links guardados.

 

Abraço.

[VictorCacciari 42]

Omar, não tinha pensado em controlar dessa forma. Muito melhor! =D

 

Seguindo a tua dica, dei uma olhada no code project, encontrei uma AVL que parece bem bacana, baixei os sources:

http://www.codeproject.com/KB/architecture/avl_tree.aspx

 

Mais tarde vou dar uma lida e ver como ele fez. :D

 

Olha, se você não se importar em compartilhar os links... hehehehe

Todo material é bem-vindo!

 

http://forum.imasters.com.br/public/style_emoticons/default/thumbsup.gif

Abraços