Skip to content

Instantly share code, notes, and snippets.

@rodrigovilar
Created June 11, 2013 04:09
Show Gist options
  • Save rodrigovilar/5754425 to your computer and use it in GitHub Desktop.
Save rodrigovilar/5754425 to your computer and use it in GitHub Desktop.
import java.util.ArrayList;
public class ArvoreAvl {
protected No raiz;
public void inserir(int k) {
No n = new No(k);
inserirAVL(this.raiz, n);
}
public void inserirAVL(No aComparar, No aInserir) {
if (aComparar == null) {
this.raiz = aInserir;
} else {
if (aInserir.getChave() < aComparar.getChave()) {
if (aComparar.getEsquerda() == null) {
aComparar.setEsquerda(aInserir);
aInserir.setPai(aComparar);
verificarBalanceamento(aComparar);
} else {
inserirAVL(aComparar.getEsquerda(), aInserir);
}
} else if (aInserir.getChave() > aComparar.getChave()) {
if (aComparar.getDireita() == null) {
aComparar.setDireita(aInserir);
aInserir.setPai(aComparar);
verificarBalanceamento(aComparar);
} else {
inserirAVL(aComparar.getDireita(), aInserir);
}
} else {
// O nó já existe
}
}
}
public void verificarBalanceamento(No atual) {
setBalanceamento(atual);
int balanceamento = atual.getBalanceamento();
if (balanceamento == -2) {
if (altura(atual.getEsquerda().getEsquerda()) >= altura(atual.getEsquerda().getDireita())) {
atual = rotacaoDireita(atual);
} else {
atual = duplaRotacaoEsquerdaDireita(atual);
}
} else if (balanceamento == 2) {
if (altura(atual.getDireita().getDireita()) >= altura(atual.getDireita().getEsquerda())) {
atual = rotacaoEsquerda(atual);
} else {
atual = duplaRotacaoDireitaEsquerda(atual);
}
}
if (atual.getPai() != null) {
verificarBalanceamento(atual.getPai());
} else {
this.raiz = atual;
}
}
public void remover(int k) {
removerAVL(this.raiz, k);
}
public void removerAVL(No atual, int k) {
if (atual == null) {
return;
} else {
if (atual.getChave() > k) {
removerAVL(atual.getEsquerda(), k);
} else if (atual.getChave() < k) {
removerAVL(atual.getDireita(), k);
} else if (atual.getChave() == k) {
removerNoEncontrado(atual);
}
}
}
public void removerNoEncontrado(No aRemover) {
No r;
if (aRemover.getEsquerda() == null || aRemover.getDireita() == null) {
if (aRemover.getPai() == null) {
this.raiz = null;
aRemover = null;
return;
}
r = aRemover;
} else {
r = sucessor(aRemover);
aRemover.setChave(r.getChave());
}
No p;
if (r.getEsquerda() != null) {
p = r.getEsquerda();
} else {
p = r.getDireita();
}
if (p != null) {
p.setPai(r.getPai());
}
if (r.getPai() == null) {
this.raiz = p;
} else {
if (r == r.getPai().getEsquerda()) {
r.getPai().setEsquerda(p);
} else {
r.getPai().setDireita(p);
}
verificarBalanceamento(r.getPai());
}
r = null;
}
public No rotacaoEsquerda(No inicial) {
No direita = inicial.getDireita();
direita.setPai(inicial.getPai());
inicial.setDireita(direita.getEsquerda());
if (inicial.getDireita() != null) {
inicial.getDireita().setPai(inicial);
}
direita.setEsquerda(inicial);
inicial.setPai(direita);
if (direita.getPai() != null) {
if (direita.getPai().getDireita() == inicial) {
direita.getPai().setDireita(direita);
} else if (direita.getPai().getEsquerda() == inicial) {
direita.getPai().setEsquerda(direita);
}
}
setBalanceamento(inicial);
setBalanceamento(direita);
return direita;
}
public No rotacaoDireita(No inicial) {
No esquerda = inicial.getEsquerda();
esquerda.setPai(inicial.getPai());
inicial.setEsquerda(esquerda.getDireita());
if (inicial.getEsquerda() != null) {
inicial.getEsquerda().setPai(inicial);
}
esquerda.setDireita(inicial);
inicial.setPai(esquerda);
if (esquerda.getPai() != null) {
if (esquerda.getPai().getDireita() == inicial) {
esquerda.getPai().setDireita(esquerda);
} else if (esquerda.getPai().getEsquerda() == inicial) {
esquerda.getPai().setEsquerda(esquerda);
}
}
setBalanceamento(inicial);
setBalanceamento(esquerda);
return esquerda;
}
public No duplaRotacaoEsquerdaDireita(No inicial) {
inicial.setEsquerda(rotacaoEsquerda(inicial.getEsquerda()));
return rotacaoDireita(inicial);
}
public No duplaRotacaoDireitaEsquerda(No inicial) {
inicial.setDireita(rotacaoDireita(inicial.getDireita()));
return rotacaoEsquerda(inicial);
}
public No sucessor(No q) {
if (q.getDireita() != null) {
No r = q.getDireita();
while (r.getEsquerda() != null) {
r = r.getEsquerda();
}
return r;
} else {
No p = q.getPai();
while (p != null && q == p.getDireita()) {
q = p;
p = q.getPai();
}
return p;
}
}
private int altura(No atual) {
if (atual == null) {
return -1;
}
if (atual.getEsquerda() == null && atual.getDireita() == null) {
return 0;
} else if (atual.getEsquerda() == null) {
return 1 + altura(atual.getDireita());
} else if (atual.getDireita() == null) {
return 1 + altura(atual.getEsquerda());
} else {
return 1 + Math.max(altura(atual.getEsquerda()), altura(atual.getDireita()));
}
}
private void setBalanceamento(No no) {
no.setBalanceamento(altura(no.getDireita()) - altura(no.getEsquerda()));
}
final protected ArrayList<No> inorder() {
ArrayList<No> ret = new ArrayList<No>();
inorder(raiz, ret);
return ret;
}
final protected void inorder(No no, ArrayList<No> lista) {
if (no == null) {
return;
}
inorder(no.getEsquerda(), lista);
lista.add(no);
inorder(no.getDireita(), lista);
}
}
public class No {
private No esquerda;
private No direita;
private No pai;
private int chave;
private int balanceamento;
public No(int k) {
setEsquerda(setDireita(setPai(null)));
setBalanceamento(0);
setChave(k);
}
public String toString() {
return Integer.toString(getChave());
}
public int getChave() {
return chave;
}
public void setChave(int chave) {
this.chave = chave;
}
public int getBalanceamento() {
return balanceamento;
}
public void setBalanceamento(int balanceamento) {
this.balanceamento = balanceamento;
}
public No getPai() {
return pai;
}
public No setPai(No pai) {
this.pai = pai;
return pai;
}
public No getDireita() {
return direita;
}
public No setDireita(No direita) {
this.direita = direita;
return direita;
}
public No getEsquerda() {
return esquerda;
}
public void setEsquerda(No esquerda) {
this.esquerda = esquerda;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment