2016-08-28 10 views
-2

Geben Sie einen Algorithmus an, der mit einer anfänglich leeren BST beginnt und "n" zufällige Einfügungen vornimmt. Verwenden Sie einen einheitlichen Zufallsgenerator, um die einzufügenden Werte zu erhalten. Messen Sie die Höhe der resultierenden BST und teilen Sie diese durch log2n.Folgen Sie dies für n = 100,500,1000,2000,3000 ...., 10000.Plot das Verhältnis Höhe/log2n als eine Funktion von n.Das Verhältnis sollte ungefähr konstant sein (um 2) .Vergewissern Sie sich, dass dies so ist.
:
Nun wissen wir alle, dass die Höhe einer BST log2n ist, wobei 'n' die Anzahl der Elemente in der Struktur ist. Wenn es eine links schief/rechts schief Baum ist, dann ist die Höhe gleich zu "n". Also, wenn wir die Höhe hier messen, welche Höhe sollten wir für die Insertionen annehmen, sind zufällig.Ich meine, wie könnte das Verhältnis immer um 2 sein.
Ich hämmere meinen Kopf gegen diesen.Binärer Suchbaum

+0

[DIESE] (https://www.sitepoint.com/hierarchical-data-database-2/) wird Ihnen helfen –

Antwort

1

Wenn es sich um einen linkssymmetrischen/rechtsschiefen Baum handelt, ist die Höhe gleich 'n'. Wenn wir also die Höhe hier messen, welche Höhe sollten wir davon ausgehen, für die Einfügungen sind zufällig

Die Höhe für einen solchen binären Baum n ist. Sie müssen hier nichts annehmen. Außerdem Höhe von perfekt ausgewogen BST ist log (n) (nicht im allgemeinen)


auf Ihre Frage kommen, ich nehme an, Sie fragen Höhe zu finden zufällig binären Baum zu bauen. In diesem Fall müssen Sie die Höhe eines bestimmten Binärbaums nicht berechnen.

Auch wenn die Höhe des verzerrten Baumes n ist, ist die Wahrscheinlichkeit, dass es in einer gleichmäßigen Zufallsverteilung erzeugt wird, sehr viel geringer. Also, wenn Sie die Höhe der zufälligen BST berechnen, wird es als O (log n) herauskommen.

Für eine genaue Berechnung finden Randomly build BST has logarithmic height

+0

Ja, ich weiß, dass ein BST a hat zufällig bauen logarithmische Höhe ...... aber was ich frage ist: wie könnte das Verhältnis immer nahe bei 2 sein ...... lese meine Frage sorgfältig ... hast du eine Lösung? – Reckoner

+0

Haben Sie den Link durchgelesen? Sie haben die erwartete Höhe angezeigt = 2 * log (n) –

+0

Yupp Ich habe es jetzt durchgemacht ....... hab es geschafft – Reckoner