Binärbaum Ordnungsproblem

[pzypher]

Hallo,

ich schaffe es nicht, Zahlen bis n in einen geordneten binären Suchbaum unterzubringen. (linker Ast kleiner; rechter Ast größer als Vaterknoten)

Bei meinem Beispiel möchte ich 60 Zahlen unterbringen, dh. hätte ich mir root = 30 angefangen.

Klasse Knoten

public class Knoten {
	
	Knoten links;
	Knoten rechts;
	int value;
	
	public Knoten(int value) {
		this.value = value;
	}
	
	public void insert(Knoten currentRoot, int value) {
		
//Füge neue Wurzel ein, falls Wert kleiner Vorgänger + nächste Wurzel = null
		if(value < currentRoot.value) {
			if(currentRoot.links == null) {
				System.out.println(" Wert " + value + " links vom root " + currentRoot.value);
				currentRoot.links = new Knoten(value);
			}
//sonst rekursiver Aufruf mit nächstem Wurzelelement
			else 
				insert(currentRoot.links, value);
		}
//Füge neue Wurzel ein, falls Wert größer Vorgänger + nächste Wurzel = null
		else if(value > currentRoot.value) {
			if(currentRoot.rechts == null) {
				System.out.println(" Wert " + value + " rechts vom root " + currentRoot.value);
				currentRoot.rechts = new Knoten(value);
			}
//sonst rekursiver Aufruf mit nächstem Wurzelelement
			else 
				insert(currentRoot.rechts, value);
		}
	}

}

Klasse Hauptprogramm

import java.util.Scanner;

public class Hauptprogramm {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub


//Mein aktueller Versuch, Zahlen von 60 in einen Binärbaum unterzubringen
//root soll den Wert 20 haben (damit alle Äste gleich lang sind?) 

		Knoten root = new Knoten(30); 
		
//Mit dieser Schleife erschaffe ich mir nur einen Baum, der nach links und rechts geht 

		for(int i = 1; i <= root.value; i++) {
			
			if(i%2==0) 
				root.insert(root, root.value-i);
			else
				root.insert(root, root.value+i);
		}
	}

}

Mit dem aktuellen Hauptprogramm erstelle ich einen Baum, bei dem jede Wurzel (bis auf root) nur 1 Nachfolger hat.

Ich suche bereits seit Stunden nach einer Rechenvorschrift, finde (oder verstehe?) aber keine. Ich wäre auch schon dankbar wenn mir jemand eben diese Rechenvorschrift vermittelt, die Implementierung mach ich dann gerne selber.

Danke für eure Hilfe!

 

[Fant]

Mit dem aktuellen Hauptprogramm erstelle ich einen Baum, bei dem jede Wurzel (bis auf root) nur 1 Nachfolger hat.

Und wieso ist das ein Problem? Mir ist nicht klar, was du nun überhaupt wissen willst?! ???:L

 

[XHelp]

Mach es doch auf dem Blattpapier nach, dann kommst du bestimmt auf das selbe Ergebnis.
Falls ich es mir richtig vorstelle, dass muss du, damit dein Baum "ausbalanciert" ist, jeweils die "Mitte" hinzufügen:
zuerst 30, dann 15 und 45, dann 7, 22, 38, 52 usw.
Einfach mal in einer Reihe alle Zahlen reinzuknallen wird nicht klappen.

 

[Fant]

Wenn man einen ausbalancierten Baum haben will, dann sollte der Baum selbst aber dafür sorgen, dass er ausbalanciert ist und nicht der Benutzer beim Einfügen der Werte.
Wenn alle einzutragenen Werte vorher bekannt sind, dann wird der Baum ja eh sinnlos sein...

 

[pzypher]

Und wieso ist das ein Problem? Mir ist nicht klar, was du nun überhaupt wissen willst?! ???:L

Jede (bis auf evtl. die letzte) Wurzel hat genau 2 Nachfolger -> Binärer Baum; Ausserdem: linker Ast kleiner; rechter Ast größer als Vaterknoten -> siehe mein Problem

Mach es doch auf dem Blattpapier nach, dann kommst du bestimmt auf das selbe Ergebnis.
Falls ich es mir richtig vorstelle, dass muss du, damit dein Baum "ausbalanciert" ist, jeweils die "Mitte" hinzufügen:
zuerst 30, dann 15 und 45, dann 7, 22, 38, 52 usw.
Einfach mal in einer Reihe alle Zahlen reinzuknallen wird nicht klappen.

Ich werds probieren, danke

Wenn man einen ausbalancierten Baum haben will, dann sollte der Baum selbst aber dafür sorgen, dass er ausbalanciert ist und nicht der Benutzer beim Einfügen der Werte.
Wenn alle einzutragenen Werte vorher bekannt sind, dann wird der Baum ja eh sinnlos sein...

Der Benutzer gibt ja nur ein, welche Zahlen von n - m er im ausbalancierten Baum haben möchte. Und genau das wie bei: "sollte der Baum selbst aber dafür sorgen, dass er ausbalanciert ist" möchte ich ja herausfinden! 😉

 

[Sesostris]

Wenn du in einen normalen binären Suchbaum die Zahlen 1 bis 60 aufsteigend sortiert einfügst, hast du einen zur linearen Liste entarteten Baum. Da das für gewöhnlich unerwünscht ist, gibt es auch sogenannte balancierte Bäume, die durch geschicktes Rotieren die Blätter "balanciert" auf alle Äste verteilen und damit überlange Äste vermeiden. Wie Fant bereits geschrieben hat, sollte der Baum für diese Balancierung sorgen und nicht der Benutzer, Stichwort: Self-balancing binary search tree

 

[Fant]

Jede (bis auf evtl. die letzte) Wurzel hat genau 2 Nachfolger -> Binärer Baum; Ausserdem: linker Ast kleiner; rechter Ast größer als Vaterknoten -> siehe mein Problem

Das geht doch so überhaupt nicht. Wenn du in einen Baum 2 Element einfügst, dann ist diese Bedingung schon verletzt. Es geht einfach darum, dass jeder Knoten höchstens zwei Nachfolger besitzt.
Wenn du einen ausbalancierten Baum haben willst, dann solltest du wie vorher schon angesprochen wirklich einen anderen Baum verwenden.

 

[XHelp]

Binärbaum heißt nicht, dass jeder Knoten (es gibt übrigens nur eine einzige Wurzel im Baum) IMMER 2 Kinder hat, sondern NICHT MEHR ALS 2 Kinder.

 

[pzypher]

Alles klar, danke, dann war das ein Missverständnis meinerseits. Ich werd mich mit der neuen Erkenntnis dann nochmal dranhocken und nachdenken 😉