Ir ao conteúdo
  • Cadastre-se
Entre para seguir isso  
InluxBDX

Avl recursão

Recommended Posts

Boa noite pessoa,

 

Estou implementando uma AVL, utilizando um código de árvores binárias de busca que o professor disponibilizou. Basicamente, o que tenho que fazer é verificar se o nó inserido está balanceamento, dentro das propriedades de uma AVL, e caso positivo, percorrer a árvore recursivamente, procurando degenerações na mesma.

 

Este procedimento, não estou conseguindo implementar de forma que após a inserção do nó (novo valor)  ele verifique se toda a árvore está balanceada.


    

 */ Este é o método de inserção. Nele, é verificado se o valor é menor ou maior, e então é chamado outros dois métodos que efetivamente efetuam a inserção na árvore.
    public void inserir(int novoValor) {
                     
        if(novoValor <= valor) {
            inserirNaSubArvoreEsquerda(novoValor);
        }
        else {
            inserirNaSubArvoreDireita(novoValor);
        }
        altura = 1 + Math.max(alturaSubEsquerda(), alturaSubDireita());    
        
        balanceamento = getBalanceamento(this);
        
        //if(balanceamento>-1 && balanceamento <1)
        //        balanceamento=getBalanceamento(ancestral);
        
        //Left-Left
        if(balanceamento > 1 && valor < subArvoreEsquerda.valor) {
            right_rotate(this);
          }
     
        //Right-Right
        if(balanceamento < -1 && valor > subArvoreDireita.valor) {
            left_rotate(this);
        }
     
        //left-right
        if(balanceamento > 1 && valor > subArvoreEsquerda.valor) {
            left_rotate(subArvoreEsquerda);
            right_rotate(this);
        }
     
        //right-left
        if(balanceamento < -1 && valor < subArvoreDireita.valor) {
            right_rotate(subArvoreDireita);
            left_rotate(this);
        }
        
        
        
    }


private void inserirNaSubArvoreEsquerda(int valor) {
        if(subArvoreEsquerda == null) {
            subArvoreEsquerda = new NoArvoreBinaria(valor, this);
        }
        else {
            subArvoreEsquerda.inserir(valor);    
        }        
    }
    
    
    /*
     * Metodo auxiliar que permite adicionar um novo 
     * elemento na sub-arvore da direita.
     
     */
    
    private void inserirNaSubArvoreDireita(int valor) {
        if(subArvoreDireita == null) {
            subArvoreDireita = new NoArvoreBinaria(valor, this);
         
        }
        else {
            subArvoreDireita.inserir(valor);
        }         
    }

 

Este é o método que criei para retornar o valor do fator de balanceamento:

 

public int getBalanceamento(NoArvoreBinaria no){
            
            if(no==null)
                return 0;
        
            if(no.balanceamento==0)
                return getBalanceamento(no.ancestral);
            
            
            return alturaSubEsquerda() - alturaSubEsquerda();
            
    }

 

Alguém poderia me ajudar a melhorar esse códig? Estou parado nele já algum tempo, e não consigo prosseguir. Caso necessário, posso disponibilizar todo o fonte com os testes também.
    
    

Compartilhar este post


Link para o post
Compartilhar em outros sites

Crie uma conta ou entre para comentar

Você precisar ser um membro para fazer um comentário

Criar uma conta

Crie uma nova conta em nossa comunidade. É fácil!

Crie uma nova conta

Entrar

Já tem uma conta? Faça o login.

Entrar agora
Entre para seguir isso  





Sobre o Clube do Hardware

No ar desde 1996, o Clube do Hardware é uma das maiores, mais antigas e mais respeitadas publicações sobre tecnologia do Brasil. Leia mais

Direitos autorais

Não permitimos a cópia ou reprodução do conteúdo do nosso site, fórum, newsletters e redes sociais, mesmo citando-se a fonte. Leia mais

×