實現具有多元素節點的Btree java

我想在每個節點中使用固定元素的多元素節點在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]; 
    } 

}

來源

2017-05-27 Kay Hoang

後的圖像的鏈接，我會添加它 – c0der

我認爲有需要增加功能之前先解決一些基本問題，比如：'Node'字段（元素，leftParent，rightParent）不被使用。您需要使用構造函數或setter來初始化它們。 'Element'（leftNode，rightNode）同樣適用。 'addElement'也允許僅向空根添加。 – c0der

謝謝，我只是把圖像，我不是很擅長Java，只是做了Java課程的介紹。我在互聯網上搜索了一些代碼，但它對我沒有多大幫助。 –

要回答你的問題的意見，請參閱下面的修改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類。
還要注意添加addElement會一籌莫展的時候，根本不爲空：

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

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

來源

2017-05-27 09:13:29 c0der

實現具有多元素節點的Btree java

回答

相關問題