Frage:
Sei X eine unsortierte Menge von n vergleichbaren Elementen.Zeige: Jeder beliebige Algorithmus zum Erstellen eines binären Suchbaums mit denElementen aus X benötigt Zeit Ω(n log n).
Hallo an alle, könnte jemand damit behilflich sein. Ich habe Probleme mit Laufzeiten, wie genau kann ich denn das Zeigen?
Hallo :-)
Betrachte doch mal den Fall, dass ein binärer Suchbaum (=BST) balanciert ist. Diese haben nämlich Höhe \(h:=\lfloor \log_2(n)\rfloor\), wobei \(n\) die Anzahl an Objekten beschreibt. Andere Arten von binären Suchbäumen haben mindestens diese Höhe. Beim Einfügen eines Objektes in den bereits vorhandenen BST, müssen also \(h\) Vergleiche durchgeführt werden.
Ein anderes Problem?
Willkommen bei der Stacklounge! Stell deine Frage einfach und kostenlos