java - BTree插入-java
问题描述
我在java中为B-Tree编写了一个插入代码,但是我的树没有正确初始化,我不知道问题是什么
例如 - 输入:ABCDGHKMRWZ
想要的输出 -
D
/ \
/ \
/ \
B HM
/ \ /|\
/ \ / | \
A C G K RWZ
D 是 B 和 HM 的父级,HM 和 B 是 D 的子级,依此类推..
但我收到了以下输出:
D
/ \
/ \
/ \
/ \
/ \
B HM
/|\ \ /|\
/ | \ \ / | \
A C G K G K RWZ
当 K 和 G 是 B 和 HM 的子代时,B 是 G 的父代,HM 是 K 的父代。
这是我的代码:
public void insert(String key){
//this method finds the node to be inserted as
//it goes through this starting at root node.
BTreeNode r = this.root;
//if it is full
if(r.count == 2*order - 1)
{
//create a new empty node
BTreeNode s = new BTreeNode(order,null);
s.leaf = false;
s.count = 0;
s.child[0] = r;
this.root = s;
split(s,0,r); //split root
nonfullInsert(s, key); //call insert method
}
else
nonfullInsert(r,key); //if its not full just insert it
}
public void split(BTreeNode s, int i, BTreeNode r){
BTreeNode z = new BTreeNode(this.order,null);
z.leaf = r.leaf; //set boolean to be the same as y
for(int j = 0; j < this.order - 1; j++){
z.key[j] = r.key[j+this.order];
z.count++;
}
// if not leaf we have to reassign child nodes.
if(!r.leaf){
for(int k = 0; k < this.order; k++){
z.child[k] = r.child[k+this.order];
}
}
r.count = this.order - 1; //new size of y
// rearranging the child nodes
for(int j = s.count ; j> i ; j--){
s.child[j+1] = s.child[j]; //shift children of x
}
s.child[i+1] = z;
for(int j = s.count; j> i; j--){
s.key[j + 1] = s.key[j]; // shift keys
}
//push the value up into the root.
s.key[i] = r.key[this.order-1];
r.key[this.order-1 ] = "";
for(int j = 0; j < this.order - 1; j++)
r.key[j + this.order] = ""; //'delete' old values
s.count++; //increase count of keys in s
r.parent=s;
z.parent=s;
}
public void nonfullInsert(BTreeNode s, String key){
int i = s.count; //i is number of keys in node x
if(s.leaf){
while(i >= 1 && key.compareTo(s.key[i-1]) < 0){
//shift values to make room for the new one
s.key[i] = s.key[i-1];
i--;
}
s.key[i] = key; //assign the value to the node
s.count++;
}
else{
int j = 0;
while(j < s.count && key.compareTo(s.key[j]) > 0)
j++;
if(s.child[j].count == order*2 - 1){
split(s,j,s.child[j]);
if(key.compareTo(s.key[j]) > 0){
j++;
}
}
nonfullInsert(s.child[j],key);
}
}
非常感谢您的帮助!
解决方案
推荐阅读
- php - 警告问题:rawurlencode() 期望参数 1 是字符串,数组中给出
- java - 从终端或命令提示符(如 git 或 maven 或 java 或 javac)运行(不是在开发期间而是在生产中)java 应用程序
- java - 编写 Avro 生产者时是否需要单独的密钥架构(字段架构除外)?
- matlab - 矩阵 A 的雅可比平面旋转
- java - Android 应用程序已停止
- windows - Windows 致命异常:使用 ssd_mobilenet_v2 量化访问冲突
- java - 如何将提到的 java 对象转换为 java 中的列表对象。java 对象内部有一个列表,其中包含相同类型的对象
- android - 文件中的 Android Studio 错误但项目编译并运行:未解决的参考
- android - 什么是 Unity 2020.1.0b16 Android 支持设置错误:无法找到 untity.exe
- html - 在 HTML5 中使用属性 align 是否合法?