Propriedade:
- Esquerda são menores que a raiz;
- Direita são os maiores que a raiz.
- Na árvore AVL de pesquisa T, as alturas de suas sub-árvores (direita e esquerda) diferem no máximo de uma unidade.
Balanceamento:
Para o balanceamento da árvore temos 2 casos
Caso 1: he (p) > hd (p) Ent ão, q pertence à subárvore esquerda de p, e p possui um filho esquerdo u, onde he (u) 6= hd (u). Dois casos podem ocorrer:
- he (u) > hd (u) : rotação direita
- hd (u) > he (u) : rotação dupla direita
Caso 2: hd (p) > he (p) Ent ̃ao, q pertence à sub de p, e p possui um filho direito z, onde he (z) 6= hd (z). Dois casos podem ocorrer:
- hd (z) > he (z) : rotção esquerda
- he (z) > hd (z) : rotação dupla esquerda
Implementação:
import java.util.ArrayList;
public class ArvoreAVL extends Arvore{
private boolean t;
private int local;
public ArvoreAVL(){
super();
}
//Metodo de busca de um elemento com chave x na arvore
public No buscarElemento(int x){
return super.buscarElemento(x);
}
/*========================================================================================*/
private void caso1(No p,boolean h){
No ptu = new No();
boolean testeraiz = false; //testa se o no e a raiz
if (p == raiz) testeraiz = true;
ptu = p.esq;
if (ptu.balanco == -1){ //rotacao direita
p.esq = ptu.dir; //seu filho a esquerda sera o filho a esquerda de seu filho
if (ptu.dir != null){ //so entra se o filho a esquerda existir
ptu.dir.pai = p; //novo pai
}
if (p !=raiz){ p.pai.esq = ptu; } //o pai de p tera o filho a direita de p como seu novo filho a direita
ptu.pai = p.pai;
ptu.dir = p;
p.pai = ptu;
p.balanco = 0;
p = ptu;
if (testeraiz) raiz = ptu;
}
else{ //rotacao dupla direita
No ptv = new No();
ptv = ptu.dir;
ptu.dir = ptv.esq;
if (ptv.esq != null){//so entra se o filho a esquerda existir
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; //se e a raiz
p = ptv;
}
p.balanco = 0;
t = false;
}
/*========================================================================================*/
/*Metodo que executa a rotacao esquerda ou
a rotacao dupla esquerda para balancear a Arvore*/
private void caso2(No p,boolean h){
No ptu = new No();
boolean testeraiz = false;
if (p == raiz) testeraiz = true;
ptu = p.dir;
if (ptu.balanco == 1){ //rotacao esquerda
p.dir = ptu.esq; //seu filho a direita sera o filho a esquerda de seu filho
if (ptu.esq != null){ //so entra se o filho a esquerda existir
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
No ptv = new No();
ptv = ptu.esq;
ptu.esq = ptv.dir;
if (ptv.dir !=null){ //so entra se o filho a direita existir
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;} //o pai de p tera ptv como seu novo filho a esq
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 com chave x na arvore
/*Este metodo faz a busca sem usar a motodo buscarElemento() pois a organizacao
* e o balanceamento sao testados e organizados durante a busca e insercao num mesmo momento.
* para que todo o processo seja efetuado em O(log(n)) passos. Algoritmo demonstrado no livro:
* SZWARCFITER,Jaime Luiz.Estruturas de Dados e seus Algoritmos.(1994).LTC, 2 Ed.*/
public boolean inserirElemento(int x){
pt = new No(x);
if (raiz == null){
raiz = pt;}//se arvore vazia, insere na raiz
else{
pt = raiz; //pt recebe raiz (para percurso na arvore)
insAVL(x,pt,false);
}
System.out.println(exibirArvorePreOrdem());
return true;
}
//Metodo privado recursivo que auxilia o metodo inserirElemento() para insercao e balanceamnto
private boolean insAVL(int x,No pt,boolean h){
t = h;
if (pt == null){//No alocado no espaco vazio
pt = new No(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) caso1(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) caso2(pt,t); //rebalanceamento (rotacao esquerda)
}
}
}
return true;
}
/*========================================================================================*/
//Metodo de remocao de um elemento com chave x na arvore
public boolean removerElemento(int x){
if (raiz == null){return false;}//arvore vazia
else{
pt = raiz;//no de percurso
remAVL(x,pt,false);
}
System.out.println(exibirArvorePreOrdem());
return true;
}
//Metodo auxiliar para remocao do no x e balanceamento da arvore
public boolean remAVL(int x,No pt,boolean h){
t=h;
if (pt == null){return false;}//nao achou
else{
if (x == pt.info ){//achou
//*******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)caso2(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) caso1(pt,t); //rebalanceamento (rotacao direita)
}
}
}
}
local=0; //sem valor, ao final da execucao
return true;
}
/*========================================================================================*/
/*Metodo que exibe a arvore em pre ordem
na representacao de parenteses aninhados*/
public String exibirArvorePreOrdem(){
return super.exibirArvorePreOrdem();
}
/*========================================================================================*/
/*Metodo que exibe o balanco da arvore em pre ordem
na representacao de parenteses aninhados*/
public String balanco(){
if (raiz == null)return "";
No p = this.raiz; // recebe o no raiz
print = print + Integer.toString(p.balanco)+ " ";
if (p.esq != null){print = print + "(" + balanco(p.esq)+")";}
if (p.dir != null){print = print + "(" + balanco(p.dir)+ ")";}
String pr =print;
print = " ";
return pr;
}
/*========================================================================================*/
/*Metodo que exibe o balanco da arvore em pre ordem (auxiliar para
recursao na representacao de parenteses aninhados*/
private String balanco(No p){
print = Integer.toString(p.balanco)+ " ";
if (p.esq != null){print = print + "( " + balanco(p.esq) + ")";}
if (p.dir != null){print = print + "(" + balanco(p.dir)+ ")";}
String pr = print;
print = " ";
return pr;
}
}
