Olá a todos…
Bom, eu estou implementando a AVL e consegui fazer quase toda a remoção, mas ela está dando problema na remoção de um nó específico(aquele erro que sempre aparece para estragar tudo) e na remoção dos nós que estão mais a direita da árvore… Então, alguém pode ajudar a finalizar… ?
Segue o código:
public void remove(int valor) {
this.raiz = remove(valor, this.raiz);
}
private NodoAvl remove(int valor, NodoAvl nodo) {
if ((nodo == raiz) && nodo == null)
return null;
else if (valor == nodo.info) {
NodoAvl temp = null;
if (nodo.esq == null) {
temp = nodo.dir;
nodo.dir = null;
nodo = null;
nodo = temp;
temp = null;
} else if (nodo.dir == null) {
temp = nodo.esq;
nodo.esq = null;
nodo = null;
nodo = temp;
temp = null;
} else {
temp = nodo.esq;
if (temp.dir != null) {
while (temp.dir != null)
temp = temp.dir;
temp.dir = nodo.dir;
temp = nodo.esq;
nodo.esq = nodo.dir = null;
nodo = temp;
temp = nodo.dir;
nodo.dir = temp.esq;
temp.esq = nodo;
nodo = temp;
temp = null;
} else {
temp.dir = nodo.dir;
nodo.esq = nodo.dir = null;
nodo = temp;
temp = null;
}
nodo.altura = Math.max(altura(nodo.esq), altura(nodo.dir)) + 1;
}
return nodo;
} else if (valor < nodo.info) {
nodo.esq = remove(valor, nodo.esq);
if ((altura(nodo.dir) - altura(nodo.esq)) == 2)
if (altura(nodo.dir) > altura(nodo.esq))
nodo = rotacaoComFilhoEsquerdo(nodo);
else
nodo = duplaRotacaoComFilhoEsquerdo(nodo);
} else if (valor > nodo.info) {
nodo.dir = remove(valor, nodo.dir);
if ((nodo.esq.getAltura() - nodo.dir.getAltura()) == 2)
if (nodo.esq.getAltura() > nodo.dir.getAltura())
nodo = rotacaoComFilhoDireito(nodo);
else
nodo = duplaRotacaoComFilhoDireito(nodo);
}
nodo.altura = Math.max(altura(nodo.esq), altura(nodo.dir)) + 1;
return nodo;
}A estrutura do nodo é a seguinte:
public int info;
public NodoAvl esq;
public NodoAvl dir;
public int altura;A sequencia de inserção é essa:
{ 1, 2, 3, 4, 5, 6, 7, 15, 14, 13, 12, 11, 10, 9, 8 };
A primeira sequência de remoção é essa: 7,10,4,3,9,14,6,5,12,13
E outra sequência é essa: 15,14
Após a inserção a arvore fica dessa forma(os nós de cima são os filhos esquerdos, os imediatamentes são os direitos e os números entre parênteses são as respectivas alturas):
->7(4)
->4(2)
->2(1)
->1(0)
->3(0)
->6(1)
->5(0)
->12(3)
->10(2)
->9(1)
->8(0)
->11(0)
->14(1)
->13(0)
->15(0)
-----------------7-------------------
->6(4)
->4(2)
->2(1)
->1(0)
->3(0)
->5(0)
->12(3)
->10(2)
->9(1)
->8(0)
->11(0)
->14(1)
->13(0)
->15(0)
-----------------10-------------------
->6(3)
->4(2)
->2(1)
->1(0)
->3(0)
->5(0)
->12(2)
->9(1)
->8(0)
->11(0)
->14(1)
->13(0)
->15(0)
------------------4------------------
->6(3)
->3(2)
->2(1)
->1(0)
->5(0)
->12(2)
->9(1)
->8(0)
->11(0)
->14(1)
->13(0)
->15(0)
------------------3------------------
->6(3)
->2(1)
->1(0)
->5(0)
->12(2)
->9(1)
->8(0)
->11(0)
->14(1)
->13(0)
->15(0)
-------------------9-----------------
->6(3)
->2(1)
->1(0)
->5(0)
->12(2)
->8(1)
->11(0)
->14(1)
->13(0)
->15(0)
-------------------14-----------------
->6(3)
->2(1)
->1(0)
->5(0)
->12(2)
->8(1)
->11(0)
->13(1)
->15(0)
-------------------6-----------------
->5(3)
->2(1)
->1(0)
->12(2)
->8(1)
->11(0)
->13(1)
->15(0)
------------------5------------------
->2(3)
->1(0)
->12(2)
->8(1)
->11(0)
->13(1)
->15(0)
-------------------12-----------------
->2(3)
->1(0)
->11(2)
->8(1)
->13(1)
->15(0)
-------------------13-----------------
->2(2)
->1(0)
->11(1)
->8(1)
->15(0)
Então. Quando eu chego na remoção do número cinco na primeira sequência de remoção ela não rebalanceia a árvore e eu não consigo entender o motivo.
Já na segunda sequência, quando eu vou remover o 14 acontece uma nullpointerException…
Agradeço a ajuda…
Tales.