# 2-3-4 Baum Problem



## TheDestroyer (4. Jul 2006)

Hallo Leute, hab nen Problem

und zwar soll ich im follgenden  Quelltext, den ich soweit fertig habe noch einen Unterlauf einfügen, weiss aber nicht recht wie ich das machen soll. Und zwar soll sich der Baum, nach dem Löschen einzelner Knoten auf der Blattebene neu aufbauen.

Hoffe ihr könnt mir helfen. Vielleicht kann hier jemand, mal die passenden Zeilen mit einsetzten, weiss ja dass das hier sonst nicht üblich ist, aber ihr würdet mir wirklich richtig dolle helfen.


```
public class Tree234{

	private class Tree234Node <T extends Comparable<T>>{

		private Comparable[] keys; 
		private Tree234Node[] children;

		private Tree234Node() {
			keys =  new Comparable[2*order];
			children = new Tree234Node[2*order+1];
		}
		// clonen der Knoten und Kinder
		private Tree234Node(Tree234Node copy) {
			keys = copy.keys.clone();
			children = copy.children.clone();
		}
		// bestimmt Position der Knoten
		private void setKeys(Comparable[] k) {
			keys = k;
		}
		// bestimmt Position der Kinder
		private void setChildren(Tree234Node[] c) {
			children = c;
		}
		// Kinder werden auf null gesetzt
		private boolean isLeaf() {
			return (children[0] == null);
		}
		// Vergleich des Knoten mit den mögl. Kindern
		private boolean find(Comparable key) {
			System.out.println(this);
			for (int i = 0; i < children.length; i++) {
				if (i == keys.length || keys[i] == null)
					return children[i].find(key);	// Kind Nachfolger vom Knoten
				int cmp = keys[i].compareTo(key);	// sonst sucht weiter bis Nachfolger gefunden
				if (cmp == 0) return true;
				else if (cmp > 0 && children[i] != null) 
					return children[i].find(key);
				else if (cmp > 0 && isLeaf())		// wenn kein Nachfolger gefunden, wird Knoten neu eingefügt
					return false;
			}
			return false;
		}
		// Löschen eines Schlüssels
		public boolean delete(Comparable newKey,Tree234Node returnNode){
			if (!isLeaf()) {
				for (int i = 0; i < children.length; i++) {
					if (i == keys.length || keys[i] == null){
						newKey = children[i].delete(newKey,returnNode);
						newKey=null;
						break;
					}	
					int cmp = keys[i].compareTo(newKey);
					if (cmp == 0) break;
					else if (cmp > 0) {
						newKey = children[i].delete(newKey,returnNode);
						break;
					}
				}
			}
			/*
			 * wenn das zu löschende Element im Baum vorhanden ist, 
			 * dann ist es in diesem Knoten (new key != null) 
			 */
			if (newKey != null) {
				int i=0;
				while (i < keys.length 
					&& keys[i] != null
					&& keys[i].compareTo(newKey) < 0) 
					i++;
				if (i < keys.length 
					&& keys[i] != null 
					&& keys[i].compareTo(newKey) == 0){ 
					keys[i] = null;//eigentliches löschen
					newKey=null;
					i++;
					/*
					 * nehmen den nächsten Index, der muss, wenn er 
					 * nicht null ist eine Stelle nach links
					 */
					}
				while (i < keys.length) {
					Comparable tmpKey = keys[i];//temporäre speicher variable
					if (tmpKey == null) break;
					Tree234Node tmpNode = children[i];//key und Inhalt muss verschoben werden
							keys[i-1] = tmpKey;//einen nach links
							children[i]= tmpNode;// einen nach links
							i++;//kann ja noch ein Eintrag drinnen sein
				}
			}	
			return false;
			}
			

		
		Comparable insert(Comparable newKey,Tree234Node returnNode) {
			// Einfügeknoten suchen 
			if (!isLeaf()) {
				for (int i = 0; i < children.length; i++) {
					if (i == keys.length || keys[i] == null){
						newKey = children[i].insert(newKey,returnNode);
						break;
					}	
					int cmp = keys[i].compareTo(newKey);
					if (cmp == 0) return null;
					else if (cmp > 0) {
						newKey = children[i].insert(newKey,returnNode);
						break;
					}
				}
			}
			// Einfügeposition in Knoten suchen
			if (newKey != null) {
				int i=0;
				while (i < keys.length 
						&& keys[i] != null
						&& keys[i].compareTo(newKey) < 0) 
					i++;
				if (i < keys.length 
						&& keys[i] != null 
						&& keys[i].compareTo(newKey) == 0) 
					return null;
				Comparable tmpKey = null;
				Tree234Node tmpNode = null;
				Tree234Node newNode = new Tree234Node(returnNode);
				
				
				// Einfügen und Nachfolger weiterrücken
				while (i < keys.length) {
					tmpKey = keys[i];
					tmpNode = children[i+1];
					keys[i] = newKey;
					children[i+1] = (newNode == null || isLeaf()) ?
						null :
						newNode;
					newKey = tmpKey;
					newNode = tmpNode;
					i++;
				}
				// Überlaufbehandlung
				if (newKey != null) {
					
					/*
					 * neuen Knoten erzeugen, Schluessel kopieren 
					 * und aus altem Knoten loeschen
					 */ 
									 
					tmpNode = new Tree234Node();
					for (i = 0; i < order-1; i++) {
						tmpNode.keys[i] = keys[order+i+1];
						tmpNode.children[i] = children[order+i+1];
						keys[order+i+1] = null;
						children[order+i+1] = null;
					}
					tmpNode.children[order-1] = children[2*order]; // Ordnung des Baums bestimmt
					children[2*order] = null; 
					tmpNode.keys[order-1] = newKey;
					tmpNode.children[order] = (newNode == null || isLeaf()) ?
						null :
						newNode;
					
					// mittlerer Schluessel als Rueckgabewert
					newKey = keys[order];
					keys[order] = null;
					children[order+1] = null;
					
					// Werte des Rueckgabeknoten setzen
					returnNode.setKeys(tmpNode.keys.clone());
					returnNode.setChildren(tmpNode.children.clone());
				}
			}
			return newKey;
		}
		// toString Methode eingesetzt
		public String toString() {
			String res = "[";
			for (int i = 0; i < keys.length; i++) 
				res = res + " " + keys[i] + " ";
			res += "]";
			return res;
		}
		// Niveau des Knotens wird bestimmt
		private String toString(int level) {
			String res = "";
			int i = 0;
			for (i = 0; i < level; i++) res += " ";
			res = res + this + "\n";
			for (i = 0; i < children.length; i ++)
				if (children[i] != null)
					res += children[i].toString(level+1);
			return res;

		}
	}
	
	int order;
	Tree234Node root = null;
	// Methoden für den Baum
	public Tree234(int o) {
		order = o;
		root = new Tree234Node();
	}
	// Vergleich 
	public boolean find(Comparable key) {
		return root.find(key);
	}
	// Einfügen neuer Schlüssel
	public void insert(Comparable newKey) {
		Tree234Node returnNode = new Tree234Node();
		Comparable newRootKey = root.insert(newKey, returnNode);
		if (newRootKey != null) {
			Tree234Node newRoot = new Tree234Node();
			newRoot.keys[0] = newRootKey;
			newRoot.children[0] = root;
			newRoot.children[1] = returnNode;
			root = newRoot;
		}
	}
	// Methode um Schlüssel zu löschen
	public boolean delete(Comparable loeschen){
		Tree234Node returnNode = new Tree234Node();
		Comparable newRootKey = root.delete(loeschen, returnNode);
		if (newRootKey != null) {
			Tree234Node newRoot = new Tree234Node();
			newRoot.keys[0] = newRootKey;
			newRoot.children[0] = root;
			newRoot.children[1] = returnNode;
			root = newRoot;
		}
		return false;
		
	}
	
	public String toString() {
		String res = "Tree234:\n------\n";
		return (res + root.toString(0));
	}

	// Ausgabe des Baumes
	public static void main(String[] args) {
		Tree234 tree234 = new Tree234(2);
		Integer[] inserts = {7, 19, 23, 4, 12, 17, 8, 11, 2, 9, 13};
		for (Integer i : inserts) {
			System.out.println("\nInsert: " + i);
			tree234.insert(i);
			System.out.println(tree234);
		}
		
		tree234.delete(23);
		System.out.println(tree234+"test");
	}
}
```


----------



## Leroy42 (4. Jul 2006)

Abgesehen davon, daß hier wohl kaum jemand auf Anhieb
weiß was ein 2-3-4-Baum ist, bzw. auf welche von mehreren
_ähnlichen_ Definitionen du dich beziehst(beziehen sollst),
hat wohl kaum jemand Lust, sich einen Baum-Restrukturierungsalgorithmus
aus den Fingern zu saugen und in ein bestehendes, 250 Zeilen starkes,
Programm einzufügen  :? 

Ich schätze mal, daß du weitaus mehr Informationen hast,
die notwendigen Änderungen zumindest schon mal zu versuchen.

Wenn du dabei konkrete Schwierigkeiten hast, wird dir hier sicher
gerne weitergeholfen werden.

Aber so, ...  :roll:


----------



## Redfrettchen (4. Jul 2006)

Ein 2-3-4-Baum ist laut Wikipedia ein B-Baum zweiter Ordnung (man muss ja auch für jeden *** einen eigenen Namen finden ~~).

Jo, aber durch den komischen Code jetzt durchwursteln und auch noch was komplexes dazu schreiben, dazu hab ich persönlich keine Lust.


----------

