2,3-Baum rekursiv erstellen

[drose_1]

Hallo, folgendes Problem:
wie lässt sich ein 2-3-Baum rekursiv erstellen?
Genauer gesagt ich gebe in den Konstruktor der Klasse ein sortiertes Array(z.B int a[] = {1,2,3,4,5,6,7,8,9,10}) und daraus soll dann der Konstruktor den Baum erstellen.
Zum 2-3-Baum:
Datensätze befinden sich nur in Blättern
Alle Nodes über den Blättern tragen Keys anstatt Datensätze
Jede Node kann bis zu 3 Keys tragen und min 2 und max 3 Kinder haben

Das Problem an der ganzen Sache ist das wir keine insert-Funktion implementieren sollen, was ich zunächst erstmal komisch finde.
Im Anhang liegt der skizzierte Baum vor der aus obigen Array entehren würde bei korrekter Implementerung.
Wäre nice wenn mir jemand Gedankenanstöße geben könnte wie man an diese Sache rangeht, ich möchte mir auch nicht die Lösung irgendwie erschleichen oder so, ich bin eigentlich ziemlich ehrgeizig was solche Datenstrukturen angeht aber momentan hab ich in der Sache gar kein Durchblick.
Normale Trees und Binary Search Trees sind mir geläufig, falls das irgendwie hilft.
Ich hätte hier noch ne Auflistung des Baumes in preOrder mit Blättern in <> geschrieben und Nodes mit Keys in () geschrieben:
(5,10)
(2,5)
(1,2)
<1>
<2>
(3,4,5)
<3>
<4>
<5>
(7,10)
(6,7)
<6>
<7>
(8,9,10)
<8>
<9>
<10>

 

[mihe7]

Ich hätte hier noch ne Auflistung des Baumes

Ist die von Dir?

 

[httpdigest]

Zum 2-3-Baum: Datensätze befinden sich nur in Blättern

Das ist nicht, was man im Allgemeinen unter einem 2-3-Baum versteht. In einem 2-3-Baum enthalten sowohl innere Knoten als auch Blattknoten die Daten. Auf den Daten ist eine totale Ordnung definiert, so dass man zwei Daten "der Größe nach" miteinander vergleichen kann. Ein innerer Knoten kann 1 Datum beinhalten und 2 Kindknoten haben, oder er kann 2 Daten beinhalten und 3 Kindknoten haben. Im Falle, dass er 2 Kindknoten hat, gilt, dass alle Daten im linken Teilbaum (also alle Daten des ersten Kindbaumes) strikt kleiner (<) sind als das Datum im inneren Knoten. Entsprechend gilt, dass alle Daten im rechten Teilbaum strikt größer (>) sind als das Datum im inneren Knoten. Bei einem inneren Knoten mit 2 Daten gelten entsprechende Bedingungen für die drei Intervalle/Kindbäume.
Ich würde mal wagen zu sagen, dass der von dir gezeigte Beispielbaum falsch ist im Sinne, dass es keinen validen 2-3-Baum darstellt - oder es ist eine Abwandlung, für die eine klarere Definition nötig ist. Auch gibt es ja bei deinem Beispiel keinen Unterschied zwischen einem "Key", der laut deiner Definition in den inneren Knoten gespeichert ist, und dem tatsächlichen Datum, das in den Kindknoten gespeichert sein soll.

 

[drose_1]

Das ist nicht, was man im Allgemeinen unter einem 2-3-Baum versteht. In einem 2-3-Baum enthalten sowohl innere Knoten als auch Blattknoten die Daten. Auf den Daten ist eine totale Ordnung definiert, so dass man zwei Daten "der Größe nach" miteinander vergleichen kann. Ein innerer Knoten kann 1 Datum beinhalten und 2 Kindknoten haben, oder er kann 2 Daten beinhalten und 3 Kindknoten haben. Im Falle, dass er 2 Kindknoten hat, gilt, dass alle Daten im linken Teilbaum (also alle Daten des ersten Kindbaumes) strikt kleiner (<) sind als das Datum im inneren Knoten. Entsprechend gilt, dass alle Daten im rechten Teilbaum strikt größer (>) sind als das Datum im inneren Knoten. Bei einem inneren Knoten mit 2 Daten gelten entsprechende Bedingungen für die drei Intervalle/Kindbäume.
Ich würde mal wagen zu sagen, dass der von dir gezeigte Beispielbaum falsch ist im Sinne, dass es keinen validen 2-3-Baum darstellt - oder es ist eine Abwandlung, für die eine klarere Definition nötig ist. Auch gibt es ja bei deinem Beispiel keinen Unterschied zwischen einem "Key", der laut deiner Definition in den inneren Knoten gespeichert ist, und dem tatsächlichen Datum, das in den Kindknoten gespeichert sein soll.

