binärer Suchbaum < Datenstrukturen < Schule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 17:03 Do 21.05.2009 | | Autor: | Chibby |
| Aufgabe | a) Wie viele verschiedene binäre Suchbäume gibt es für n Objekte?
b) Welche Höhe h hat ein binärer Suchbaum für n Objekte? |
Hallo, obige Fragen kann ich nicht lösen
zu a) dachte ich n! ist eine gute Abschätzung nach oben.
bei b) dachte ich an [mm] log_2(n)
[/mm]
Danke für die Antworten
Chibby
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 14:18 Fr 22.05.2009 | | Autor: | bazzzty |
Hallo,
zunächst: Für mich ist ein binärer Suchbaum jeder Baum mit Wurzel, in dem jeder Knoten maximal zwei Kinder hat und im linken Teilbaum eines Knotens nur kleinere Elemente vorkommen dürfen, im rechten nur größere, so wie ![[]](/images/popup.gif) hier.
Der Einfachheit halber nehme ich an, die "Objekte" sind genau die Zahlen von 1 bis n.
> a) Wie viele verschiedene binäre Suchbäume gibt es für n
> Objekte?
Wenn ich Dir irgendeinen binären Suchbaum mit n Knoten gebe und nicht hinschreibe, welcher Knoten welche Zahl darstellt, dann solltest Du die Zahlen eindeutig ergänzen können. Also ist jeder Binärbaum mit n Knoten und einer Wurzel als Suchbaum geeignet. Und davon gibt es viele.
> zu a) dachte ich n! ist eine gute Abschätzung nach oben.
n! geht zwar in die richtige Richtung, ist aber noch zu wenig. Aber das ist eigentlich keine Frage, die man mit Schulmathematik lösen kann, habe ich was übersehen?
> b) Welche Höhe h hat ein binärer Suchbaum für n Objekte?
>
> bei b) dachte ich an [mm]log_2(n)[/mm]
Das gilt nur für balancierte Suchbäume. Im allgemeinen ist ja auch erlaubt, dass ein binärer Suchbaum das kleinste Element oben steht, und es immer nur nach rechts geht, qie in einer Liste. So ein Baum wäre dann sehr viel höher!
|
|
|
| |
|
| Status: |
(Frage) überfällig  | | Datum: | 09:07 So 24.05.2009 | | Autor: | Chibby |
| Aufgabe | a) Wie viele verschiedene binäre Suchbäume gibt es für n Objekte?
b) Welche Höhe h hat ein binärer Suchbaum für n Objekte? |
Hi!
> zunächst: Für mich ist ein binärer Suchbaum jeder Baum mit
> Wurzel, in dem jeder Knoten maximal zwei Kinder hat und im
> linken Teilbaum eines Knotens nur kleinere Elemente
> vorkommen dürfen, im rechten nur größere, so wie
> hier.
So meinte ich das auch, nur dass er noch unbalanciert ist.
> Der Einfachheit halber nehme ich an, die "Objekte" sind
> genau die Zahlen von 1 bis n.
Ok
> > a) Wie viele verschiedene binäre Suchbäume gibt es für n
> > Objekte?
>
> Wenn ich Dir irgendeinen binären Suchbaum mit n Knoten gebe
> und nicht hinschreibe, welcher Knoten welche Zahl
> darstellt, dann solltest Du die Zahlen eindeutig ergänzen
> können. Also ist jeder Binärbaum mit n Knoten und einer
> Wurzel als Suchbaum geeignet. Und davon gibt es viele.
>
> > zu a) dachte ich n! ist eine gute Abschätzung nach oben.
>
>
> n! geht zwar in die richtige Richtung, ist aber noch zu
> wenig. Aber das ist eigentlich keine Frage, die man mit
> Schulmathematik lösen kann, habe ich was übersehen?
Ich soll ja auch kein Beweis finden, sondern die Lösung, und die ist mir bis jetzt noch nicht klar.
> > b) Welche Höhe h hat ein binärer Suchbaum für n Objekte?
> >
> > bei b) dachte ich an [mm]log_2(n)[/mm]
>
> Das gilt nur für balancierte Suchbäume. Im allgemeinen ist
> ja auch erlaubt, dass ein binärer Suchbaum das kleinste
> Element oben steht, und es immer nur nach rechts geht, qie
> in einer Liste. So ein Baum wäre dann sehr viel höher!
Ja, dann maximal n?
Ist ja irgendwie logisch
Grüße von
Chibby
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 09:20 Sa 30.05.2009 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
