Beweisen zum Erstellen eines binären Suchbaum mit Laufzeit

Question

Frage:

Sei X eine unsortierte Menge von n vergleichbaren Elementen.
Zeige: Jeder beliebige Algorithmus zum Erstellen eines binären Suchbaums mit den
Elementen 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?

Answer 1

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.