ja wir haben die "Datensätze" der inneren Knoten einfach als Keys bezeichnet
der einzige Unterschied den wir zu allgemein bekannten 2-3-Bäumen haben ist, das innere Knoten bis zu 3 Datensätze tragen können und das die Datensätze links vom Knoten nicht strikt kleiner sein müssen sonder auch gleich groß sein darf, das gilt dann auch analog für rechte

 

[Xyz1]

und das die Datensätze links vom Knoten nicht strikt kleiner sein müssen sonder auch gleich groß sein darf

super, wobei dann die Trichotomie der Ordnung nicht mehr gegeben sei, wenn ich mich nicht verschaut hab

 

[drose_1]

die Dreiteilung ist weiterhin intakt ob jetzt Datensätze < oder <= sind macht doch keinen unterschied, ich würde ja gerne ne Skizze vom baum hochladen aber die Forum-Software meckert ständig das die Bilder zu groß seien, was ist denn die maximale Dateigröße hier ?

 

[httpdigest]

Nimm einfach einen anderen Uploaddienst (ich persönlich nehme hierfür immer imgur) und poste das Bild hier als Image URL.

 

[mihe7]

           5|10
   2|5             7|10
1|2  3|4|5      6|7  8|9|10

 

[httpdigest]

Bevor du dir Gedanken machst, wie der Baum aus der Liste der Zahlen aufgebaut wird, skizziere erstmal deine Datenstruktur. Algorithmen ergeben sich meist direkt aus den Datenstrukturen. Wie sieht deine Baum/Knoten-Klasse ganz exakt aus? Wie wird zwischen einem inneren Knoten und einem Blattknoten unterschieden? Wo/wie werden die Kindknoten eines inneren Knotens gespeichert und wo/wie wird das Datum eines Blattknotens gespeichert?

 

[drose_1]

           5|10
   2|5             7|10
1|2  3|4|5      6|7  8|9|10

Genau so nur das die Blätter fehlen

 

[drose_1]

Bevor du dir Gedanken machst, wie der Baum aus der Liste der Zahlen aufgebaut wird, skizziere erstmal deine Datenstruktur. Algorithmen ergeben sich meist direkt aus den Datenstrukturen. Wie sieht deine Baum/Knoten-Klasse ganz exakt aus? Wie wird zwischen einem inneren Knoten und einem Blattknoten unterschieden? Wo/wie werden die Kindknoten eines inneren Knotens gespeichert und wo/wie wird das Datum eines Blattknotens gespeichert?

