Olá pessoal,
tô querendo implementar uma árvore binária AVL, mas tô com dificuldade de implementar as rotações.
Tenho a implementação da árvore binária funcionando 100%, alguém tem alguma idéia de como implementar as rotações nesta árvore para que ela mantenha-se sempre balanceada?
Código Árvore Binária:
[code]public class Arvore_AVL {
No raiz;
public class No{
int info, fat_bal;
No dir, esq;
public No(int dado){
esq = dir = null;
this.info = dado;
this.fat_bal = 0;
}
public void inserir( int valor ){
if( valor < info ){
if( esq == null ){
esq = new No( valor );
}
else{
esq.inserir( valor );
}
}
else if( valor > info ){
if( dir == null ){
dir = new No( valor );
}
else{
dir.inserir( valor );
}
}
}
}
public Arvore_AVL(){
{
raiz = null;
}
}
public void inserirNo( int valor ){
if( raiz == null )
{
raiz = new No( valor );
}
else
{
raiz.inserir( valor );
}
}
public void preOrdem()
{
preOrdemAjudante( raiz );
}
// Método para percorrer a árvore em pre - ordem
// utiliza a recursão para percorrer os nos da ávore
public void preOrdemAjudante( No no )
{
if( no == null )
return;
System.out.println( no.info + "" );
preOrdemAjudante( no.esq );
preOrdemAjudante( no.dir );
}
public static void main(String args[]){
Arvore_AVL arvore = new Arvore_AVL();
arvore.inserirNo(10);
arvore.inserirNo(20);
arvore.inserirNo(30);
arvore.preOrdem();
}
Eu fiz uma implementação de uma estrutura dessas em JME na minha graduação. Basicamente, o que eu fiz foi sempre que eu fazia uma inserção, eu “subia” na árvore, verificando sempre se os nós estavam balanceados. Você pode fazer isso verificando se o módulo da diferença entre a altura da sub-árvore esquerda com a altura da sub-árvore da direita é menor que 2.
Outra dica: você pode fazer isso numa rotina recursiva.
De boa, mas tem uma coisa.
os nós de uma Árvore AVL guardam tipicamente um fator de balanceamento,
que varia entre -1 0 1.
eu posso ter entendido errado,
mas na árvore apresentada o fator de balanceamento foi substituido por um atributo ‘altura’ que guarda a altura do nó em relação aos folhas. ;x