如何在树 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?
我正在尝试自己实现一个树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 正确的密钥，如果有人有更好的方法，我将感谢你的支持，在此先感谢。 :)
我设法实现了搜索方法，我的解决方案是 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，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 正确的密钥，如果有人有更好的方法，我将感谢你的支持，在此先感谢。 :)
我设法实现了搜索方法，我的解决方案是 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 相同的节点