Oferecendo Árvore AVL

class AVL {
    private No raiz;
    public No getRaiz() {
        No raiz = null;
        return raiz;
    }

    private int Tamanho(No t) {
        //retornando a altura
        return t == null ? -1 : t.Altura;
    }

    // retornando o valor maior entre esquerdo e direito
    private int max(int lhs, int rhs) {
        return lhs > rhs ? lhs : rhs;
    }

    // retornando o balanceamento da árvore com raiz t
    private int getFator(No t) {
        return Tamanho(t.Esq) - Tamanho(t.Dir);
    }

   public void inserir(int x) {
        raiz = inserir(x, raiz);
    }

    private No inserir(int x, No t) {
        if (t == null) {
            t = new No(x, null, null);
        } else if (x < t.Dado) {
            t.Esq = inserir(x, t.Dir);
        } else if (x > t.Dado) {
            t.Dir = inserir(x, t.Dir);
        }
        t = balanco(t);
        return t;
    }
        public No balanco(No t) {
        if (getFator(t) == 2) {
            if (getFator(t.Esq) > 0) {
                t = RotacaoSimplesDireita(t);
            } else {
                t = RotacaoDuplaDireita(t);
            }
        } else if (getFator(t) == -2) {
            if (getFator(t.Dir) < 0) {
                t = RotacaoSimplesEsquerda(t);
            } else {
                t = RotacaoDuplaEsquerda(t);
            }
        }
        t.Altura = max(Tamanho(t.Esq), Tamanho(t.Dir)) + 1;
        return t;
    }
            //rotação simples direita
    private No RotacaoSimplesDireita(No k2) {
        No k1 = k2.Esq;
        k2.Esq = k1.Dir;
        k1.Dir = k2;
        k2.Altura = max(Tamanho(k2.Esq), Tamanho(k2.Dir)) + 1;
        k1.Altura = max(Tamanho(k1.Esq), k2.Altura) + 1;
        return k1;
    }

    //rotação simples esquerda
    private No RotacaoSimplesEsquerda(No k1) {
        No k2 = k1.Dir;
        k1.Dir = k2.Esq;
        k2.Esq = k1;
        k1.Altura = max(Tamanho(k1.Esq), Tamanho(k1.Dir)) + 1;
        k2.Altura = max(Tamanho(k2.Dir), k1.Altura) + 1;
        return k2;
    }

    //rotação dupla direita
    private No RotacaoDuplaDireita(No k3) {
        k3.Esq = RotacaoSimplesEsquerda(k3.Esq);
        return RotacaoSimplesDireita(k3);
    }

    //rotação dupla esquerda
    private No RotacaoDuplaEsquerda(No k1) {
        k1.Dir = RotacaoSimplesDireita(k1.Dir);
        return RotacaoSimplesEsquerda(k1);
    }
        public No Busca(int elemento) {
        return Busca(raiz, elemento);
    }

    protected No Busca(No p, int Elemento) {
        while (p != null) {
            // se valor procuradp == chave do nó retorna referência ao nó
            if (Elemento == p.Dado) {
                return p;
            } else if (Elemento < p.Dado) {// se valor procurado < chave do nó, procurar na sub-árvore esquerda deste nó
                p = p.Esq;
            } else {// se valor procurado > chave do nó, procurar na sub-árvore direita deste nó
                p = p.Dir;
            }
        }
        // caso chave não foi achada, retorna null
        return null;
    }

    public void Preordem() {
        System.out.println("A Arvore em Pre Ordem é: ");
        PreOrdem (raiz);
        System.out.println();


    }

    public void Posordem() {
        System.out.println("A Arvore em Pos Ordem é: ");
        PosOrdem(raiz);
        System.out.println();
    }

    public void EmOrdem() {
        System.out.println("A Arvore em Em Ordem é: ");
        EmOrdem(raiz);
        System.out.println();

    }

    protected void PreOrdem(No t) {
        if (t != null) {
            imprime(t.Dado);

            PreOrdem(t.Esq);

            PreOrdem(t.Dir);
        }
    }

    protected void PosOrdem(No t) {
        if (t != null) {
            PosOrdem(t.Esq);

            PosOrdem(t.Dir);

            imprime(t.Dado);
        }
    }

    protected void EmOrdem(No t) {
        if (t != null) {

            EmOrdem(t.Esq);

            imprime(t.Dado);

            EmOrdem(t.Dir);
        }
    }

    public void imprime(int s) {
        System.out.print(" - " + s + " ");
    }
    }


