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