複数要素のノードJavaでBtreeを実装する

Question

各ノードに固定要素を持つ複数要素のノードを持つJavaでBtreeを実装しようとしています。ツリーの挿入メソッドを作成しようとしています。

私のコードでは、例えば、各ノードは3つの要素を含み、各要素は2つの子ノード（左と右）を指します。これは2,3ツリーに似ていますが、各ノードの要素の数はもっと多くなり、各ノードは固定長要素を持ちます。 基本的に、ノードが分割されると、中央の要素は昇格を取得します。 この画像は、インサートがどのように動作するかを示しています。

これは私のコードですが、私はルートノードを作り始めるために書いているが、私は、挿入および分割方法の再利用により、木が大きくする方法がわかりません。

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クラスに適用されます。
はまた、ルートがnullでないときaddElementは何もしません追加注意：

public void addElement(int key, String rId){ 
     //add element to root node 
     if(root == null){ 

     } 
     //what happens if root != null ? 
    }