Inneren Knoten eines Baumes erstellen

Allgemeine Themen rund um Java

Moderator: wegus

Antworten
SmokeTM
Beiträge: 1
Registriert: 08.12.2017, 17:00

Inneren Knoten eines Baumes erstellen

Beitrag von SmokeTM » 08.12.2017, 17:24

Hallo,

versuche gerade die inneren Knoten eines B+Baumes zu erstellen, jedoch weiß ich nicht wie der Code dazu aussehen muss.
Mir wird hier eine Liste mit Objekten übergeben, mit einer Arraylist als Attribut für die keys. Mit diesen keys muss ich nun die inneren Knoten erstellen.
Das heißt jeder erste key eines Blattes steigt auf und wird zum inneren Knoten sollte dieser überlaufen muss ein zweiter und dritter innerer Knoten erstellt werden, einer in der gleichen Ebene und einer muss aufsteigen.
Die Methode sieht wie folgt aus:

Code: Alles auswählen


 /**
   * Builds a valid inner level of this B+ tree with the minimal number of inner
   * nodes for the specified list of child nodes. This method returns a sorted
   * list of the inner nodes created in the process (sorted with respect to the
   * keys in the nodes). The children in an inner node are supposed to point
   * to the respective child nodes.
   *
   * @param children a sorted list of child nodes for which the next inner level
   *  is built
   *
   * @return a sorted list of all inner nodes created in the process, or
   *  <tt>null</tt> if there are no children to connect
   */
  private List<BPNode<Key>> buildInnerLevel (final List<BPNode<Key>> children) {
    // deal with trivial cases
    if ((children == null) || children.isEmpty()) {
      return null;
    }

    List<BPNode<Key>> currentLevel = new ArrayList<BPNode<Key>>();
    
    BPNode<Key> temp = new BPNode<Key>(degree());
    
    for(int i = 1; i < children.size(); i++) {
    	temp.addKey(children.get(i).key(0));
    	if(temp.keys().size() > (degree() - 1)) {
    	
    	}
    }
    
    currentLevel.add(temp);
    
    System.out.println(currentLevel.get(0).key(0));
    
    return currentLevel;
  }

Mein Ansatz mit der for-schleife wird nicht funktionieren? Muss es rekursiv gelöst werden?
currentLevel soll dann alle inneren Knoten geordnet(aufsteigend) zurück geben.

Ich hoffe, es kann mir wer helfen. Falls noch mehr Informationen benötigt werden lasst es mich bitte wissen!

LG

Antworten