0 Daumen
115 Aufrufe

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?

von

1 Antwort

0 Daumen
 
Beste Antwort

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.

von

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community