Problemas de implementação de árvores B e AVL

0 respostas
nois_159
Boa tarde, estou querendo tirar uma dúvida de dois trabalhos que fiz, e não tive sucesso, no caso eles apresentavam erros, e eu acabei não conseguindo identificar. Mais isso já passou, e estou querendo só tirar essa dúvida o do por que acontece isso, no caso, vou colocar até as alterações que mexi por esses dias, pra ver se conseguia algo, mais, me deu muito trabalho. Então o primeiro que estarei passando é a Árvore AVL, no caso, do jeito que fiz ele, de primeiro, ele roda de boa, se eu colocar as variáveis fixas, mais, passou da 7 inserção ele acusa um erro, mesmo eu colocando o vetor de 256 posições. Porque acontece esse tipo de coisa, e quando eu coloco pra poder fazer a chamada, pra ir inserindo um por vez, pra fazer o tamanho do vetor e perguntando as variáveis está boa, mais o importante que é o balanceamento, nem sinal. Por favor, dá uma olhada nessas implementações, eu tenho que pegar esses macetes logo.. só dou trabalho mesmo.. rsrs
public class AvlNode {


        protected int height;      
        protected int key;
        protected AvlNode left, right;

       public AvlNode ( int Elemento ) {
           this( Elemento, null, null );
       }

       public AvlNode ( int theElement, AvlNode lt, AvlNode rt ) {
           key = theElement;
           left = lt;
           right = rt;
           height = 0;
       }
   }
public class AvlTree {
    /*private static Object arvore;*/
    private static Object t;

        private AvlNode root = null;

        public AvlTree( ) {
            root = null;
        }

        public void clear() {
            root = null;
        }
        public boolean isEmpty() {
            return root == null;
        }

        public AvlNode getRootNode (){
            return root;
        }

        /** Retorna a altura da árvore */
        private static int height( AvlNode t ) {
          return t == null ? -1 : t.height;
        }

         /**
         * Retorna o maior valor ente lhs e rhs.
         */
        private static int max( int lhs, int rhs ) {
            return lhs > rhs ? lhs : rhs;
        }

        /** Retorna o fator de balanceamento da árvore com raiz t */
        private int getFactor (AvlNode t) {
            return height( t.left ) - height( t.right );
        }

        public boolean insert (int x) {
            root = inserirNo (x, root);
            return true;
        }

        private AvlNode inserirNo (int x, AvlNode t) {
            if( t == null )
                t = new AvlNode( x, null, null );
            else if( x<t.key ) t.left = inserirNo( x, t.left );
            else if( x>t.key) t.right = inserirNo( x, t.right );
            t = balance (t);
            return t;
        }
        /** Faz a chamada da rotação dupla direita e esquerda*/
        public AvlNode balance (AvlNode t) {
            if ( getFactor(t) == 2 ) {
                    if (getFactor (t.left)>0) t = doRightRotation( t );
                    else t = doDoubleRightRotation( t );
            }
            else if ( getFactor(t) == -2 ) {
                    if ( getFactor(t.right)<0 ) t = doLeftRotation( t );
                    else t = doDoubleLeftRotation( t );
            }
            t.height = max( height( t.left ), height( t.right ) ) + 1;
            return t;
        }

        /** Faz a rotação simples a direita */
        private static AvlNode doRightRotation( AvlNode r2 ) {
            AvlNode r1 = r2.left;
            r2.left = r1.right;
            r1.right = r2;
            r2.height = max( height( r2.left ), height( r2.right ) ) + 1;
            r1.height = max( height( r1.left ), r2.height ) + 1;
            return r1;
        }

        /** Faz a rotação simples à esquerda */
        private static AvlNode doLeftRotation( AvlNode r1 ) {
            AvlNode r2 = r1.right;
            r1.right = r2.left;
            r2.left = r1;
            r1.height = max( height( r1.left ), height( r1.right ) ) + 1;
            r2.height = max( height( r2.right ), r1.height ) + 1;
            return r2;
        }

        public AvlNode search(int el) {
            return search(root,el);
        }
        protected AvlNode search(AvlNode p, int el) {
            while (p != null) {
                /* se valor procurado == chave do nó retorna referência ao nó */
                if (el==p.key) return p;
                /* se valor procurado < chave do nó, procurar na sub-árvore esquerda deste nó */
                else if (el<p.key) p = p.left;
                /* se valor procurado > chave do nó, procurar na sub-árvore direita deste nó */
                else p = p.right;
            }
            // caso chave não foi achada, retorna null
            return null;
        }

        public void inorder() {
            inorder(root);
        }
        protected void inorder(AvlNode p) {
            if (p != null) {
                 inorder(p.left);
                 System.out.print(p.key+" - ");
                 inorder(p.right);
            }
        }

        public void preorder() {
            preorder(root);
        }
        protected void preorder(AvlNode p) {
            if (p != null) {
                 System.out.print(p.key + " ");
                 preorder(p.left);
                 preorder(p.right);
            }
        }

        public void postorder() {
            postorder(root);
        }

