# 2-3 Baum, Einfügen



## nody (3. Jan 2009)

Hallo, habe ein Problem mit der Programmierung eines 2-3 Baums
Hänge bei der Einfügeoperation und weiss nichtmehr weiter(habe schon endlos gegoogled aber kriegs echt nicht hin   )

Also das was Ich bis jetzt habe funktioniert grundsätzlich, aber sobald ein Knoten nach oben hin "durchgereicht" werden muss weil eine Aufteilung des Elternknotens notwendig ist, verliere Ich alle darunterliegenden Referenzen.

Hier ein Beispiel dass Ich ebenfalls als Testfall benutze:
http://www.maths.lse.ac.uk/Courses/MA407/23trees.html

Im Beispiel versagt mein Baum beim einfügen von "e" da dass splitten nach oben durchgereicht werden müsste
bin schon ziemlich durch nun, hoffe wirklich mir kann jemand helfen (mir bleibt dann noch c-k-t)

Habe bisher dass hier:

Die Knotenklasse


```
public class TreeNode{
        
        TreeNode parent;
        TreeNode leftChild;
        TreeNode middleChild;
        TreeNode rightChild;
        
        Integer item1;
        Integer item2;
        
        public TreeNode(){
            
        }
              
        boolean isEmpty(){
            return item1 == null && item2 == null;
        }
        
        boolean isTwoNode(){
            return (item1 != null && item2 == null);
        }
        
        boolean isThreeNode(){
            return(item1 != null && item2 != null);
        }
        
        public TreeNode(TreeNode parent){
            this.parent = parent;
        }
        
        public TreeNode(int value, TreeNode parent){
            this.item1 = value;
            this.parent = parent;
        }
        
        public TreeNode(int minValue, int maxValue, TreeNode parent){
            this.item1 = minValue;
            this.item2 = maxValue;
            this.parent = parent;
        }
        
        boolean hasLeftChild(){
            return (leftChild != null);
        }
        
        boolean hasMiddleChild(){
            return (middleChild != null);
        }
        
        boolean hasRightChild(){
            return (rightChild != null);
        }
                
        boolean hasParent(){
            return parent != null;
        }
        
        boolean isLeaf(){
            return (this.leftChild == null && this.middleChild == null && this.rightChild == null);
        }
        
        void insert(int value){
            if(item1 == null){
                item1 = value;
                return;
            }
            if(value < item1 && item2 == null){
                item2 = item1.intValue();
                item1 = value;
                return;
            }
            if(value >= item1 && item2 == null){
                item2 = value;
                return;
            }
        }
        
        @Override
        public String toString(){
            String sItem1 = null;
            String sItem2 = null;
            try{
                sItem1 = ""+(char)item1.intValue();
                sItem2 = ""+(char)item2.intValue();
            }catch(Exception e){
                
            }            
            return new String("( "+sItem1+" | "+sItem2+" )");
        }       
    }
```

Der Baum:


```
public class Tree {

    public TreeNode root;
    
    public Tree() {
        root = new TreeNode();
    }
    
    public void insert(char c){
        insert((int)c);
    }
    public void insert(int key){
        //Blattknoten finden in den eingefügt werden muss:
        TreeNode node = root;
        while(!node.isLeaf()){
            node = traverse(node, key);
        }
        if(!node.isThreeNode()){
            node.insert(key);
        }else{
            split(node, key);
        }
        
    }
    
    public void split(TreeNode node, int key){
        TreeNode parent;
        
        if(node.hasParent()){
            parent = node.parent;
        }else{
            parent = new TreeNode();
            root = parent;
        }
        
        //kleinsten, mittleren und größten wert ermitteln:
        int[] arr = { node.item1, node.item2, key };
        Arrays.sort(arr);
        
        TreeNode nodemin = new TreeNode(arr[0], parent);
        TreeNode nodemax = new TreeNode(arr[2], parent);
        
        if(parent.isTwoNode()){
            if(parent.item1 < nodemin.item1){
                parent.middleChild = nodemin;
                parent.rightChild = nodemax;
            }            
            if(parent.item1 > nodemin.item1){
                parent.leftChild = nodemin;
                parent.middleChild = nodemax;
            }                       
        }else if(parent.isThreeNode()) {

        }else {
            parent.leftChild = nodemin;
            parent.rightChild = nodemax;           
        }

        
        if(!node.isLeaf()){
            
        }
        
        if(parent.isThreeNode()){
            split(parent, arr[1]);
        }else{
            parent.insert(arr[1]); 
        }     
    }

    private TreeNode traverse(TreeNode tmp, int newItem) {
        if(tmp.isTwoNode()){
            if(newItem < tmp.item1){
                return tmp.leftChild;
            }
            if(newItem > tmp.item1){
                return tmp.rightChild;
            }
        }else{           
            if(newItem < tmp.item1){
                return tmp.leftChild;
            }
            if(newItem > tmp.item1 && newItem < tmp.item2){
                return tmp.middleChild;
            }
            if(newItem > tmp.item2){
                return tmp.rightChild;
            }
        }
        return null;
    }
        
    public void inorder (TreeNode cur){
        System.out.println(cur);
        if (cur != null){
            inorder(cur.leftChild);
            inorder(cur.middleChild);
            inorder(cur.rightChild);
        }
    }
}
```


