Implementieren Sie Btree mit Multi-Elemente-Knoten Java

Question

Ich versuche, ein Javatree in Java mit Multi-Elemente-Knoten mit festen Element in jedem Knoten. Ich versuche, eine Einfügemethode für den Baum zu machen.

In meinem Code zum Beispiel enthält jeder Knoten 3 Elemente und jedes Element zeigt auf 2 Kinderknoten (links und rechts). Es funktioniert ähnlich wie 2,3-Baum, aber die Anzahl der Elemente in jedem Knoten könnte viel größer sein und jeder Knoten hat feste Länge Elemente. Grundsätzlich wird das mittlere Element bei der Aufteilung eines Knotens aktiviert. Dieses Bild zeigt, wie der Einsatz funktioniert:

Das ist mein Code, ich schreibe machen Root-Knoten zu starten, aber ich weiß nicht, wie der Baum größer der Einsatz und Split-Methoden durch die Wiederverwendung zu machen.

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

Ihre Frage in den Kommentaren zu beantworten, die folgende modifizierte Element-Klasse:

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; 
    } 
} 

Gleiches gilt für Node Klasse gilt.
Beachten Sie auch die addElement hinzufügen wird nichts tun, wenn root nicht null ist:

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

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