我正在尝试用Java实现一个具有多元素节点的Btree,每个节点中都有固定元素。我正在尝试为树创建一个插入方法。
例如,在我的代码中,每个节点将包含 3 个元素,每个元素将指向 2 个子节点(左和右)。它的工作原理与 2,3 树类似,但每个节点中的元素数量可能要大得多,并且每个节点都有固定长度的元素。 基本上,当节点 split 时,中间元素将得到提升。 此图显示了插入件的工作原理:
这是我的代码,我正在编写开始创建根节点,但我不知道如何通过重用插入和拆分方法来使树更大。
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];
}
}
最佳答案
要回答评论中的问题,请参阅以下修改后的 Element
类:
public class Element{
//you need a way to initialize fields. For this use a constructor,
//a setter, or both
private int key;
private String rId;
private Node leftNode;
private Node rightNode;
//if all fields are know when constructing the object, you can do it
//in the constructor
public Element(int key, String rId, Node leftNode, Node rightNode) {
this.key = key;
this.rId = rId;
this.leftNode = leftNode;
this.rightNode = rightNode;
}
public Element(int key, String rId){
this.key = key;
this.rId = rId;
}
//alternatively, or in addition, you can use setters to set fields,
//and getters to retrieve thier values (remove unneeded setters / getters)
public int getKey() {
return key;
}
public String getrId() {
return rId;
}
public Node getLeftNode() {
return leftNode;
}
public Node getRightNode() {
return rightNode;
}
public void setKey(int key) {
this.key = key;
}
public void setrId(String rId) {
this.rId = rId;
}
public void setLeftNode(Node leftNode) {
this.leftNode = leftNode;
}
public void setRightNode(Node rightNode) {
this.rightNode = rightNode;
}
}
这同样适用于 Node
类。
另请注意,当 root 不为 null 时,添加 addElement
将不执行任何操作:
public void addElement(int key, String rId){
//add element to root node
if(root == null){
}
//what happens if root != null ?
}
关于java - 用多元素节点java实现Btree,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/44212691/