Árvore AVL [RESOLVIDO]

Programação Java
#1

Olá pessoal,
tô querendo implementar uma árvore binária AVL, mas tô com dificuldade de implementar as rotações.
Tenho a implementação da árvore binária funcionando 100%, alguém tem alguma idéia de como implementar as rotações nesta árvore para que ela mantenha-se sempre balanceada?
Código Árvore Binária:

[code]public class Arvore_AVL {
No raiz;
public class No{
int info, fat_bal;
No dir, esq;

    public No(int dado){
        esq = dir = null;
        this.info = dado;
        this.fat_bal = 0;
    }

    public void inserir( int valor ){
       if( valor < info ){
           if( esq == null ){
               esq = new No( valor );
           }
           else{
               esq.inserir( valor );
           }
       }
       else if( valor > info ){
           if( dir == null ){
               dir = new No( valor );
           }
           else{
               dir.inserir( valor );
           }
       }
    }
            
}

public Arvore_AVL(){
    {
        raiz = null;
    }
}

 public void inserirNo( int valor ){
      if( raiz == null )
      {
         raiz = new No( valor );
      }
      else
      {
          raiz.inserir( valor );
      }
 }

 public void preOrdem()
 {
     preOrdemAjudante( raiz );
 }

 // Método para percorrer a árvore em pre - ordem
 // utiliza a recursão para percorrer os nos da ávore

 public void preOrdemAjudante( No no )
 {
      if( no == null )
       return;

      System.out.println( no.info + "" );

      preOrdemAjudante( no.esq );

      preOrdemAjudante( no.dir );
  }


public static void main(String args[]){
    Arvore_AVL arvore = new Arvore_AVL();
    arvore.inserirNo(10);
    arvore.inserirNo(20);
    arvore.inserirNo(30);
    arvore.preOrdem();
    
}

[/code]
Agradeço a ajuda!
T+

Árvore AVL
#2

Eu fiz uma implementação de uma estrutura dessas em JME na minha graduação. Basicamente, o que eu fiz foi sempre que eu fazia uma inserção, eu “subia” na árvore, verificando sempre se os nós estavam balanceados. Você pode fazer isso verificando se o módulo da diferença entre a altura da sub-árvore esquerda com a altura da sub-árvore da direita é menor que 2.
Outra dica: você pode fazer isso numa rotina recursiva.

[]'s.

#3

Segue abaixo as duas classes que fazem o que voce quer

[code] // Basic node stored in AVL trees
// Note that this class is not accessible outside
// of package DataStructures

public class AvlNode {
	protected int height;       // Height
	protected int key;
    protected AvlNode left, right;

    public AvlNode ( int theElement ) {
        this( theElement, null, null );
    }

    public AvlNode ( int theElement, AvlNode lt, AvlNode rt ) {
        key = theElement;
        left = lt;
        right = rt;
        height   = 0;
    }
}[/code]

[code]
public class AvlTree {
private AvlNode root = null;

    public AvlTree( ) {
        root = null;
    }
    
    public void clear() {
        root = null;
    }
    public boolean isEmpty() {
        return root == null;
    }
    
    public AvlNode getRootNode (){
        return root;
    }
    
    /** Retorna a altura da árvore */
    private static int height( AvlNode t ) {
        return t == null ? -1 : t.height;
    }
    
     /**
     * Retorna o maior valor ente lhs e rhs.
     */
    private static int max( int lhs, int rhs ) {
        return lhs > rhs ? lhs : rhs;
    }
    
    /** Retorna o fator de balanceamento da árvore com raiz t */ 
    private int getFactor (AvlNode t) {
        return height( t.left ) - height( t.right );
    }
    
    public boolean insert (int x) {
        root = insert (x, root);
        return true;
    }
    
    private AvlNode insert (int x, AvlNode t) {
        if( t == null )
            t = new AvlNode( x, null, null );
        else if( x<t.key ) t.left = insert( x, t.left );
        else if( x>t.key) t.right = insert( x, t.right );
        t = balance (t);
        return t;
    }
    
    public AvlNode balance (AvlNode t) {
        if ( getFactor(t) == 2 ) {
                if (getFactor (t.left)>0) t = doRightRotation( t );
                else t = doDoubleRightRotation( t );
        }
        else if ( getFactor(t) == -2 ) {
                if ( getFactor(t.right)<0 ) t = doLeftRotation( t );
                else t = doDoubleLeftRotation( t );
        }
        t.height = max( height( t.left ), height( t.right ) ) + 1;
        return t;
    }

    /** Faz Rotação simples a direita */
    private static AvlNode doRightRotation( AvlNode k2 ) {
        AvlNode k1 = k2.left;
        k2.left = k1.right;
        k1.right = k2;
        k2.height = max( height( k2.left ), height( k2.right ) ) + 1;
        k1.height = max( height( k1.left ), k2.height ) + 1;
        return k1;
    }

    /** Rotação simples à esquerda */
    private static AvlNode doLeftRotation( AvlNode k1 ) {
        AvlNode k2 = k1.right;
        k1.right = k2.left;
        k2.left = k1;
        k1.height = max( height( k1.left ), height( k1.right ) ) + 1;
        k2.height = max( height( k2.right ), k1.height ) + 1;
        return k2;
    }

    /** Rotação dupla à direita */
    private static AvlNode doDoubleRightRotation( AvlNode k3 ) {
        k3.left = doLeftRotation( k3.left );
        return doRightRotation( k3 );
   }

    /** Rotação dupla à esquerda */
    private static AvlNode doDoubleLeftRotation( AvlNode k1 ) {
        k1.right = doRightRotation( k1.right );
        return doLeftRotation( k1 );
    }
    
    public AvlNode search(int el) {
        return search(root,el);
    }
    protected AvlNode search(AvlNode p, int el) {
        while (p != null) {
            /* se valor procuradp == chave do nó retorna referência ao nó */ 
            if (el==p.key) return p;
            /* se valor procurado < chave do nó, procurar na sub-árvore esquerda deste nó */
            else if (el<p.key) p = p.left;
            /* se valor procurado > chave do nó, procurar na sub-árvore direita deste nó */
            else p = p.right;
        }
        // caso chave não foi achada, retorna null
        return null;
    }
    
    public void inorder() {
        inorder(root);
    }
    protected void inorder(AvlNode p) {
        if (p != null) {
             inorder(p.left);
             System.out.print(p.key+" - ");
             inorder(p.right);
        }
    }
    
    public void preorder() {
        preorder(root);
    }
    protected void preorder(AvlNode p) {
        if (p != null) {
             System.out.print(p.key + " ");
             preorder(p.left);
             preorder(p.right);
        }
    }
    
    public void postorder() {
        postorder(root);
    }

    protected void postorder(AvlNode p) {
        if (p != null) {
             postorder(p.left);
             postorder(p.right);
             System.out.print(p.key + " ");
        }
    }
    
protected AvlNode searchFather (int el) {
    AvlNode p = root;
    AvlNode prev = null;
    while (p != null && !(p.key==el)) {  // acha o nó p com a chave el
        prev = p;                           
        if (p.key<el)
              p = p.right;
        else p = p.left;
    }
    if (p!=null && p.key==el) return prev;
    return null;
}

/* método de autoria de Leonardo Zandoná - 2006/2 */
public void displayTree() {
	if (isEmpty()){
		System.out.println("Árvore vazia!");
		return;
	}    		
	String separator = String.valueOf("  |__");
	System.out.println(this.root.key+"("+root.height+")");
	displaySubTree(root.left,  separator);
	displaySubTree(root.right, separator);
}
private void displaySubTree(AvlNode node, String separator) {
	
	if (node != null) {
		
		AvlNode father = this.searchFather(node.key);
		if (node.equals(father.left) == true) {
			System.out.println(separator+node.key+"("+node.height+")"+" (ESQ)");
		}else{
			System.out.println(separator+node.key+"("+node.height+")"+" (DIR)");
		}			
		displaySubTree(node.left,  "     "+separator);
		displaySubTree(node.right, "     "+separator);
	}
}
    
    public static void main (String args[]){
        AvlTree t = new AvlTree();
        t.insert(1);
        t.insert(2);
        t.insert(3);
        t.insert(4);
        t.insert(5);
        t.insert(6);
        t.insert(7);
        t.insert(8);
        t.insert(9);
        t.displayTree();
    }

} // class[/code]

#4

Olá xupisco,
Seu código funcionou perfeitamente, vou estudá-lo para entender melhor como funciona a estrutura!
Valeu pela força! T+

#5

parabens xupisco realmente testei e funciona mesmo!

#6

De boa, mas tem uma coisa.
os nós de uma Árvore AVL guardam tipicamente um fator de balanceamento,
que varia entre -1 0 1.

eu posso ter entendido errado,
mas na árvore apresentada o fator de balanceamento foi substituido por um atributo ‘altura’ que guarda a altura do nó em relação aos folhas. ;x

vo tentar mudar o fator de balanceamento aqui. ;p

#7

Como remover um elemento da arvore avl através desse codigo?

#8