ArvoreAvl.java

import java.util.Arrays;
import java.util.Scanner;
 
 
public class Main {
 
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		Scanner entrada = new Scanner(System.in);
		int n = entrada.nextInt();
		
		ArvoreBinariaAvl arvoreBinaria = new ArvoreBinariaAvl();
		for( int i = 0; i < n; i++ )
			arvoreBinaria.addNo(new No(entrada.nextInt()));
		//arvoreBinaria.calculaFbArvore();
		arvoreBinaria.balancear();
		arvoreBinaria.calculaFbArvore();
		System.out.println(arvoreBinaria.altura());
		arvoreBinaria.imprime();
		entrada.close();
 
	}
 
 
}
 
 
class No{
	
	private int elemento;
	private int fb;
	private No esq = null;
	private No dir = null;
	
	public No(int e){
		elemento = e;
	}
	
	public No getEsq() {
		return esq;
	}
	public void setEsq(No esq) {
		this.esq = esq;
	}
	public No getDir() {
		return dir;
	}
	public void setDir(No dir) {
		this.dir = dir;
	}
	public int getElemento() {
		return elemento;
	}

	public int getFb() {
		return fb;
	}

	public void setFb(int fb) {
		this.fb = fb;
	}
}
 
class ArvoreBinariaAvl{
	
	private No raiz;
	
	public void addNo(No no){
		if( raiz == null)
			raiz = no;
		else
			addNoAvl(raiz, no);
			
	}
 
	private void addNoAvl(No r, No no) {
		
		if( no.getElemento() < r.getElemento()){
			if( r.getEsq() == null )
				r.setEsq(no);
			else
				addNoAvl(r.getEsq(), no);
		}
		else if( no.getElemento() > r.getElemento()){
			if( r.getDir() == null )
				r.setDir(no);
			else
				addNoAvl(r.getDir(), no);
		}
	}
	
	public void imprime(){
		imprimeEmOrdem(raiz);
	}
 
	private void imprimeEmOrdem(No r) {
		if( r != null){
			System.out.println("" + r.getElemento() + "Fb-> " + r.getFb());
			imprimeEmOrdem(r.getEsq());
			imprimeEmOrdem(r.getDir());
		}
	}
	public void calculaFbArvore(){
		calculaFb(raiz);
	}
	
	private void calculaFb(No r){
		if ( r != null ){
			int esq = alturaAvl(r.getEsq());
			int dir = alturaAvl(r.getDir());
			r.setFb(esq - dir);
			calculaFb(r.getEsq());
			calculaFb(r.getDir());
		}
	}
	
	public int altura(){
		return alturaAvl(raiz);
	}
	
	private int alturaAvl(No r){
		if( r  == null)
			return -1;
		else{
			int esq = alturaAvl(r.getEsq()) + 1;
			int dir = alturaAvl(r.getDir()) + 1;
			return esq > dir ? esq : dir;
		}
	}
	
	public void balancear(){
		raiz = balancearAvl(raiz);
	}
	
	private No balancearAvl(No r) {
		if ( r == null )
			return null;
		else{
			r.setEsq(balancearAvl(r.getEsq()));
			r.setDir(balancearAvl(r.getDir()));
			calculaFb(r);
			No raiz = r;
			if (r.getFb() > 1){
				No B = r.getEsq();
				if( B.getFb() > 0 )
					raiz = RR(r);
				if (B.getFb() < 0)
					raiz = LR(r);
			}
			if( r.getFb() < -1){
				No B = r.getDir();
				if( B.getFb() < 0)
					raiz = LL(r);
				if( B.getFb() > 0)
					raiz = RL(r);
			}
			return raiz;
		}
	}

	private No RR(No A){
		No B = A.getEsq();
		A.setEsq(B.getDir());
		B.setDir(A);
		return B;
	}
	
	private No LL(No A){
		No B = A.getDir();
		A.setDir(B.getEsq());
		B.setEsq(A);
		return B;
	}
	
	private No LR(No A){
		No B = A.getEsq();
		No C = B.getDir();
		B.setDir(C.getEsq());
		C.setEsq(B);
		A.setEsq(C);
		return RR(A);
	}
	
	private No RL(No A){
		No B = A.getDir();
		No C = B.getEsq();
		B.setEsq(C.getDir());
		C.setDir(B);
		A.setDir(C);
		return LL(A);
	}
}