I am trying to implement a tree B on my own, the insert_order was working, and the function divide, but the search function, I don't know how to implement it to give me the left child of the node key.
This is the method that the node finds, if it doesn't find it it returns -1, but I want it to return the position of the continuous key (if it can't find it and it's leaf).
public int search(Nodo nodo, int valor){
int i = 0;
while(i < nodo.numKeys && nodo.keys[i] < valor){
i = i + 1;
}
if(i < nodo.numKeys && nodo.keys[i] == valor){
return i;
}
if(nodo.isLeaf()){
return -1;
}else{
return search(nodo.sons[i], valor);
}
}
This method inserts in an orderly way in the array,moves a position to reorder the array
public void insert_order(Nodo nodo, int value, Nodo right_son){
if(estaVacia(nodo.keys)){
nodo.keys[nodo.numKeys] = value;
nodo.sons[1] = right_son;
nodo.numSons++;
}else{
int pivote = 0;
while(pivote < nodo.numKeys&&nodo.keys[pivote] < value){
pivote = pivote + 1;
}
for(int i = nodo.numKeys-1; i >= pivote; --i ){
nodo.keys[i+1] = nodo.keys[i];
}
for(int i = nodo.numSons-1; i >= pivote; --i){
nodo.sons[i+1] = nodo.sons[i];
}
nodo.keys[pivote] = value;
nodo.sons[pivote+1] = right_son;
}
nodo.numKeys++;
if(!nodo.isLeaf()){
nodo.numSons++;
}
}
this is a method that inserts a key into the tree, if it is a leaf it calls insert_order, but if it is not a leaf it calls recursively until reaching a leaf, if it reaches a leaf it should call insert_order.
public Nodo insertion(Nodo nodo, int value){
if(nodo.isLeaf()){
insert_order(nodo, value, null);
}else{
int i = search(nodo,value);
Nodo nuevo = null;
if(i!=-1){//<-- is leaf and return -1 :(
throw new RuntimeException("exist this key");
}else{
//error: Array index of bounds Exception : -1
nuevo = insertion(nodo.sons[i], value);
}
if(nuevo != null){
int pivote = nuevo.keys[0];
insert_order(nodo, pivote, nuevo);
for(int k = 0; k <= nodo.numKeys-1; k++ ){
nodo.keys[k] = nodo.keys[k+1];
}
}
}
if (nodo.numKeys > nodo.degree -1){
Nodo new1 = divide(nodo);
/*
* the root was divided, the new node will be the right child
* and all that remains is to upload the root to the father,
* but since this is the first time, the root will divide and
* redefine the root.
*
* */
if(first_time && new1 != null ){
int pivote1 = new1.keys[0];
Nodo izquierda = nodo;
Nodo new_root = new Nodo(root.degree);
new_root.keys = new int [root.degree];
new_root.sons = new Nodo[root.degree];
insert_order(new_root,pivote1, new1);
root = new_root;
int pivotem = 0;
while(root.keys[pivotem] < pivote1){
pivotem = pivotem + 1;
}
root.sons[pivotem] = izquierda;
for(int k = 0; k <= new1.numKeys-1; k++ ){
new1.keys[k] = new1.keys[k+1];
}
new1.numKeys--;
first_time = false;
}
return new1;
}else{
return null;
}
}
I leave all the code in case someone wants to see it in more detail
package ARBOL_B;
public class treeB {
Nodo root;
public treeB(int grado){
root = new Nodo(grado);
}
public boolean exist(Nodo nodo, int valor){
int i =0;
while(i < nodo.numKeys && nodo.keys[i] < valor){
i = i+1;
}
if(i < nodo.numKeys && nodo.keys[i] == valor){
return true;
}
if(nodo.isLeaf()){
return false;
}else{
return exist(nodo.sons[i], valor);
}
}
/*
This is the method that the node finds, if it doesn't find it it returns -1, but I want it to return the position of the continuous key (if it can't find it and it's leaf).
* */
public int search(Nodo nodo, int valor){
int i = 0;
while(i < nodo.numKeys && nodo.keys[i] < valor){
i = i + 1;
}
if(i < nodo.numKeys && nodo.keys[i] == valor){
return i;
}
if(nodo.isLeaf()){
return -1;
}else{
return search(nodo.sons[i], valor);
}
}
/* This method inserts in an orderly way in the array, moves a position to reorder the array */ public void insert_order(Nodo nodo, int value, Nodo right_son){
if(estaVacia(nodo.keys)){
nodo.keys[nodo.numKeys] = value;
nodo.sons[1] = right_son;
nodo.numSons++;
}else{
int pivote = 0;
while(pivote < nodo.numKeys&&nodo.keys[pivote] < value){
pivote = pivote + 1;
}
for(int i = nodo.numKeys-1; i >= pivote; --i ){
nodo.keys[i+1] = nodo.keys[i];
}
for(int i = nodo.numSons-1; i >= pivote; --i){
nodo.sons[i+1] = nodo.sons[i];
}
nodo.keys[pivote] = value;
nodo.sons[pivote+1] = right_son;
}
nodo.numKeys++;
if(!nodo.isLeaf()){
nodo.numSons++;
}
}
boolean first_time = true;
/*
this is a method that inserts a key into the tree,
if it is a leaf it calls insert_order, but if it is not a leaf it
calls recursively until reaching a leaf, if it reaches a leaf
it should call insert_order
* */
public Nodo insertion(Nodo nodo, int value){
if(nodo.isLeaf()){
insert_order(nodo, value, null);
}else{
int i = search(nodo,value);
Nodo nuevo = null;
if(i!=-1){//<-- is leaf and return -1 :(
throw new RuntimeException("exist this key");
}else{
//error: Array index of bounds Exception : -1
nuevo = insertion(nodo.sons[i], value);
}
if(nuevo != null){
int pivote = nuevo.keys[0];
insert_order(nodo, pivote, nuevo);
for(int k = 0; k <= nodo.numKeys-1; k++ ){
nodo.keys[k] = nodo.keys[k+1];
}
}
}
if (nodo.numKeys > nodo.degree -1){
Nodo new1 = divide(nodo);
/*
* the root was divided, the new node will be the right child
* and all that remains is to upload the root to the father,
* but since this is the first time, the root will divide and
* redefine the root.
*
* */
if(first_time && new1 != null ){
int pivote1 = new1.keys[0];
Nodo izquierda = nodo;
Nodo new_root = new Nodo(root.degree);
new_root.keys = new int [root.degree];
new_root.sons = new Nodo[root.degree];
insert_order(new_root,pivote1, new1);
root = new_root;
int pivotem = 0;
while(root.keys[pivotem] < pivote1){
pivotem = pivotem + 1;
}
root.sons[pivotem] = izquierda;
for(int k = 0; k <= new1.numKeys-1; k++ ){
new1.keys[k] = new1.keys[k+1];
}
new1.numKeys--;
first_time = false;
}
return new1;
}else{
return null;
}
}
public Nodo divide(Nodo nodo){
Nodo new_node = new Nodo(nodo.degree);
new_node.keys = new int[nodo.degree];
new_node.sons = new Nodo[nodo.degree];
for(int i = (int)(Math.ceil(nodo.degree/2)), j = 0; i < nodo.degree; i++, j++){
new_node.keys[j] = nodo.keys[i];
nodo.keys[i] = 0;
if(!nodo.isLeaf()){
new_node.sons[j+1] = nodo.sons[i+1];
nodo.sons[i+1] = null;
}
}
if(nodo.isLeaf()){
nodo.numKeys = (int)(Math.ceil(nodo.degree/2));
new_node.numKeys = nodo.degree - nodo.numKeys;
}
return new_node;
}
public boolean estaVacia(int[] claves){
for(int i = 0; i < root.numKeys; i++){
if(claves[i] != 0){
return false;
}
}
return true;
}
public static String print(int[] list){
String str = "";
for(int i = 0;i < list.length; i++){
str += list[i]+ "; ";
}
return str;
}
public static void printSons(Nodo[] sons){
String str = "";
for(int i = 0; i < sons.length; i ++ ){
if(sons[i] != null)
str += " [ "+print(sons[i].keys)+ " ] , ";
}
System.out.println(str);
}
public static void main(String[] args) {
treeB bb = new treeB(3);
bb.root.keys = new int[3];
bb.root.sons = new Nodo[3];
Nodo nuevo = bb.insertion(bb.root, 3);
System.out.println(print(bb.root.keys));
nuevo = bb.insertion(bb.root, 1);
System.out.println(print(bb.root.keys));
System.out.println(bb.root.numKeys);
System.out.println(bb.root.numSons);
nuevo = bb.insertion(bb.root, 2);
System.out.print(bb.root.numSons+"<");
System.out.print(bb.root.sons[1].numKeys);
nuevo = bb.insertion(bb.root, 4);
System.out.println(print(bb.root.keys));
printSons(bb.root.sons);
}
} And this is the class Node.
public class Nodo {
int degree;
int []keys = new int[degree];// es hasta N-1, pero se necesita un espacio mas
int numKeys = 0;
Nodo[] sons = new Nodo[degree];
int numSons = 0;
public Nodo(int grado){
this.degree = grado;
}
public Nodo(){ }
public boolean isLeaf(){
for(int i = 0 ; i < this.numSons; i++){
if(this.sons[i] != null){
return false;
}
}
return true;
}
} I hope you can help me, I do not know how to get me to return the right key, and if someone has a better way of doing it I would appreciate your support, Thanks in advance. :)
I managed to implement the search method, my solution was to return the current Node, instead of a position, I made a class that packed the Node and the position in the key array, that is if it can't find it.
public wrapp search_2(Node node, int valor){
wrapp em;
int i = 0;
while(i < node.numKeys && node.keys[i] < valor){
i = i + 1;
}
if(i < node.numKeys && node.keys[i] == valor){
em = new wrapp(null,-1);
return em;
}
if(node.isLeaf()){
em = new wrapp(node,i);
return em;
}else{
return search_2(node.sons[i], valor);
}
}
The problem was finding the current node, thinking that it would return the position of the child,when in reality it would be much easier to return the same node