----------



## SlaterB (3. Jan 2009)

du könntest nun auf einen Experten treffen, der sich genau an den Algorithmus des 2-3 Baums mit insert/ split erinnert,
das vielleicht als korrekten Code vorliegen hat und genau erkennt, was bei dir falsch ist,
denkbar, aber wenig aussichtsreich

viel eher wirst du hier auf versierte Programmierer treffen, die in der Lage sind, so ein Problem zu durchdenken 
und den passenden Code dazu schreiben und begrenzt auch lesen/ korrigieren können,
mich z.B. 

aber da reicht dann nicht, 200 Zeilen unkommentierten Code zu posten,
den Helfer damit allein zu lassen und vielleicht auch noch selber bei google den passenden korrekten Algorithmus suchen zu lassen,
wer erinnert sich schon immer an die Details solcher Datenstrukturen?

also: erkläre detailliert, an besten an einem gemalten Beispiel-Baum,
was beim Einfügen nach welchen Regeln passieren soll,
und welche Schritte davon dein Programm auf welche Weise korrekt erledigt bzw. wo genau was genau verloren geht,


dazu gehören Beispiel-Skizzen und jede Menge System.out.println, also ein Log im Programm,
ganz wichtig ist auch eine main-Methode mit Einfüge-Reihenfolge, damit jeder das gleiche nachvollziehen kann

mit etwas Glück findest du auf diese Weise schon selber den Fehler

(edit: ok, das Beispiel hast du ja im Link , nun aber noch eine main-Methode zum Ablaufen, und erklären + Log im Programm, was alles schon klappt und wo es scheitert,

das Beispiel ist vielleicht auch zu heftig, da da in einem Schritt zweimal gesplittet wird, lieber erstmal nur einmal splitten)


----------



## nody (3. Jan 2009)

Hi,
aber genau das 2 fache splitten ist ja das problem, ansonsten würde es ja wie oben einfach funktionieren


```
public static void main(String[] args) {
        Tree tree = new Tree();
        //k, a, t, u, r, c, e, m, and d.. The first node holds ak
        tree.insert('k');
        tree.insert('a');
        tree.insert('t');
        tree.insert('u');
        tree.insert('r');
        tree.insert('c');
        tree.insert('e');
        //tree.insert('m');
        //tree.insert('d');
        System.out.println("                            "+tree.root);
        System.out.println("                "+ tree.root.leftChild+"                "+ tree.root.rightChild);
        System.out.println("            "+ tree.root.leftChild.leftChild+"              "+ tree.root.leftChild.rightChild+"            "+tree.root.rightChild.leftChild+"              "+tree.root.rightChild.rightChild);
    }
```

das ist die main, in der sich sobald man das e einfügt eben das problem des "doppelten splits" ergibt und mein baum somit ruiniert wird

einfach mal ausführen und insert(e) auskommentieren
und das gleiche wieder mit e

wie man sehen wird, werden die unterbäume von c und t nichtmehr existieren(ist ja klar, speichere auch die referenzen in dem fall nicht um, weil ich nicht weiss wie)

da die TreeNode Klasse recht trivial ist hier die kommentierte Tree Klasse

