0 Daumen
587 Aufrufe


In einen binären Suchbaum sollen die Schlüssel 1, 2, 3, . . . , n − 1 eingefügt werden. Geben
Sie eine Einfügereihenfolge an, sodass die Höhe des entstehenden Baums
(a) in Θ(n)
(b) in Θ(log n)
liegt.

Angenommen n = 2m ist für m ∈ N.

Skizzieren Sie die entstehenden Bäume

Avatar von

1 Antwort

0 Daumen

Hallo, ein vollständiger binärer Baum hat Höhe \(⌊\log_2(n)⌋\), bzw dann in Theta-Notation \(\Theta(\log(n))\). Dieser Baum ist also so strukturiert, sodass jeder Knoten höchstens zwei Kindknoten besitzt. Nun musst du jetzt mit den Einfügemethoden die ihr definiert haben müsst, so arbeiten bzw. sodass die Suchbaumeigenschaft eines Binärbaumes erfüllt ist:

-> Ist \(x\) Knoten in \(T\) und \(y\) Knoten in linkem Teilbaum von \(x\), so ist
\(y.key ≤ x.key\).
-> Ist \(x\) Knoten in \(T\) und \(y\) Knoten in rechtem Teilbaum von \(x\), so ist
\(y.key ≥ x.key\).

Für den linearen Fall kannst du ja das mittlere Element von \(1,2,...,n-1\) als Wurzel nehmen den Rest entsprechend der Suchbaumeigenschaft nun so einfügen, sodass du eine ,,V-Form" erkennst.

Avatar von

Ein anderes Problem?

Stell deine Frage

Ähnliche Fragen

0 Daumen
1 Antwort
+1 Daumen
1 Antwort
Gefragt 14 Jun 2016 von Gast

Willkommen bei der Stacklounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community