        protected void postorder(AvlNode p) {
            if (p != null) {
                 postorder(p.left);
                 postorder(p.right);
                 System.out.print(p.key + " ");
            }
        }

    protected AvlNode searchFather (int el) {
        AvlNode p = root;
        AvlNode prev = null;
        while (p != null && !(p.key==el)) {  // acha o nó p com a chave el
            prev = p;
            if (p.key<el)
                  p = p.right;
            else p = p.left;
        }
        if (p!=null && p.key==el) return prev;
        return null;
    }

   
    public void displayTree() {
     if (isEmpty()){
         System.out.println("Árvore vazia!");
         return;
     }
     String separator = String.valueOf("  |____ ");
     System.out.println(this.root.key+"("+root.height+")");
     displaySubTree(root.left,  separator);
     displaySubTree(root.right, separator);
 }
 private void displaySubTree(AvlNode node, String separator) {

     if (node != null) {

         AvlNode father = this.searchFather(node.key);
         if (node.equals(father.left) == true) {
             System.out.println(separator+node.key+"("+node.height+")"+" (ESQ)");
         }else{
             System.out.println(separator+node.key+"("+node.height+")"+" (DIR)");
         }
         displaySubTree(node.left,  "     "+separator);
         displaySubTree(node.right, "     "+separator);
     }
 }

        public static void main (String args[]){
            //AvlTree inserirNo = new AvlTree();

            //ArvoreAVL arvore = new ArvoreAVL();
            Scanner leia = new Scanner (System.in);
            int n;
            int valor;
            int bal;


            System.out.println("\n Digite a qtdade de posições:");
            n=leia.nextInt();

            System.out.println("\n Digite os valores as serem inseridos:");
            for(int i =1;i<=n;i++){
                valor=leia.nextInt();
                t.inserirNo( valor );

            }
/*
            t.insert(65);
            t.insert(98);
            t.insert(100);
            t.insert(27);
            t.insert(76);
            t.insert(28);
            t.insert(10);
            t.displayTree();*/
        }


    private AvlNode doDoubleRightRotation(AvlNode t) {
       throw new UnsupportedOperationException("Not yet implemented");
    }

    private AvlNode doDoubleLeftRotation(AvlNode t) {
        throw new UnsupportedOperationException("Not yet implemented");
    }
}

Agora na minha árvore B é questão de implementação, tipo, na classe BSTNode tem o erro, e o netbeans pede pra criar um contrutor BSTNode(int) dentro do meu pacote. Mais ai que está, eu já tentei criar alguns construtor, mais saia desse erro e criava outro.. será que minha implementação está errada?? Só queria que alguém pudesse me ajudar a entender essa minha implementação de árvore B.

class BSTNode {
    private BSTNode root;
    private BSTNode left;
    private int key;
    private BSTNode right;


    public boolean insert(int el) {
        BSTNode p = root, prev = null;
        // caso o valor já exista na árvore, não inserir e retornar false
        if (search(el)!=null) return false;
        // procurando um lugar para colocar o novo nó
        while (p != null) {
            prev = p;
            if (el<p.key) p = p.left;
            else p = p.right;

        }
        // se árvore vazia
        if (root == null)  root = new BSTNode(el);
        else if (prev.key<el) prev.right = new BSTNode(el);
        else prev.left = new BSTNode(el);
        return true;
    }

    public BSTNode search(int el) {
        return search(root,el);
    }
    protected BSTNode search(BSTNode p, int el) {
        while (p != null) {
            /* se valor procurado == chave do nó retorna referência ao nó */
            if (el==p.key) return p;
            /* se valor procurado < chave do nó, procurar na sub-árvore esquerda deste nó */
            else if (el<p.key) p = p.left;
            /* se valor procurado > chave do nó, procurar na sub-árvore direita deste nó */
            else p = p.right;
        }
        // caso chave não foi achada, retorna null
        return null;
    }

    /* métodos de busca recursivos */
    public BSTNode searchR (int el) {
        return searchR(root,el);
    }

    protected BSTNode searchR(BSTNode p, int el) {
        if (p==null || el==p.key) return p;
        else if (el<p.key) return searchR (p.left, el);
        else return searchR (p.right, el);
    }

    protected BSTNode searchFather (int el) {
        BSTNode p = root;
        BSTNode prev = null;
        while (p != null && !(p.key==el)) {  // acha o nó p com a chave el
            prev = p;
            if (p.key<el)
                  p = p.right;
            else p = p.left;
        }
        if (p!=null && p.key==el) return prev;
        return null;
    }


    public void inorder() {
        inorder(root);
    }
    protected void inorder(BSTNode p) {
        if (p != null) {
             inorder(p.left);
             System.out.print(p.key + " ");
             inorder(p.right);
        }
    }

    public void preorder() {
        preorder(root);
    }
    protected void preorder(BSTNode p) {
        if (p != null) {
             System.out.print(p.key + " ");
             preorder(p.left);
             preorder(p.right);
        }
    }

    public void postorder() {
        postorder(root);
    }