So gesehen würde ich das in 3 Klassen teilen.
Einmal die Baumklasse: Mit einer root Node als Instanzvariable.
die innere Knoten Klasse : mit 3 Datensätzen zum Beispiel left , middle ,right (left < middle < right) und mit Verweisen auf bis zu 3 Kindknoten zum bespiel Node left_child, middle_child und right _child
und eine Blattknoten klasse : die nur einzelne Datensätze hält (z.B int Data

alles mit Getter und setter implementiert. Das wäre zunächst der Ansatz.

 

[httpdigest]

Skizziere das doch mal ganz genau als Java Klassen. Und ich würde für die Datensätze in den Knoten und für die Verweise auf die Kindknoten wahrscheinlich schon eine java.util.List statt drei Instanzvariablen nehmen (twenn ihr dürft). Da es ja manchmal 2 und manchmal 3 sein können und wir viele if-Abfragen hier vermeiden wollen.

 

[drose_1]

Skizziere das doch mal ganz genau als Java Klassen. Und ich würde für die Datensätze in den Knoten und für die Verweise auf die Kindknoten wahrscheinlich schon eine java.util.List statt drei Instanzvariablen nehmen (twenn ihr dürft). Da es ja manchmal 2 und manchmal 3 sein können und wir viele if-Abfragen hier vermeiden wollen.

public class TwoThreeTree {

    private class insideNode {

        int data;
        insideNode left, middle, right, parent;

        insideNode(int data) { this.data = data; }

        insideNode getLeft() { return left; }
        insideNode getMiddle() { return middle; }
        insideNode getRight() { return right; }
        insideNode getParent() { return parent; }
        int getData() { return data; }
        void setData(int data) { this.data = data; }
        void setLeft(insideNode left) { this.left = left; }
        void setMiddle(insideNode middle) { this.middle = middle; }
        void setRight(insideNode right) { this.right = right; }
        void setParent(insideNode parent) { this.parent = parent; }
    }

    private class leafNode {

        int data;
        insideNode parent;

        leafNode(int data) {
            this.data = data;
        }

        int getData() { return data; }
        void setData(int newData) { this.data = newData; }
        insideNode getParent() { return parent; }
        void setParent(insideNode parent) { this.parent = parent; }
    }

    private insideNode root;

    TwoThreeTree(int[] a) {
        
    }
}

Hab den Konstruktor des Baumes jetzt offen gelassen, weil der komplette Baum ja über diesen enstehen soll.
Bisher bei Bäumen sind wir so verfahren das über ne Insertfunktion den Baum entsteht auf diese sollen wir aber ja verzichten.

 

[httpdigest]

Denke mal noch etwas über deine Klassenhierarchie für die Knoten des Baumes nach. So funktioniert das noch nicht. Du kannst aktuell keine `leafNode` Instanzen speichern, da diese keine `insideNode` sind (btw.: in Java werden Typnamen IMMER "Groß" geschrieben, also `LeafNode` und `InsideNode` bzw. üblicher ist `InnerNode`).

 

[drose_1]

Denke mal noch etwas über deine Klassenhierarchie für die Knoten des Baumes nach. So funktioniert das noch nicht. Du kannst aktuell keine `leafNode` Instanzen speichern, da diese keine `insideNode` sind (btw.: in Java werden Typnamen IMMER "Groß" geschrieben, also `LeafNode` und `InsideNode` bzw. üblicher ist `InnerNode`).

package com.company.Übung11;

public class TwoThreeTree {

    private class InnerNode {

        int data;
        InnerNode left, middle, right, parent;
        LeafNode leftLeaf, middleLeaf, rightLeaf;

        InnerNode(int data) { this.data = data; }

        InnerNode getLeft() { return left; }
         InnerNode getMiddle() { return middle; }
        InnerNode getRight() { return right; }
        InnerNode getParent() { return parent; }
        int getData() { return data; }
        void setData(int data) { this.data = data; }
        void setLeft(InnerNode left) { this.left = left; }
        void setMiddle(InnerNode middle) { this.middle = middle; }
        void setRight(InnerNode right) { this.right = right; }
        void setParent(InnerNode parent) { this.parent = parent; }
        LeafNode getLeftLeaf() { return leftLeaf; }
        LeafNode getMiddleLeaf() { return middleLeaf;}
        LeafNode getRightLeaf() { return  rightLeaf;}
        void setLeftLeaf(LeafNode leftLeaf) {this.leftLeaf = leftLeaf;}
        void setMiddleLeaf(LeafNode middleLeaf) { this.middleLeaf = middleLeaf; }
        void setRightLeaf(LeafNode rightLeaf) { this.rightLeaf = rightLeaf; }
    }

    private class LeafNode {

        int data;
        InnerNode parent;

        LeafNode(int data) {
            this.data = data;
        }

        int getData() { return data; }
        void setData(int newData) { this.data = newData; }
        InnerNode getParent() { return parent; }
        void setParent(InnerNode parent) { this.parent = parent; }
    }

    private InnerNode root;

    TwoThreeTree(int[] a) {

    }
}

ok habs jetzt nochmal überarbeitet

 

[httpdigest]

Nein, jetzt hast du viele unnötige Felder, von denen ja immer nur eine Hälfte gefüllt sein wird. Was du willst, ist eine Typhierarchie. Schau dir mal das "extends" Schlüsselwort in Java an, bzw. was Vererbung ist.

 

[drose_1]

Ja stimmt, das hab ich komplett vergessen.
Ich würde jetzt mal annehmen das die InsideNode von den LeafNodes erben, da diese ja ein paar Felder mehr haben.

 

[httpdigest]

Ich würde jetzt mal annehmen das die InsideNode von den LeafNodes erben, da diese ja ein paar Felder mehr haben.

Ich würde weder InnerNode von LeafNode, noch LeafNode von InnerNode erben lassen.

 

[drose_1]

Also beide von einer separaten Node-Klasse ?
Aber irgendwie erscheint mir das eigenartig. Da innerNodes wesentlich mehr Felder besitzen als LeafNodes, auch wenn es Node sind ,sind diese doch schon ziemlich verschieden.

 

[mihe7]

Da innerNodes wesentlich mehr Felder besitzen als LeafNodes, auch wenn es Node sind ,sind diese doch schon ziemlich verschieden.

Ist das so? Ein Blatt ist-ein Knoten, ein innerer Knoten ist-ein Knoten. So verschieden können die also gar nicht sein.

Du kannst einen Knoten nach seinen Einträgen fragen, Du kannst einen Knoten nach seinen Kindknoten fragen, Du kannst einen Knoten fragen, ob es sich um ein Blatt handelt...

 

[Barista]

Falls Du nicht gezwungen bist einen 2-3-baum zu erstellen würde ich Dir zum B-Tree raten, der ist einfacher zu implementieren.