Hallo,
habe eine Frage zu den Suchbäumen maximaler Höhe.
Nach meiner Berechnung sind es ziemlich viele ( 2^5 =32). Müssen wir da wirklich jeden einzeln aufzeichnen, oder können wir nicht einfach nur das Muster angeben, wie man die erzeugen kann?
Nach meiner Berechnung sind es ziemlich viele ( 2^5 =32). Müssen wir da wirklich jeden einzeln aufzeichnen, oder können wir nicht einfach nur das Muster angeben, wie man die erzeugen kann?
In einem Suchbaum werden doch total geordneten Mengen verwendet. Unter Beachtung der Reihenfolge der natürlichen Zahlen habe ich wesentlich weniger Bäume erhalten ;)
Ja die Mengen sind geordnet, aber es gibt ja ziemlich viele Verzweigungsmoeglichkeiten.
Wichtig ist ja nur, dass pro Ebene nur ein Knoten vorhanden ist, also dass ein Knoten nur ein Kind hat.
Ja die Mengen sind geordnet, aber es gibt ja ziemlich viele Verzweigungsmoeglichkeiten.
Wichtig ist ja nur, dass pro Ebene nur ein Knoten vorhanden ist, also dass ein Knoten nur ein Kind hat.
Ja und wie kommst du dann auf soviele Bäume mit maximaler Höhe? Also ein maximal hoher binärer Suchbaum muss doch nicht ausbalanciert sein, oder?
Naja Bsp ein Baum der Hoehe 3 für die Liste 10,15,20
Dann gibt es 20 - 15 -10
Es gibt auch 20-10-15
Es gibt auch 10-15-20
Es gibt auch 10-20-15
natürlich hängen die Knoten immer verschieden, also einmal linker Nachfolger und einmal rechter Nachfolger. Für 3 Elemente 2^2 .
Für 6 Elemente gibts 2^5 Möglichkeiten.
^^ die haben aber nicht alle maximale Höhe bzw. sind keine Suchbäume!
Doch.
20
|
15
|
10
20
|
10
|
15
10
|
15
|
20
10
|
20
|
15
Sorry der erste ist
20
|
15
|
10
Doch.
Nein, das sind keine Suchbäume. Sieh dir nochmal die Definition
an. Vielleicht hast du "child" und "subtree" in der Definition verwechselt.
Mhh. Also laut Definition ausm Skript ist ein Suchbaum ein Baum mit der Eigenschaft:
Ist y ein Knoten im linken Teilbaum von x, dann gilt key[y] < key[x]
" … rechten Teilbaum von x, dann gilt key[y] >= key[x]
Kann mir einer sagen, wo das da verletzt ist? Ich seh das irgendwie nicht….
Ich meine auch, dass das "ziemlich viele" Suchbäume sind. Eine Angabe des
Konstruktionsverfahrens reicht dann aber. Die müssen nicht alle gezeichnet
werden. (Eine Begründung/ein Beweis warum man alle diese (nicht mehr, nicht
weniger) hat ist aber auf jeden Fall nötig!)
Frank :)
Huch, da hab ich totalen Quatsch erzählt.
Das sind natürlich Suchbäume.
Und es gibt nur 2 Suchbäume minimaler Höhe, oder?
Das würd ich so bestätigen.
nun komme ich auch auf 4:)
Huch, da hab ich totalen Quatsch erzählt.
Das sind natürlich Suchbäume.
Na zum Glück haste das noch gemerkt!
Hallo,
habe eine Frage zu den Suchbäumen maximaler Höhe.
Nach meiner Berechnung sind es ziemlich viele ( 2^5 =32). Müssen wir da wirklich jeden einzeln aufzeichnen, oder können wir nicht einfach nur das Muster angeben, wie man die erzeugen kann?
Ich sagte heute in der Vorlesung, dass uns drei gezeichnete maximale Suchbäume zu 2.1 reichen.
Das war ein Fehler "die" statt "drei", den keiner gemerkt hatte!
sorry!!
Matthias Jantzen
