java - 用多元素节点java实现Btree

Question

我正在尝试用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];
    }

}

Answer 1

要回答评论中的问题，请参阅以下修改后的 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  ? 
  }