class No {
        public int Altura;
    public int Dado;
    public No Esq, Dir;

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

    public No(int x, No esq, No dir) {
        Dado = x;
        Esq = esq;
        Dir = dir;
        Altura = 0;
    }

}


public class NoAVL {

    private int chave, bal;
    private NoAVL esq, dir, pai;

    /** Creates a new instance of NoAVL */
    public NoAVL() {
    }

    public int getChave() {
        return chave;
    }

    public void setChave(int chave) {
        this.chave = chave;
    }

    public int getBal() {
        return bal;
    }

    public void setBal(int bal) {
        this.bal = bal;
    }

    public NoAVL getEsq() {
        return esq;
    }

    public void setEsq(NoAVL esq) {
        this.esq = esq;
    }

    public NoAVL getDir() {
        return dir;
    }

    public void setDir(NoAVL dir) {
        this.dir = dir;
    }

    public NoAVL getPai() {
        return pai;
    }

    public void setPai(NoAVL pai) {
        this.pai = pai;
    }

}


public class tudoDinovo {
    static NoAVL raiz;
    private boolean h;

    public tudoDinovo() {

    }

    private NoAVL inicia(int x){
        NoAVL aux;
        aux = new NoAVL();
        aux.setChave(x);
        aux.setEsq(null);
        aux.setDir(null);
        aux.setBal(0);
        return aux;
    }

    private NoAVL caso1(NoAVL pt){

        NoAVL ptu;
        ptu = pt.getDir();
        if(ptu.getBal() == -1){
            pt = rotacao_esquerda(pt);
        }else
            pt = rotacao_direita_esquerda(pt);
        pt.setBal(0);
        return pt;
   }



    private NoAVL rotacao_esquerda(NoAVL no){
        NoAVL aux;
        aux = no.getDir();
        no.setDir(aux.getEsq());
        if (aux.getEsq() != null){
            aux.getEsq().setPai(no);
        }
        aux.setEsq(no);
        aux.setPai(no.getPai());
        no.getPai().setEsq(aux);
        no.setPai(aux);
        no.setBal(0);
        return aux;
    }


    private NoAVL rotacao_direita_esquerda(NoAVL no){
        NoAVL pai;
        NoAVL no_dir;
        NoAVL novo_no;
        int fb_fesq;

        pai = no.getPai();
        no_dir = no.getDir();
        fb_fesq = no_dir.getEsq().getBal();
        no.setDir(rotacao_direita(no_dir));
        novo_no = rotacao_esquerda(no);
        novo_no.setPai(pai);
        no.setBal(fb_fesq == -1 ? 1 : 0);
        no_dir.setBal(fb_fesq == 1 ? -1 : 0);
        return novo_no;
    }




    private NoAVL rotacao_direita(NoAVL no){
        NoAVL aux;
        aux = no.getEsq();
        no.setEsq(aux.getDir());
        if (aux.getDir() != null){
            aux.getDir().setPai(no);
        }
        aux.setDir(no);
        aux.setPai(no.getPai());
        no.getPai().setDir(aux);
        no.setPai(aux);
        no.setBal(0);
        return aux;
    }


    private NoAVL rotacao_esquerda_direita(NoAVL no){
        NoAVL pai;
        NoAVL no_esq;
        NoAVL novo_no;
        int fb_fdir;

        pai = no.getPai();
        no_esq = no.getEsq();
        fb_fdir = no_esq.getDir().getBal();
        no.setEsq(rotacao_esquerda(no_esq));
        novo_no = rotacao_direita(no);
        novo_no.setPai(pai);
        no.setBal(fb_fdir == 1 ? -1 : 0);
        no_esq.setBal(fb_fdir == -1 ? 1 : 0);
        return novo_no;
    }

    private NoAVL caso2(NoAVL pt){

        NoAVL ptu;
        ptu = pt.getDir();
        if(ptu.getBal() == 1){
            pt = rotacao_direita(pt);
        }else
            pt = rotacao_esquerda_direita(pt);
        pt.setBal(0);
        return pt;
    }

    private NoAVL baldir(NoAVL pt){
        if (h){
            switch (pt.getBal()){
                case -1:
                    pt.setBal(0);
                    h = false;
                    break;
                case 0:
                    pt.setBal(1);
                    break;
                case 1:
                    pt = caso1(pt);
                    h = false;
                    break;
            }
        }
        return pt;
    }