    protected void postorder(BSTNode p) {
        if (p != null) {
             postorder(p.left);
             postorder(p.right);
             System.out.print(p.key + " ");
        }
    }
    public void deleteByCopying(int el) {
        BSTNode node = null, father = null;
        node = search (el) ; // procura nó a ser deletado
        if (node != null && node.key==el) {
             if (node!=root) father = searchFather (el);  // procura pai do nó a ser deletado
             if (node.right == null){             // nó não tem filho direito (segundo caso);
                  if (node==root) root= node.left;
                  else if (father.left == node) father.left = node.left;
                  else father.right = node.left;
             }
             else if (node.left == null) {         // nó não tem filho esquerdo (segundo caso)
                  if (node==root) root= node.right;
                  else if (father.left == node) father.left = node.right;
                  else father.right = node.right;
             }
             else {     // nó tem ambos os filhos: fazer remoção por cópia
                  BSTNode tmp = node.left;       // 1. pegando sub-arvore esquerda
                  while (tmp.right != null) {    // 2. acha a posicao mais a direita
                      tmp = tmp.right;           //    da sub-árvore esquerda do nó
                  }
                  deleteByCopying (tmp.key);     // remove por copia o nó que possui o maior  valor
                                                 // da sub-arvore esquerda do nó a ser deletado
                  node.key = tmp.key;             // copia o valor da chave do maior nó
                                                  // da subárvore esquerda
             }
        }
        else if (root != null)
             System.out.println("el " + el + " is not in the tree");
        else System.out.println("the tree is empty");
    }

    public void deleteByMerging(int el) {
        BSTNode tmp = null, node = null,father = null;
        node = search (el) ; // procura nó a ser deletado
        if (node != null && node.key==el) {
             if (node!=root) father = searchFather (el);  // procura pai do nó a ser deletado
             if (node.right == null){     // nó não tem filho direito (segundo caso);
                  if (root==node) root=node.left;
                  else if (father.left == node) father.left = node.left;
                  else father.right = node.left;
             }
             else if (node.left == null) {  // nó não tem filho esquerdo (segundo caso)
                  if (root==node) root=node.right;
                  else if (father.left == node) father.left = node.right;
                  else father.right = node.right;
             }
             else {  // se tem dois filhos, faz deleção por fusão
                  tmp = node.left;           // pega sub-arvore esquerda
                  while (tmp.right != null) //  pega filho mais a direita da sub-arvore esquerda
                      tmp = tmp.right;
                  tmp.right = node.right;   // o filho mais a direita da sub-arvore esquerda passa a ter
                                           // como filho direito o filho direito do nó a ser deletado
                  if (root==node)
                      root = node.left;
                  else if (father.left == node)
                      father.left = node.left;
                  else father.right = node.left;
             }
        }
        else if (root != null)
             System.out.println("el " + el + " is not in the tree");
        else System.out.println("the tree is empty");
    }

    public int max (int i, int j){
        return i>j?i:j;
    }

    /*void inserirNo(int valor, Object raiz) {
    //public void inserirNo( int valor ){   
    if( raiz == null )   
    {   
    raiz = new No( valor );   
    }   
    else   
    {   
    raiz.insert( valor );   
    }   
    // }
    }*/


}
public class Main {
     public static void main(String args[]){
       // (vermelho) leitura e inserção de elementos
        BSTNode arvore = new BSTNode();
        Scanner leia = new Scanner (System.in);
        int n;
        int valor;
        int bal;

        System.out.println("\n Digite a qtdade de posições:");
        n=leia.nextInt();

        System.out.println("\n Digite os valores as serem inseridos:");
        for(int i =1;i<=n;i++)
        {
        valor=leia.nextInt();
        arvore.insert( valor );
        }
         /*BST b = new BST();
         b.insert(5);
         
         b.displayTree();
         System.out.print("\n\nEM-ORDEM: ");
         b.inorder();
         System.out.print("\nPOS-ORDEM: ");
         b.postorder();
         System.out.print("\nPRE-ORDERM: ");
         b.preorder();
         System.out.println("\n");*/
     }
}

public class BST {
    protected BSTNode root = null;
    private Object raiz;

    public BST() {
    }
    public void clear() {
        root = null;
    }
    public boolean isEmpty() {
        return root == null;
    }

    public BSTNode getRootNode (){
        return root;
    }
}


    /*//Criando metodos pelo main, pela duvida peguei pela correcao do programa
    void displayTree() {
    throw new UnsupportedOperationException("Not yet implemented");
    }

    void inorder() {
    throw new UnsupportedOperationException("Not yet implemented");
    }

    void postorder() {
    throw new UnsupportedOperationException("Not yet implemented");
    }

    void preorder() {
    throw new UnsupportedOperationException("Not yet implemented");
    }

    void insert(int i) {
    //   if( raiz == null ){
    //     raiz = new No(valor);
    //}else{
    // raiz.inserir(valor);
    //}
    //}
    throw new UnsupportedOperationException("Not yet implemented");
    }

    }*/

Muito obrigado pela paciência por lerem meus erros e tentar me ajudar!
Inté mais Ficam com DEUS!!

Criado 1 de julho de 2010
Respostas 0
Participantes 1