Ir ao conteúdo
  • Cadastre-se
Seraphan

Transformar arvore b em b*

Recommended Posts

Pessoal eu tenho de fazer um algoritmo em Java onde seja efetuado o procedimento da arvore B*, já consegui fazer o código da arvore B, funcionando, mas não estou conseguindo fazer a mudança para a arvore B*, alguém pode me dar uma mão.

O código esta deste jeito.


package btree;

import btreel.exceptions.DuplicateException;
import btreel.exceptions.ChaveNotFoundException;

public class BTree {

    private No raiz = null;
    private int M = 4; //ordem da árvore, ou seja, número maximo de subarvores de um nó
    private int altura = 0;

 public void insere(int chave) throws DuplicateException {
        if (raiz == null) {
            raiz = new No();
            this.altura++;
        }
        No folha = procuraFolha(chave);// encontre um nó folha para inserir K;
        Entrada posicao,novaEntrada=null;
        No novo=null;
        boolean sair = false;
        while (!sair) {
            posicao = folha.localizaPosicao(chave); //encontre uma posição apropriada no vetor de chaves para K;
            if (novo == null) 
                novaEntrada = new Entrada(chave); //se não, cria nova entrada sem filhos
            else
                novo.pai = folha;//vai colocar a entrada na folha e o novo já está dependurado na entrada então muda o pai do novo
            
            if (!folha.estaCheio()) //se (nó não está cheio) então
            {
                folha.insereChave(posicao, novaEntrada);// insira K e aumente a quantidade de chaves no nó;
                sair = true;
            } 
            else //nó está cheio
            {
                folha.insereChave(posicao, novaEntrada);
                novo = folha.divideNo(chave);   
                novo.folha = folha.folha;//se folha é folha então novo tbém será...
                if (folha.pai != null) {
                    chave = folha.ultimaEntrada().chave; // K = ultima chave de nó1;
                    novaEntrada = folha.ultimaEntrada();//nova entrada que ira subir
                    folha.ultimaEntrada().anterior.proximo = null;//a qual é retirada de nó1 
                    folha.nroChaves--;                                
                    folha = folha.pai;//continua o processo no proximo nível
                    
                } else // a folha era a raiz
                {
                    raiz = new No();//                crie uma nova raiz 
                    novo.pai = raiz;//como ascendente de nó1 e nó2;
                    folha.pai=raiz;
                    raiz.entradas = folha.ultimaEntrada();
                    raiz.entradas.anterior.proximo = null;//tira a chave do no1
                    folha.nroChaves--;
                    raiz.inicial = folha;//                coloque K e ponteiros para nó1 e nó2 na raiz ;
                    raiz.entradas.subarvore=novo;
                    raiz.folha = false;
                    raiz.nroChaves = 1;//e ajuste sua quantidade de chaves para 1
                    this.altura++;
                    sair = true; //                retorne;
               }
            }
        }
    }

    private No procuraFolha(int chave) throws DuplicateException {
        No auxNo = raiz;
        Entrada auxEntrada;
        if (raiz != null) {
            while (auxNo.folha == false) {
                if (auxNo.entradas != null && chave < auxNo.entradas.chave) // testa a cada nó 
                {
                    auxNo = auxNo.inicial; // pega a primeira subárvore à esquerda
                } else {
                    auxEntrada = auxNo.entradas;
                    while (auxEntrada != null && chave > auxEntrada.chave) {
                        if (!auxNo.chavePertenceNo(chave)) {
                        auxNo = auxEntrada.subarvore; //marca a proxima subarvore que pode vir a ser explorada
                        auxEntrada = auxEntrada.proximo;
                        }
                        else
                            throw new DuplicateException(Integer.toString(chave));
                    }
                }
            }
        }
        return auxNo;
    }

        @Override
    public String toString() {
        int nivel=0;
        String texto="";
        while (nivel <= this.altura)
        {
            nivel++;
            texto += percursoNivel(raiz, new String(), nivel) + "\n";
        }
        return texto;
    }
    
    public String percursoNivel(No raiz, String texto, int nivel) {
        if (raiz != null) {
            if (this.altura == nivel)
                texto = texto.concat(raiz.toString() + ' ');
            texto = percursoNivel(raiz.inicial, texto, nivel + 1);
            Entrada aux = raiz.entradas;
            while (aux != null) {
                texto = percursoNivel(aux.subarvore, texto, nivel + 1);
                aux = aux.proximo;
            }
        }
        return texto;
    }

    public String pre(No raiz, String texto) {
        if (raiz != null) {
            texto = texto.concat(raiz.toString() + ' ');
            texto = pre(raiz.inicial, texto);
            Entrada aux = raiz.entradas;
            while (aux != null) {
                texto = pre(aux.subarvore, texto);
                aux = aux.proximo;
            }
        }
        return texto;
    }