    private NoAVL balesq(NoAVL pt){
        if (h){
            switch (pt.getBal()){
                case 1:
                    pt.setBal(0);
                    h = false;
                    break;
                case 0:
                    pt.setBal(-1);
                    break;
                case -1:
                    pt = caso2(pt);
                    h = false;
                    break;
            }
        }
        return pt;
    }

    public void insere(int x){
        h = true;
        if (raiz == null){
            raiz = insere(x, null);
        } else{
            raiz = insere(x, raiz);
        }
    }

    private NoAVL insere(int x, NoAVL pt){
        if(pt == null){
            NoAVL aux;
            aux = inicia(x);
            h = true;
            return aux;
        }else {
            if(x < pt.getChave()){
                pt.setEsq(insere(x, pt.getEsq()));
                pt.getEsq().setPai(pt);
                pt = baldir(pt);
            }else{
                pt.setDir(insere(x, pt.getDir()));
                pt.getDir().setPai(pt);
                pt = balesq(pt);
            }
        }
        return pt;
    }


    public String preorder(){
        String arvore =  "";
        if (raiz == null){
            JOptionPane.showMessageDialog(null, "Árvore Vazia!!!");
            return arvore;
        }
        preorder(raiz);
        return arvore;
    }

    private String preorder(NoAVL p){
        String msg = "";
        msg+= p.getChave() + " bal " + p.getBal() + " --- ";
        System.out.print(msg);
        if(p.getEsq() != null){
            preorder(p.getEsq());
        }
        if(p.getDir() != null){
            preorder(p.getDir());
        }
        return msg;
    }

    private NoAVL busca_remove(NoAVL no, NoAVL no_chave) {

        NoAVL no_removido;
        if (no.getDir()!= null) {
            no.setDir(busca_remove(no.getDir(), no_chave));
            if (h)
                no = baldir(no);
        } else {
            no_chave.setChave(no.getChave());
            no_removido = no;
            no = no.getEsq();
            if (no != null)
                no.setPai(no_removido.getPai());
            h = true;     //Deve propagar a atualização dos FB
            no_removido = null;
        }
        return no;
    }


/*
 *  Remoção da Árvore AVL
 *http://www.lcad.icmc.usp.br/~nonato/ED/AVL/algo-remocao.html
 */
    public void remove(int x){

        raiz = remove(raiz, x);
    }

    private NoAVL remove(NoAVL raiz, int x) {
        h = true;
        if (raiz == null) {
            System.out.println("Elemento " + x + " não existe!!" );
            h = false;
        }else {
            //remove o da esquerda
            if (raiz.getChave() > x) {
                raiz.setEsq(remove(raiz.getEsq(), x));
                if (h)
                    raiz = balesq(raiz);
                //remove o da direita
            }else
                if (raiz.getChave() < x) {
                    raiz.setDir(remove(raiz.getDir(), x));
                    if (h)
                        raiz = baldir(raiz);
                }else{
                 //Encontrou o elemento a ser removido
                    if (raiz.getDir() == null) {
                        //raiz com filho a direita nulo
                        if (raiz.getEsq() != null) //Escolhe o nó à esquerda como substituto
                            //raiz com apenas 1 filho (a esquerda)
                            raiz.getEsq().setPai(raiz.getPai());
                        raiz = raiz.getEsq();
                        h = true;
                    }else
                        if (raiz.getEsq() == null) {
                            //raiz com filho a esquerda nulo
                            if (raiz.getDir() != null) //Escolhe o nó à direita como substituto
                                //raiz com apenas 1 filho (a direita)
                                raiz.getDir().setPai(raiz.getPai());
                            raiz = raiz.getDir();
                            h = true;
                        }else {
                            //raiz com 2 filhos
                            // Busca o elemento mais à direita do nó esquerdo
                            raiz.setEsq(busca_remove(raiz.getEsq(), raiz));
                            //Se necessário efetua balanceamento (Esquerdo pois a função
                            //busca_remove foi para o nó esquerdo)
                            if (h){
                                raiz = balesq(raiz);
                            }

                    }
                }
        }
        return(raiz);
    }


    public static void main (String args []){

        AVL avl = new AVL();
                //Arvore tree = new Arvore();
        int valor;
        do {
        valor = Integer.parseInt(JOptionPane.showInputDialog(null, "entre com um valor ou 0 para sair"));
        if (valor != 0) {
        avl.inserir(valor);
        }
        } while (valor != 0);
        avl.Preordem();
        avl.Posordem();
        avl.EmOrdem();
    }
}