如何在树 B 中进行函数搜索，return 节点的索引，必须在其中找到键？

Question

我正在尝试自己实现一个树B，insert_order可以工作，功能除法，但是搜索功能，我不知道如何实现它给我左边节点键的子节点。

这个是节点找的方法，如果没找到就returns -1，但是我要return连续键的位置（如果是找不到它，它是叶子）。

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);
    }
}

该方法在数组中有序插入，移动一个位置使数组重新排序

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

这是一个向树中插入key的方法，如果是叶子就调用insert_order，但是如果不是叶子就递归调用直到到达叶子，如果到达叶子它应该调用 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;
    }
}

我留下了所有代码，以防有人想更详细地查看它

package ARBOL_B;

public class 树B {

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);
    }
}

/* 该方法在数组中有序插入，移动一个位置以重新排列数组 */ 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);
}

} 这是 class 节点。

public class 诺多{

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

} 我希望你能帮助我，我不知道如何让我找到 return 正确的密钥，如果有人有更好的方法，我将感谢你的支持，在此先感谢。 :)

Answer 1

我设法实现了搜索方法，我的解决方案是 return 当前节点，而不是位置，我做了一个 class 将节点和键数组中的位置打包, 就是找不到。

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);
    }
}

问题是找到当前节点，认为它会 return child 的位置，而实际上 return 相同的节点

如何在树 B 中进行函数搜索，return 节点的索引，必须在其中找到键？

How do I make my function search in a tree B, return the index of a node, in which the key must be found?

java

data-structures

b-tree