Binärer Suchbaum - Frage
-
Ich verstehe die folgende Aufgabe nicht:
Zeigen Sie, dass sich die Wahrscheinlichkeitsverteilung, welche resultiert, wenn
man einen binaren Suchbaum aus n Schlusseln zufallig aufgebaut, von der Ver-
teilung unterscheidet, die entsteht, wenn man gleichverteilt einen binaren Such-
baum auf n Elementen auswahlt. (Hinweis: Betrachten Sie den Fall n = 3.)Kann mir jmd erklären, was ich tun soll?
-
Tut mir leid, aber die Frage verstehe ich auch nicht - zumindest nicht ohne die Zusammenhänge zu kennen. (ich bin nicht einmal sicher, was für eine Wahrscheinlichkeitsverteilung in dem Zusammenhang für eine Rolle spielen soll)
Der einzige Ansatzpunkt, den ich da sehe, sind entartete Binärbäume:
Wenn du n aufsteigend sortierte Zahlen in einen anfangs leeren Baum einfügst, erhältst du (ohne Balancierungsmaßnahmen) eine lineare Liste, da bei allen Knoten nur der rechte Nachbar genutzt wird. Wenn du die Zahlen in zufälliger Reihenfolge einfügst, bekommst du (wahrscheinlich) einen Baum, bei dem die linken und rechten Nachbarn halbwegs gleichmäßig ausgenutzt werden.
-
Vielleicht ein kleiner Denkansatz:
Wieviele verschiedene Reihenfolgen gibt es, um {1,2,3} nacheinander in einen Suchbaum einzufügen?
Wieviele verschiedene binäre Suchbäume erhält man auf diese Art?
-
Hm das ist klar, dass sich die Anzahl der Suchbäume von n! unterscheidet, aber was soll ich antworten?
SOll ich einfach alle Suchbäume aufmalen und sagen, dass manche Einfügereihenfolgen keinen Unterschied im Baum ergeben (2,1,3 und 2,3,1 zB)?
Und was hat das mit Wahrscheinlichkeitsverteilung zu tun?
-
Ganz so einfach nicht, aber das ist ein Teil des Arguments.
Es gibt 5 verschiedene Suchbäume, von denen man einen auf 2 Arten kriegt, die anderen 4 nur auf eine. Dieser eine ist also - wenn man zufällig einfügt - wahrscheinlicher als die anderen. Und damit ist das eine andere Verteilung als wenn alle 5 gleichverteilt sind.