```
public void insert(int key){

        //Blattknoten finden in den eingefügt werden muss:
        TreeNode node = root;
        while(!node.isLeaf()){
            node = traverse(node, key);
        }

        //Im Knoten ist noch Platz für ein Element, also einfach einfügen
        if(!node.isThreeNode()){
            node.insert(key);
        }
        //Kein Platz, also muss der Knoten aufgeteilt werden(mittleres Element wird "hochgekickt")
        else{
            split(node, key);
        }
        
    }
    
    public void split(TreeNode node, int key){
        TreeNode parent;
        
        //Knoten hat nen Elternknoten
        if(node.hasParent()){
            parent = node.parent;
        }
        //Knoten besitzt keinen Elternknoten, also muss es sich um die Wurzel handeln
        //neue Wurzel erzeugen
        else{
            parent = new TreeNode();
            root = parent;
        }
        
        //kleinsten, mittleren und größten wert ermitteln:
        int[] arr = { node.item1, node.item2, key };
        Arrays.sort(arr);
        
        //nodemin = knoten mit kleinem element
        //nodemax = knoten mit großem element
        TreeNode nodemin = new TreeNode(arr[0], parent);
        TreeNode nodemax = new TreeNode(arr[2], parent);
        
        //wenn der elternknoten noch platz hat, die beiden neuen knoten einfach an der richtigen position anfügen
        if(parent.isTwoNode()){
            if(parent.item1 < nodemin.item1){
                parent.middleChild = nodemin;
                parent.rightChild = nodemax;
            }            
            if(parent.item1 > nodemin.item1){
                parent.leftChild = nodemin;
                parent.middleChild = nodemax;
            }                       
        }
        //alles hier ist wohl falsch
        else if(parent.isThreeNode()) {

        }
        //wenn der knoten kein TwoNode ist (also (3, freierplatz) und kein threenode, also (3, 4))
        //muss es sich wohl um einen neu erzeugten knoten handeln, also einfach links und rechts anfügen
        else {
            parent.leftChild = nodemin;
            parent.rightChild = nodemax;           
        }

        
        //wenn der knoten der gesplitted wird kein Blattknoten ist ist das hier wohl der Punkt an dem Ich
        //die Referenzen umspeichern müsste(also wenn ein "doppelsplit" erfolgt?) 
        if(!node.isLeaf()){
            
        }
        
        //wenn der elternknoten keinen platz hat, aufsplitten
        if(parent.isThreeNode()){
            split(parent, arr[1]);
        }
        //sonst einzufügendes element einfügen
        else{
            parent.insert(arr[1]); 
        }     
    }

    private TreeNode traverse(TreeNode tmp, int newItem) {
        if(tmp.isTwoNode()){
            if(newItem < tmp.item1){
                return tmp.leftChild;
            }
            if(newItem > tmp.item1){
                return tmp.rightChild;
            }
        }else{           
            if(newItem < tmp.item1){
                return tmp.leftChild;
            }
            if(newItem > tmp.item1 && newItem < tmp.item2){
                return tmp.middleChild;
            }
            if(newItem > tmp.item2){
                return tmp.rightChild;
            }
        }
        return null;
    }
```


----------



## SlaterB (3. Jan 2009)

so, bin nun hier weitergekommen,
die main war durchaus sehr hilfreich,

ansonsten konntest du natürlich nicht viel beschreiben, weil ja große Teile des Algorithmus noch ganz fehlen,

hätte jetzt nur schreiben können 'was nicht da ist musst du erst noch programmieren',
aber ich war ja vorher schon so unnachgiebig, da darf es nun ruhig bisschen mehr sein 

also erstmal nach ner Quelle gesucht, gar nicht so viel vorhanden,
von 
http://en.wikipedia.org/wiki/2-3_tree
ist 
http://www.cs.ucr.edu/cs14/cs14_06win/slides/2-3_trees_covered.pdf
verlinkt, der Code dort sieht deinem teilweise verdächtig ähnlich,

bei den schwierigen Stellen bleibt er aber auch sehr schemenhaft,
ich habe nun was zusammengebastelt, welches für das aktuelle Beispiel zu funktionieren scheint,
ob für alle, das muss noch bewiesen werden und ich habe auch das Gefühl, dass es eigentlich einfacher gehen müsste,
aber zu viel will ich eh nicht machen, also schon ganz gut so als Anregung:


