1
我想在每个节点中使用固定元素的多元素节点在Java中实现Btree。我正在尝试为树插入方法。例如,在我的代码中,每个节点将包含3个元素,每个元素将指向2个子节点(左侧和右侧)。它的工作方式与2,3树类似,但每个节点中元素的数量可能会更多,每个节点具有固定长度的元素。 基本上,当一个节点分裂时,中间元素会得到促进。 此图像显示插入的工作原理:实现具有多元素节点的Btree java
这是我的代码,我写开始做根节点,但我不知道如何使树具有更大的重用插入和分离方法。
public class BTree {
private Node root = null;
int maxElementInNode = 3;
public class Node {
//each node contain 3 elements
Element[] elements;
Element leftParent;
Element rightParent;
public Node(){
}
}
public class Element{
int key;
String rId;
Node leftNode;
Node rightNode;
public Element(int key, String rId){
this.key = key;
this.rId = rId;
}
}
//add new element to tree
public void addElement(int key, String rId){
//add element to root node
if(root == null){
root = new Node();
if (root.elements.length < maxElementInNode){
for(int i = 0; i<root.elements.length;i++){
if(root.elements[i] == null){
root.elements[i] = new Element(key, rId);
Arrays.sort(root.elements);
break;
}
}
//need to split
}else{
root = new Node();
split(root);
}
}
}
public void split(Node nodeToSplit){
if(root.elements == null){
//first element of root = median element of split node
root.elements[0] = nodeToSplit.elements[(maxElementInNode+1)/2];
}
Element[] leftChildNode = new Element[maxElementInNode];
Element[] rightChildNode = new Element[maxElementInNode];
for(int i = 0; i< (maxElementInNode+1)/2;i++){
leftChildNode[i] = nodeToSplit.elements[i];
}
Node left = new Node();
left.rightParent = nodeToSplit.elements[(maxElementInNode+1)/2];
left.elements = leftChildNode;
for(int j = ((maxElementInNode+1)/2)+1; j< maxElementInNode;j++){
int i = 0;
rightChildNode[i] = nodeToSplit.elements[j];
i++;
}
Node right = new Node();
right.elements = rightChildNode;
right.leftParent = nodeToSplit.elements[(maxElementInNode+1)/2];
}
}
后的图像的链接,我会添加它 – c0der
我认为有需要增加功能之前先解决一些基本问题,比如:'Node'字段(元素,leftParent,rightParent)不被使用。您需要使用构造函数或setter来初始化它们。 'Element'(leftNode,rightNode)同样适用。 'addElement'也允许仅向空根添加。 – c0der
谢谢,我只是把图像,我不是很擅长Java,只是做了Java课程的介绍。我在互联网上搜索了一些代码,但它对我没有多大帮助。 –