Erstellen eines binären Suchbaums mit der kleinsten Tiefe

Ich habe die Nummer von 1 bis 31 und ich muss einen binären Suchbaum mit diesen Zahlen mit der kleinsten Tiefe erstellen. Ich dachte daran, 31/2 zu teilen und 16 meine Wurzel zu machen. Danach 16/2 teilen und 8 als nächstes einfügen, aber das scheint nicht zu funktionieren. Gibt es einen Algorithmus, um zu wissen, in welcher Reihenfolge die Zahlen einzugeben sind, damit der Baum die kleinste mögliche Tiefe haben kann?Erstellen eines binären Suchbaums mit der kleinsten Tiefe

Quelle

2016-03-24 NBera

Es gibt Algorithmen, die das Balancieren von Bäumen ermöglichen, die dem besser entsprechen würden. Auf diese Weise spielt die Reihenfolge der Einfügung keine Rolle, aber der Baum ist minimal. [AVL] (https://en.wikipedia.org/wiki/AVL_tree) ist in der Nähe, Internal Path Reduction Bäume sind noch besser (garantiert Minimum), kann aber etwas länger dauern. – Obicere

Meistens irrelevant beiseite: 31/2 sollte 15 für die Wurzel geben, nicht 16. –

Wenn Sie Nummern 1-31, 31 Zahlen haben, möchten Sie 15 Zahlen links von der Wurzel und 15 Zahlen rechts.
Also ist die Wurzel 16 (das ist nicht 31/2, sondern 31/2 + 1).

Wiederholen Sie den gleichen Vorgang, der linke Teilbaum hat 15 Elemente, Sie wollen also sieben Zahlen auf jeder Seite dieses Teilbaums.
Die Wurzel des linken Teilbaums ist also 8 (das ist 15/2 + 1; hier ist ein Muster).
Eine ähnliche Berechnung gibt die Wurzel des rechten Teilbaums an.

Und so weiter.

Quelle

2016-03-24 18:33:03 molbdnilo

Erstellen eines binären Suchbaums mit der kleinsten Tiefe

Antwort

Verwandte Themen