    private class No {
        public No inicial;//primeira subarvore do no, a esquerda da 1a. chave
        public Entrada entradas; //lista de chaves com as subarvores e
        public boolean folha;
        public int nroChaves;
        public No pai; //guarda o ascendente do nó
        public No() {
            folha = true;
        }
        public boolean estaCheio() {
            if (this.nroChaves == M - 1) 
                return true;
            else 
                return false;
        }
        private boolean chavePertenceNo(int chave) {
            Entrada auxEntrada = this.entradas;
            while (auxEntrada != null && chave != auxEntrada.chave) {
                auxEntrada = auxEntrada.proximo;
            }
            if (auxEntrada == null) 
                return false;
             else 
                return true;
        }
          //   encontre uma posição apropriada no vetor de chaves para K;
        public Entrada localizaPosicao(int chave)  throws DuplicateException {
            Entrada auxEntradaAnterior = null;
            Entrada auxEntrada = this.entradas;
            while (auxEntrada != null && chave > auxEntrada.chave && chave != auxEntrada.chave) {
                auxEntradaAnterior = auxEntrada;
                auxEntrada = auxEntrada.proximo;
            }
            if (auxEntrada != null && chave == auxEntrada.chave)
                throw new DuplicateException(Integer.toString(chave));
            return auxEntradaAnterior;
              //se auxEntradaAnterior for nulo, deve inserir na cabeça da lista, inicial
              //se nao deve-se inserir depois do auxEntradaAnterior
        }
             //se posicao for nulo, deve inserir na cabeça da lista, inicial
             //se nao deve-se inserir depois do posicao  
        public Entrada insereChave(Entrada posicao,  Entrada novo)
        {
            if (posicao == null)//inserir no inicio da lista
            {
                novo.proximo = this.entradas;
                novo.anterior=null;
                if (this.entradas != null)
                    this.entradas.anterior=novo;
                this.entradas = novo;          
            }
            else
            {
                novo.proximo = posicao.proximo;
                novo.anterior = posicao;
                if(posicao.proximo!=null)
                     posicao.proximo.anterior=novo;
                posicao.proximo=novo;
            }
            this.nroChaves++;
            return novo;
        }
//            divida o nó em nó1 e nó2; //nó1 == nó, nó2 é novo
//            distribua as chaves e os ponteiros igualmente entre nó1 e nó2
//            inicialize apropriadamente sua quantidades de chaves
    public No divideNo(int chave)
    {
        No novo = new No();
        int cont = 1;
        Entrada auxEntrada = this.entradas;
        while (cont < M/2+M%2) // pára na chave que vai subir
        {
            auxEntrada = auxEntrada.proximo;
            cont++;
        }
        novo.entradas = auxEntrada.proximo; //inicio do no2
        if(auxEntrada.subarvore!= null)
        {
        novo.inicial = auxEntrada.subarvore; //se existia alguma coisa no nó que vai subir, guarda
        novo.inicial.pai = novo;//muda o pai do novo guardado
        }
        //atualiza o pai de todas as subarvores do novo
        Entrada aux = novo.entradas;
        while (aux != novo.ultimaEntrada())//nao pode comparar até porque pode haver subarvores do meio do nó que são nulas
        {
            if (aux.subarvore != null)
                aux.subarvore.pai = novo;
            aux = aux.proximo;
        }
        if (aux.subarvore != null) //faz para o última nó
                aux.subarvore.pai = novo;
        auxEntrada.subarvore=novo;//dependura o novo nó no que já existia
        novo.pai=this;
        auxEntrada.proximo.anterior = null;//atualiza anterior do inicio do no2
        auxEntrada.proximo= null; //termino do no1
        novo.nroChaves = this.nroChaves - cont;
        this.nroChaves = cont;
        return novo;
    }
        @Override
        public String toString() {
            Entrada aux = this.entradas;
            String chaves="(";
            if (this.pai != null)
                chaves+=this.pai.entradas.chave;
            else
                chaves+="sem pai";
            chaves +=")";
            chaves += "{"+this.nroChaves+"} "+this.folha+"-";
            if (this.inicial != null)
                chaves+=this.inicial.entradas.chave+"-";
            else
                chaves+="sem inicial-";
            chaves +="[";
            while (aux != null)
            {
                chaves = chaves + aux.toString();
                aux = aux.proximo;
            }
               chaves += "]";
            return chaves;
        }

        private Entrada ultimaEntrada() {
            Entrada aux=this.entradas;
            while (aux.proximo != null)
                aux = aux.proximo;
            return aux;
        }
    }  
    
    private class Entrada {
        public int chave;
        public Entrada proximo, anterior;
        public No subarvore;
        public Entrada(int chave) {
            this.chave = chave;
        }
        @Override
        public String toString() {
            return chave + " ";
        }
    }
}

 

Editado por Seraphan

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





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

×