```
public class Test {

	public static void main(String[] args) throws Exception {
		Tree tree = new Tree();
		// k, a, t, u, r, c, e, m, and d.. The first node holds ak
		tree.insert('k');
		tree.insert('a');
		tree.insert('t');
		tree.insert('u');
		tree.insert('r');
		tree.insert('c');
		tree.insert('e');
		// tree.insert('m');
		// tree.insert('d');
		System.out.println("                            " + tree.root);
		System.out.println("                " + tree.root.leftChild
				+ "                " + tree.root.rightChild);
		System.out.println("            " + tree.root.leftChild.leftChild
				+ "              " + tree.root.leftChild.rightChild
				+ "            " + tree.root.rightChild.leftChild
				+ "              " + tree.root.rightChild.rightChild);
	}
}

class TreeNode implements Comparable<TreeNode> {

	TreeNode parent;
	TreeNode leftChild;
	TreeNode middleChild;
	TreeNode rightChild;

	Integer item1;
	Integer item2;

	public TreeNode() {

	}

	boolean isEmpty() {
		return item1 == null && item2 == null;
	}

	boolean isTwoNode() {
		return (item1 != null && item2 == null);
	}

	boolean isThreeNode() {
		return (item1 != null && item2 != null);
	}

	public TreeNode(TreeNode parent) {
		this.parent = parent;
	}

	public TreeNode(int value, TreeNode parent) {
		this.item1 = value;
		this.parent = parent;
	}

	public TreeNode(int minValue, int maxValue, TreeNode parent) {
		this.item1 = minValue;
		this.item2 = maxValue;
		this.parent = parent;
	}

	boolean hasLeftChild() {
		return (leftChild != null);
	}

	boolean hasMiddleChild() {
		return (middleChild != null);
	}

	boolean hasRightChild() {
		return (rightChild != null);
	}

	boolean hasParent() {
		return parent != null;
	}

	boolean isLeaf() {
		return (this.leftChild == null && this.middleChild == null && this.rightChild == null);
	}

	void insert(int value) {
		if (item1 == null) {
			item1 = value;
			return;
		}
		if (value < item1 && item2 == null) {
			item2 = item1.intValue();
			item1 = value;
			return;
		}
		if (value >= item1 && item2 == null) {
			item2 = value;
			return;
		}
	}

	@Override
	public String toString() {
		String sItem1 = null;
		String sItem2 = null;
		try {
			sItem1 = "" + (char) item1.intValue();
			sItem2 = "" + (char) item2.intValue();
		} catch (Exception e) {

		}
		return "( " + sItem1 + " | " + sItem2 + " )";
	}

	@Override
	public int compareTo(TreeNode o) {
		return this.item1 - o.item1;
	}

}

class Tree {

	public TreeNode root;

	public Tree() {
		root = new TreeNode();
	}

	public void insert(char c) {
		insert((int) c);
	}

	public void insert(int key) {
		// Blattknoten finden in den eingefügt werden muss:
		TreeNode node = root;
		System.out.println("insert " + (char) key + ", " + node);
		while (!node.isLeaf()) {
			node = traverse(node, key);
		}

		// Im Knoten ist noch Platz für ein Element, also einfach einfügen
		if (!node.isThreeNode()) {
			node.insert(key);
		}
		// Kein Platz, also muss der Knoten aufgeteilt werden(mittleres Element
		// wird "hochgekickt")
		else {
			split(node, key, null, null);
		}

	}

	public void split(TreeNode node, int key, TreeNode specialChild1,
			TreeNode specialChild2) {
		TreeNode parent;

		// Knoten hat nen Elternknoten
		if (node.hasParent()) {
			parent = node.parent;
		}
		// Knoten besitzt keinen Elternknoten, also muss es sich um die Wurzel
		// handeln
		// neue Wurzel erzeugen
		else {
			parent = new TreeNode();
			root = parent;
		}
		// kleinsten, mittleren und größten wert ermitteln:
		int[] arr = { node.item1, node.item2, key };
		Arrays.sort(arr);

		// nodemin = knoten mit kleinem element
		// nodemax = knoten mit großem element
		TreeNode nodemin = new TreeNode(arr[0], parent);
		TreeNode nodemax = new TreeNode(arr[2], parent);

		// Liste aller neu zu verteilender Child-Nodes
		// (die eigenen + die vom aufgelösten SubNode = specialChild1 + 2)
		List<TreeNode> nodeList = new ArrayList<TreeNode>();
		if (node.leftChild != null) {
			nodeList.add(node.leftChild);
		}
		if (node.middleChild != null) {
			nodeList.add(node.middleChild);
		}
		if (node.rightChild != null) {
			nodeList.add(node.rightChild);
		}
		if (specialChild1 != null) {
			nodeList.add(specialChild1);
		}
		if (specialChild2 != null) {
			nodeList.add(specialChild2);
		}
		if (nodeList.size() > 0) {
			Collections.sort(nodeList);
			if (nodeList.size() == 4) {
				nodemin.leftChild = nodeList.get(0);
				nodemin.rightChild = nodeList.get(1);
				nodemax.leftChild = nodeList.get(2);
				nodemax.rightChild = nodeList.get(3);
			} else {
				throw new RuntimeException("unexpected list size: "
						+ nodeList.size());
			}
		}

		if (parent.isThreeNode()) {
			// node wurde pulverisiert, beim parent löschen
			if (node == parent.leftChild) {
				parent.leftChild = null;
			}
			if (node == parent.middleChild) {
				parent.middleChild = null;
			}
			if (node == parent.rightChild) {
				parent.rightChild = null;
			}

			// nodemin und nodemax wurden bisher noch nirgendwo als child
			// eingefügt, kann erst beim spluit weiter oben geschehen
			split(parent, arr[1], nodemin, nodemax);
		} else if (parent.isTwoNode()) {
			// manuelle Korrektur aller Links
			if (parent.item1 < nodemin.item1) {
				parent.middleChild = nodemin;
				parent.rightChild = nodemax;
				parent.item2 = arr[1];
			}
			if (parent.item1 > nodemin.item1) {
				// wichtig: altes item1 merken/ weiterschieben
				parent.item2 = parent.item1;

				parent.leftChild = nodemin;
				parent.middleChild = nodemax;
				parent.item1 = arr[1];
			}
		} else {
			parent.leftChild = nodemin;
			parent.rightChild = nodemax;
			parent.item1 = arr[1];
		}
	}

	private TreeNode traverse(TreeNode tmp, int newItem) {
		if (tmp.isTwoNode()) {
			if (newItem < tmp.item1) {
				return tmp.leftChild;
			}
			if (newItem > tmp.item1) {
				return tmp.rightChild;
			}
		} else {
			if (newItem < tmp.item1) {
				return tmp.leftChild;
			}
			if (newItem > tmp.item1 && newItem < tmp.item2) {
				return tmp.middleChild;
			}
			if (newItem > tmp.item2) {
				return tmp.rightChild;
			}
		}
		throw new RuntimeException("ach du Schreck");
	}

	public void inorder(TreeNode cur) {
		System.out.println(cur);
		if (cur != null) {
			inorder(cur.leftChild);
			inorder(cur.middleChild);
			inorder(cur.rightChild);
		}
	}
}
```
zu Zeile 181-208 siehe PDF, Folie 26,27, 35 oben
Zeile 211-220 sind dafür auch noch wichtig

