Usamos cookies para medir audiência e melhorar sua experiência. Você pode aceitar ou recusar a qualquer momento. Veja sobre o iMasters.
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;
};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, 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
>
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
{
//... 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.