Olá, Amigos, não estou conseguindo remover na minha árvore AVL:
public class AvlNode {
protected int altura; // Height
protected int chave;
protected AvlNode esquerda, direita;
public AvlNode ( int theElement ) {
this( theElement, null, null );
}
public AvlNode ( int valor, AvlNode folhaEsquerda, AvlNode folhaDireita ) {
chave = valor;
esquerda = folhaEsquerda;
direita = folhaDireita;
altura = 0;
}
public class AvlTree {
static int totalRotacaoDireita=0;
static int totalRotacaoDuplaDireita=0;
static int totalRotacaoEsquerda=0;
static int totalRotacaoDuplaEsquerda=0;
private AvlNode raizArvore = null;
public AvlTree( ) {
raizArvore = null;
}
public void Limpar() {
raizArvore = null;
}
public boolean Vazio() {
return raizArvore == null;
}
public AvlNode getraizArvoreNode (){
return raizArvore;
}
/** Retorna a altura da árvore */
private static int altura( AvlNode t ) {
return t == null ? -1 : t.altura;
}
/**
* Retorna o maior valor entre altura a esquerda e altura a direita.
*/
private static int max( int alturaEsquerda, int alturaDireita ) {
return alturaEsquerda > alturaDireita ? alturaEsquerda : alturaDireita;
}
/** Retorna o fator de balanceamento da árvore com raiz t */
private int bal (AvlNode t) {
return altura( t.esquerda ) - altura( t.direita );
}
public boolean inserir (int x) {
raizArvore = inserir (x, raizArvore);
return true;
}
private AvlNode inserir (int x, AvlNode t) {
if( t == null )
t = new AvlNode( x, null, null );
else if( x<t.chave ) t.esquerda = inserir( x, t.esquerda );
else if( x>t.chave) t.direita = inserir( x, t.direita );
t = balancear (t);
return t;
}
public AvlNode retorna_maior(AvlNode t){
AvlNode aux;
aux = t;
if (aux.direita==null){
t=t.esquerda;
return aux;
}else
return (retorna_maior(t.direita));
}
public boolean remover (int x) {
raizArvore = remover (x, raizArvore);
return true;
}
private AvlNode remover (int x, AvlNode t) {
AvlNode aux;
if (t == null) {
return t;
}
if (t.chave==x){ //encontrou
aux=t;
/* se não tiver filho na esquerda */
if (t.esquerda==null) {
t=t.direita; /*então o filho da direita substitui */
}
/* se não tem filho a direita */
else if (t.direita==null) {
t=t.esquerda; /* então o filho da esquerda substitui */
}
/* senão possui dois filhos */
else {
aux=retorna_maior(t.esquerda); /* busca o substituto */
t.chave = aux.chave;
}
return t;
}else{
if (x<t.chave) {
return (remover(x, t.esquerda));
}
else {
return (remover(x, t.direita));
}
}
}
public AvlNode balancear (AvlNode t) {
if ( bal(t) == 2 ) {
if (bal (t.esquerda)>0) t = rotacaoDireita( t );
else t = rotacaoDuplaDireita( t );
}
else if ( bal(t) == -2 ) {
if ( bal(t.direita)<0 ) t = rotacaoEsquerda( t );
else t = rotacaoDuplaEsquerda( t );
}
t.altura = max( altura( t.esquerda ), altura( t.direita ) ) + 1;
return t;
}
/** Faz Rotação simples a direita */
private static AvlNode rotacaoDireita( AvlNode k2 ) {
AvlNode k1 = k2.esquerda;
k2.esquerda = k1.direita;
k1.direita = k2;
k2.altura = max( altura( k2.esquerda ), altura( k2.direita ) ) + 1;
k1.altura = max( altura( k1.esquerda ), k2.altura ) + 1;
totalRotacaoDireita = totalRotacaoDireita + 1;
return k1;
}
/** Rotação simples à esquerda */
private static AvlNode rotacaoEsquerda( AvlNode k1 ) {
AvlNode k2 = k1.direita;
k1.direita = k2.esquerda;
k2.esquerda = k1;
k1.altura = max( altura( k1.esquerda ), altura( k1.direita ) ) + 1;
k2.altura = max( altura( k2.direita ), k1.altura ) + 1;
totalRotacaoEsquerda = totalRotacaoEsquerda + 1;
return k2;
}
/** Rotação dupla à direita */
private static AvlNode rotacaoDuplaDireita( AvlNode k3 ) {
k3.esquerda = rotacaoEsquerda( k3.esquerda );
totalRotacaoDuplaDireita = totalRotacaoDuplaDireita + 1;
return rotacaoDireita( k3 );
}
/** Rotação dupla à esquerda */
private static AvlNode rotacaoDuplaEsquerda( AvlNode k1 ) {
k1.direita = rotacaoDireita( k1.direita );
totalRotacaoDuplaEsquerda = totalRotacaoDuplaEsquerda + 1;
return rotacaoEsquerda( k1 );
}
/** vl=valor */
public AvlNode procurar(int vl) {
return procurar(raizArvore,vl);
}
protected AvlNode procurar(AvlNode p, int vl) {
while (p != null) {
/* se valor procurado == chave do nó retorna referência ao nó */
if (vl==p.chave) return p;
/* se valor procurado < chave do nó, procurar na sub-árvore esquerda deste nó */
else if (vl<p.chave) p = p.esquerda;
/* se valor procurado > chave do nó, procurar na sub-árvore direita deste nó */
else p = p.direita;
}
// caso chave não foi achada, retorna null
return null;
}
public void emordem() {
emordem(raizArvore);
}
protected void emordem(AvlNode p) {
if (p != null) {
emordem(p.esquerda);
System.out.print(p.chave+" - ");
emordem(p.direita);
}
}
public void preordem() {
preordem(raizArvore);
}
protected void preordem(AvlNode p) {
if (p != null) {
System.out.print(p.chave + " ");
preordem(p.esquerda);
preordem(p.direita);
}
}
public void posordem() {
posordem(raizArvore);
}
protected void posordem(AvlNode p) {
if (p != null) {
posordem(p.esquerda);
posordem(p.direita);
System.out.print(p.chave + " ");
}
}
protected AvlNode procurarPai (int vl) {
AvlNode p = raizArvore;
AvlNode prev = null;
while (p != null && !(p.chave==vl)) { // acha o nó p com a chave el
prev = p;
if (p.chave<vl)
p = p.direita;
else p = p.esquerda;
}
if (p!=null && p.chave==vl) return prev;
return null;
}
/* método de autoria de Leonardo Zandoná - 2006/2 */
public void mostrarArvore() {
if (Vazio()){
System.out.println("Árvore vazia!");
return;
}
String separador = String.valueOf(" |__");
System.out.println(this.raizArvore.chave+"("+raizArvore.altura+")");
mostrarSubArvore(raizArvore.esquerda, separador);
mostrarSubArvore(raizArvore.direita, separador);
}
private void mostrarSubArvore(AvlNode node, String separador) {
if (node != null) {
AvlNode pai = this.procurarPai(node.chave);
if (node.equals(pai.esquerda) == true) {
System.out.println(separador+node.chave+"("+node.altura+")"+" (ESQ)");
}else{
System.out.println(separador+node.chave+"("+node.altura+")"+" (DIR)");
}
mostrarSubArvore(node.esquerda, " "+separador);
mostrarSubArvore(node.direita, " "+separador);
}
}
public void mostrarRotacoes() {
System.out.println("Total de Rotações Simples a Direita: " + totalRotacaoDireita);
System.out.println("Total de Rotações Simples a Esquerda: " + totalRotacaoEsquerda);
System.out.println("Total de Rotações Dupla a Direita: " + totalRotacaoDuplaDireita);
System.out.println("Total de Rotações Dupla a Esquerda: " + totalRotacaoDuplaEsquerda);
}
public static void main (String args[]){
AvlTree t = new AvlTree();
t.inserir(4);
t.inserir(17);
t.inserir(23);
t.inserir(14);
t.inserir(9);
t.inserir(5);
t.inserir(16);
t.inserir(24);
t.inserir(41);
t.inserir(81);
t.inserir(45);
t.mostrarArvore();
t.remover(9);
t.remover(5);
t.remover(16);
t.mostrarArvore();
t.mostrarRotacoes();
}
Especificamente o que não está funcionando corretamente é essa parte:
private AvlNode remover (int x, AvlNode t) {
AvlNode aux;
if (t == null) {
return t;
}
if (t.chave==x){ //encontrou
aux=t;
/* se não tiver filho na esquerda */
if (t.esquerda==null) {
t=t.direita; /*então o filho da direita substitui */
}
/* se não tem filho a direita */
else if (t.direita==null) {
t=t.esquerda; /* então o filho da esquerda substitui */
}
/* senão possui dois filhos */
else {
aux=retorna_maior(t.esquerda); /* busca o substituto */
t.chave = aux.chave;
}
return t;
}else{
if (x<t.chave) {
return (remover(x, t.esquerda));
}
else {
return (remover(x, t.direita));
}
}
}
Quando eu imprimo;
17(3)
|__9(2) (ESQ)
|__4(1) (ESQ)
|__5(0) (DIR)
|__14(1) (DIR)
|__16(0) (DIR)
|__24(2) (DIR)
|__23(0) (ESQ)
|__45(1) (DIR)
|__41(0) (ESQ)
|__81(0) (DIR)
Árvore vazia!
Total de Rotações Simples a Direita: 3
Total de Rotações Simples a Esquerda: 5
Total de Rotações Dupla a Direita: 0
Total de Rotações Dupla a Esquerda: 2
Ou seja, ta removendo tudo quando eu faço uma remoção, também não sei em qual parte colocar o balanceamento, tentei colocar antes do return e deu um erro.
P.S: Eu peguei um código de remoção AVL em C e tentei adaptar no JAVA.