Transformar arvore b em b*

[Seraphan]

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 + " ";
        }
    }
}