Zeile 225-244 hattest du auch schon weitgehend


----------



## nody (3. Jan 2009)

Hi,

Wow, das mit der split(node, key, subnode1, subnode2) hatte ich auch die letzten stunden probiert, nur hatte ich nach wie vor das problem mit der neureferenzierung der subknoten. muss mir jetzt mal deine version zu gemüte führen.

danke schonmal


----------



## nody (3. Jan 2009)

So, hab jetzt mal deinen Code getestet und bin "leider" zu einem ähnlichen Ergebnis gekommen wie bei meinem Versuch.

Zwar funktioniert er für das erste Testbeispiel, doch wenn Ich mal die Zahlenfolge aus der pdf nehme (toString aus TreeNode muss dann angepasst werden) "verliert" er die 70 und die 60.

Dennoch denke Ich wars sehr hilfreich, werde selbst mal schauen ob Ich weiterkomme nun (Ich hoffs doch schwer, sonst wirds peinlich   )


```
tree.insert(50);
        tree.insert(30);
        tree.insert(70);
        tree.insert(90);
        
        tree.insert(10);
        
        tree.insert(20);                             
        tree.insert(40);
        tree.insert(60);
        tree.insert(80);
        tree.insert(100);
```

Hier das Applet dass Ich zur Kontrolle nutze

2-3 Tree Applet

Weiss nicht worans liegt, ne normale Liste oder nen BST krieg Ich ja ohne Probleme hin, aber beim 2-3 hängts irgendwie  ???:L


----------

