Binärbaum Algorithem

Question

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

Answer 1

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.