1. Este site usa cookies. Ao continuar a usar este site está a concordar com o nosso uso de cookies. Saber Mais.

Arvores de espalhamento

Discussão em 'Programação' iniciada por DJS, 14 de Abril de 2008. (Respostas: 3; Visualizações: 884)

  1. DJS

    DJS Power Member

    Boas,

    Estou a implementar um programa em java que guarda inteiros numa arvore de espalhamento mas estou com um problema na minha função splay.

    Quando adiciono o 2º elemento dá-me nullpointer exception.

    A parte do main, remove e insert afins está bem implementada pois já o fiz com outras arvores. O problema é mesmo quando faço a rotação na inserção do segundo elemento.

    segue aqui a dita função:
    Código:
    protected SplayNode splay( int numero, SplayNode raiz ){
            if(raiz==null)
                return new SplayNode(numero);
            if(numero<raiz.data){
                if(raiz.Esquerdo==null){
                    raiz.Esquerdo= new SplayNode(numero);
                    return SimpRotDir(raiz);
                }
                if(numero<raiz.Esquerdo.data){
                    raiz.Esquerdo.Esquerdo=splay(numero,raiz.Esquerdo.Esquerdo);
                    raiz = SimpRotDir(raiz);
                }
                else{
                    raiz.Esquerdo.Direito=splay(numero,raiz.Esquerdo.Direito);
                    raiz.Esquerdo=SimpRotEsq(raiz.Esquerdo);
                }
                return SimpRotDir(raiz);
            }
            else{
                if(raiz.Direito==null){
                    raiz.Direito=new SplayNode(numero);
                    return SimpRotEsq(raiz);
                }
                if(numero>raiz.Direito.data){
                    raiz.Direito.Direito=splay(numero,raiz.Direito.Direito);
                    raiz = SimpRotEsq(raiz);
                }
                else{
                    raiz.Direito.Esquerdo=splay(numero,raiz.Direito.Esquerdo);
                    raiz.Direito=SimpRotDir(raiz.Direito);
                }
                return SimpRotEsq(raiz);
            }
        }
    mais especificamente o problema aparece no:

    Código:
    static private SplayNode SimpRotDir(SplayNode no){
            SplayNode noaux = no.Direito;
            [B][U]no.Direito = noaux.Esquerdo;[/U][/B]
            noaux.Esquerdo = no;
            return noaux;
        }
    Tanto na rotação para a esquerda como para a direita.

    Alguém me pode ajudar a solucionar este problema ?

    Cumps
     
  2. hYpe

    hYpe [email protected] Member

    Assim sem ver com muita atenção (que estou extremamente cansado), quando vais fazer a rotação tens q ver se existe o no.Direito..

    Não sei, n tenho certeza nenhuma do q estou a dizer.
     
  3. DJS

    DJS Power Member

    Já me tinha lembrado disso mas ainda não tive tempo de testar. Daqui a nada ja tento a ver o que dá.

    Cumps
     
  4. DJS

    DJS Power Member

    Já testei a tua opção e basicamente a inserção processa-se bem mas pelo contrário a remoção e dá um belo dum stack overflow.

    Outra duvida que tenho devido às explicações nulas dadas pelos meus professores sobre este assunto é a seguinte:

    Ao fazer o Splay numa arvore de espalhamento o elemento que entra como argumento tem como objectivo ficar na raiz certo?

    Edit:
    Uma outra coisa, esta função é baseada numa presente num livro do sedgwick logo é estranho não funcionar.
     
    Última edição: 14 de Abril de 2008

Partilhar esta Página