Gente essa implementação é de uma inserção e remoção em uma árvore AVL.
Não consigo descobrir o que tem de errado que não está rotacionando a árvore corretamente quando
insiro os elementos: 8, 5, 10, 3, 4. Ele tira o 10 da exibição e repete o 5 duas vezes. Além disso, coloca a subárvore do 4 no lado errado.
Já olhei uma porção de vezes e não consigo achar. :(
Segue o código abaixo:
package Ins_Rem_Arvore;
import Ins_Rem_Arvore.Node;
public class Node
{
public int info;//atributo que guarda a informação do no
public Node dir;//atributo que aponta para o no esquerdo
public Node esq;//atributo que aponta para o no direito
public Node pai;//atributo que aponta para o pai do no
public int balanco; //atributo utilizado apenas na arvore avl. balanco = altura(arvore a esq) - altura(arvore a dir)
//construtor com entrada da chave
public Node(int x)
{
this.info = x;
this.dir = null;
this.esq = null;
this.pai = null;
this.balanco = 0;
}
/*========================================================================================*/
//construtor padrao
public Node()
{
}
/*========================================================================================*/
//construtor com entrada da chave e Node dir e esq
public Node(int x,Node esq,Node dir)
{
this.info = x;
this.dir = dir;
this.esq = esq;
this.pai = null;
this.dir.pai = this;
this.esq.pai =this;
}
}
package Ins_Rem_Arvore;
import javax.swing.JOptionPane;
import Ins_Rem_Arvore.Node;
/** Arvore AVL
*/
public class ArvoreAvl
{
private boolean t; //controlador do balanceamento da arvore
private int local; //localiza se o pai do no removido vai ter um novo
private Node raiz; // no raiz da arvore
private Node pt; // no de percurso
private Node aux;// no auxiliar de percurso (guarda o ultimo no acessado)
private int pos; // posicao do no, 1 = esquerda, 2 = direita
private String print; //atributo para impressao da arvore
/*========================================================================================*/
public ArvoreAvl()
{
this.raiz = null;
this.pt = null;
this.aux = null;
this.print = " ";
}
/*========================================================================================*/
//Metodo que executa a rotacao direita
private void rotacaoDireita(Node p,boolean h)
{
Node ptu = new Node();
boolean testeraiz = false; //testa se o no e a raiz
if (p == raiz)
testeraiz = true;
ptu = p.esq;
if (ptu.balanco == -1)
{
p.esq = ptu.dir; //seu filho a esquerda sera o filho a direita de seu filho
if (ptu.dir != null)
{
ptu.dir.pai = p; //novo pai
}
if (p !=raiz)
{
p.pai.esq = ptu;
}
ptu.pai = p.pai;
ptu.dir = p;
p.pai = ptu;
p.balanco = 0;
p = ptu;
if (testeraiz)
raiz = ptu;
}
else
{ //rotacao dupla direita
Node ptv = new Node();
ptv = ptu.dir;
ptu.dir = ptv.esq;
if (ptv.esq != null)
{
ptv.esq.pai= ptu;
}
ptv.esq = ptu;
ptu.pai = ptv;
p.esq = ptv.dir;
if (ptv.dir !=null)
{
ptv.dir.pai = p;
}
ptv.dir = p;
if (p.pai !=null)
{
p.pai.dir = ptv;
} //o pai de p tera ptv como seu novo filho a direita
ptv.pai = p.pai;
p.pai =ptv;
if (ptv.balanco == -1)
p.balanco = 1;
else
p.balanco = 0;
if (ptv.balanco == 1)
ptu.balanco = -1;
else
ptu.balanco = 0;
if (testeraiz)
raiz = ptv;
p = ptv;
}
p.balanco = 0;
t = false;
}
/*========================================================================================*/
//Metodo que executa a rotacao esquerda
private void rotacaoEsquerda(Node p,boolean h)
{
Node ptu = new Node();
boolean testeraiz = false;
if (p == raiz)
testeraiz = true;
ptu = p.dir;
if (ptu.balanco == 1)
{
p.dir = ptu.esq; //seu filho a direita sera o filho a esquerda de seu filho
if (ptu.esq != null)
{
ptu.esq.pai = p; //novo pai
}
if (p !=raiz)
{
p.pai.dir = ptu;
} //o pai de p tera o filho a direita de p como seu novo filho a direita
ptu.pai = p.pai;
ptu.esq = p;
p.pai = ptu;
p.balanco = 0;
p = ptu;
if (testeraiz)
raiz = ptu;
}
else
{
//rotacao dupla esquerda
Node ptv = new Node();
ptv = ptu.esq;
ptu.esq = ptv.dir;
if (ptv.dir !=null)
{
ptv.dir.pai= ptu;
}
ptv.dir = ptu;
ptu.pai = ptv;
p.dir = ptv.esq;
if (ptv.esq !=null)
{
ptv.esq.pai = p;
}
ptv.esq = p;
if (p.pai !=null)
{
p.pai.esq = ptv;
}
p.pai =ptv;
if (ptv.balanco == 1)
p.balanco = -1;
else
p.balanco = 0;
if (ptv.balanco == -1)
ptu.balanco = 1;
else
ptu.balanco = 0;
if (testeraiz)
raiz = ptv;
p = ptv;
}
p.balanco = 0;
t = false;
}
/*========================================================================================*/
//Metodo de insercao de um elemento na arvore
public boolean inserirElemento(int x)
{
pt = new Node(x);
if (raiz == null)
{
raiz = pt;
}//se arvore vazia, insere na raiz
else
{
pt = raiz;
insAVL(x,pt,false);
}
return true;
}
/*========================================================================================*/
//Metodo que auxilia o metodo inserirElemento() para insercao e balanceamnto
private boolean insAVL(int x,Node pt,boolean h)
{
t = h;
if (pt == null)
{//No alocado no espaco vazio
pt = new Node(x);
if(pos==1)
{
aux.esq= pt;
}
else if (pos == 2)
{
aux.dir = pt;
}
pt.pai = aux;//pai do no
t=true;
pos=0;
}
else
{
if (x == pt.info)
{ //ja existe element na arvore
pt = null;
return false;
}
if (x < pt.info)
{//chave menor que o no
aux = pt; //aux sera o pai do no inserido
pos = 1; // filho a esquerda de aux
insAVL(x,pt.esq,t);
//depois da insercao, a verificacao
if (t)
{
if (pt.balanco == 1)
{
pt.balanco = 0;
t = false;
}
else if (pt.balanco == 0)
pt.balanco = -1;
else if (pt.balanco == -1)
rotacaoDireita(pt,t); //rebalanceamento (rotacao direita)
}
}
else
{//chave maior que o no
aux = pt; //aux sera o pai do no inserido
pos = 2; // filho a direita de aux
insAVL(x,pt.dir,t);
//depois da insercao, a verificacao
if (t)
{
if (pt.balanco == -1)
{
pt.balanco = 0;
t = false;
}
else if (pt.balanco == 0)
pt.balanco = 1;
else if (pt.balanco == 1)
rotacaoEsquerda(pt,t); //rebalanceamento (rotacao esquerda)
}
}
}
return true;
}
/*========================================================================================*/
//Metodo de remocao de um elemento na arvore
public boolean removerElemento(int x)
{
if (raiz == null)
{
return false;
}//arvore vazia
else
{
pt = raiz;//no de percurso
remAVL(x,pt,false);
}
return true;
}
/*========================================================================================*/
//Metodo auxiliar para remocao do no x e balanceamento da arvore
public boolean remAVL(int x,Node pt,boolean h)
{
t=h;
if (pt == null)
{
return false;
}//nao achou
else
{
if (x == pt.info )
{
//*******REMOCAO*******/
if (pt.esq == null && pt.dir == null)
{
//no sem filhos
if (pt == raiz)
{
raiz = null;
}
else
{
if (pos == 1)//este no e' o filho da esquerda do seu pai
pt.pai.esq = null;
else if(pos == 2)//este no e' o filho da direita do seu pai
pt.pai.dir = null;
}
pt =null;
t = true;
}
else
{
//tem filhos
aux = pt;
if (pt.esq == null)
{ //pode ter apenas o filho da direita
pt = pt.dir;
local = 1; //pai de pt tera novo filho a direita
}
else
{
if (pt.dir == null)
{//tem apenas o filho da esquerda
pt = pt.esq;
local = 2; //pai de pt tera novo filho a esquerda
}
else
{//tem dois filhos
pt = minDir(aux.dir); //achar o menor a direita
pt.esq = aux.esq; //reordenacao de ponteiros
if (aux == raiz)
{
raiz = pt;
}//se o no a ser removido era a raiz, pt e' a nova raiz
else
{
pt.pai = aux.pai;
if (pos == 1)//este no e' o filho da esquerda do seu pai
aux.pai.esq =pt;
else if(pos == 2)//este no e' o filho da direita do seu pai
aux.pai.dir =pt;
}
aux = null;
return true;
}
}
}
if (aux == raiz)
{
raiz = pt;
}//se o no a ser removido era a raiz, pt e' a nova raiz
else
{//nao e a raiz(tem pai)
if (local == 1)
{
aux.pai.dir = pt;
} //pai tem filho a direita
else if (local == 2)
{
aux.pai.esq = pt;
}//pai tem filho a esquerda
}
aux = null;
}
//Continua a pesquisa
else
{
if (x < pt.info)
{//procura na esquerda
aux = pt;
pos=1;
remAVL(x,pt.esq,t);
//depois da remocao, a verificacao
if (t)
{
if(pt.balanco == -1)
pt.balanco = 0;
t = false;
}
else if (pt.balanco == 0)
pt.balanco = 1;
else if (pt.balanco == 1)
rotacaoEsquerda(pt,t);//rebalanceamento (rotacao esquerda)
}
else
{ //procura na direita
aux = pt;
pos=2;
remAVL(x,pt.dir,t);
//depois da remocao, a verificacao
if (t)
{
if (pt.balanco == 1)
{
pt.balanco = 0;
t = false;
}
else if (pt.balanco == 0)
pt.balanco = -1;
else if (pt.balanco == -1)
rotacaoDireita(pt,t); //rebalanceamento (rotacao direita)
}
}
}
}
local=0; //sem valor, ao final da execucao
return true;
}
/*========================================================================================*/
/*Metodo auxiliar para o metodo da remocao. Acha o no de menor chave ao lado direito do no dado */
protected Node minDir(Node p)
{
if (p.esq ==null)
return p;
else
{
p = p.esq;
return minDir(p);
}
}
/*========================================================================================*/
/*Metodo que exibe a arvore na representacao de parenteses aninhados*/
public String exibirArvorePreOrdem()
{
if (raiz == null)
return "";
Node p = this.raiz; // recebe o no raiz
print = print + Integer.toString(p.info)+ " ";
if (p.esq != null)
{
print = print + "(" + exibirArvorePreOrdem(p.esq)+")";
}
if (p.dir != null)
{
print = print + "(" + exibirArvorePreOrdem(p.dir)+ ")";
}
String pr = print;
print = " ";
return pr;
}
/*========================================================================================*/
//Metodo que exibe a arvore em pre ordem
private String exibirArvorePreOrdem(Node p)
{
print = Integer.toString(p.info)+ " ";
if (p.esq != null)
{
print = print + "( " + exibirArvorePreOrdem(p.esq) + " ) ";
}
if (p.dir != null)
{
print = print + " ( " + exibirArvorePreOrdem(p.dir)+ " ) ";
}
String pr = print;
print = " ";
return pr;
}
/*========================================================================================*/
//Metodo de execucao da Arvore AVL
public void interfaceUsuario()
{
String parametro;
String tipodeOperacao = " ";
boolean testeOperador=false;
boolean testeParametro=false;
while (tipodeOperacao != null)
{
tipodeOperacao = JOptionPane.showInputDialog(" Entre com o tipo de operacao que deseja fazer:\n" +
" [1] Insercao \n [2] Remocao\n ");
if(tipodeOperacao == null || tipodeOperacao.length() == 0)
{
return;
}//entrada vazia(cancelamento do panel)
for(int j =0; j < tipodeOperacao.length(); j++)
{//testa se entrada nao é inteiro
if (!Character.isDigit(tipodeOperacao.charAt(j)))
{
testeOperador =true;
}
}
if (testeOperador)
{
JOptionPane.showMessageDialog( null,"Entrada incorreta (entre com um numero de 1 a 2)", " Arvore AVL ",
JOptionPane.PLAIN_MESSAGE );
}
else
{
if( ( tipodeOperacao.equals("1") ) || ( tipodeOperacao.equals("2") ) )
{
parametro = JOptionPane.showInputDialog("Entre com o parametro da operacao (Int)");
if (parametro == null ||parametro.length() == 0)
{
return;
}//teste de cancelamento ou entrada vazia
for(int j =0; j < parametro.length(); j++)
{
if (!Character.isDigit(parametro.charAt(j)))
{ //testa se entrada nao é inteiro
testeParametro = true;
}
}
if(testeParametro)
{
JOptionPane.showMessageDialog(null,"Entrada incorreta (somente inteiros)"," Arvore B ",JOptionPane.ERROR_MESSAGE);
}
else
{
int x = Integer.parseInt(parametro);
//INSERCAO
if(tipodeOperacao.length() == 1 && tipodeOperacao.charAt(0) == '1')
{
this.inserirElemento(x);
JOptionPane.showMessageDialog(null,"A arvore atual e': " + exibirArvorePreOrdem()
,"Impressao",JOptionPane.PLAIN_MESSAGE);
}
//REMOCAO
else if(tipodeOperacao.length() == 1 && tipodeOperacao.charAt(0) == '2')
{
this.removerElemento(x);
JOptionPane.showMessageDialog(null,"A arvore atual e': " + exibirArvorePreOrdem()
,"Impressao",JOptionPane.PLAIN_MESSAGE);
}
else if(tipodeOperacao == null)
{//cancelou
return; //teste de cancelamento
}
else
{//Se diferente de todas as outras opcoes, entrada incorreta
JOptionPane.showMessageDialog(null,"Entrada incorreta"," Arvore AVL ",
JOptionPane.ERROR_MESSAGE);
}
}
}
else
{
JOptionPane.showMessageDialog( null,"Entrada incorreta (entre com um numero de 1 a 2)",
" Arvore AVL ",JOptionPane.PLAIN_MESSAGE );
}
}
}
}
}
package Ins_Rem_Arvore;
import Ins_Rem_Arvore.ArvoreAvl;
public class ChamaArvoreAVL
{
public static void main(String[] args)
{
ArvoreAvl inicio = new ArvoreAvl();
inicio.interfaceUsuario();
}
}
