-4
Wie hoch ist die Zeitkomplexität beim Einfügen eines Knotens in einen binären Suchbaum?Wie hoch ist die Zeitkomplexität beim Einfügen eines Knotens in einen binären Suchbaum?
A
Antwort
2
O(n) wobei n die Anzahl der Knoten ist. Das passiert zum Beispiel, wenn Sie alle Schlüssel in einer geordneten Weise einfügen
+0
Ja, der Binärbaum ist in diesem Fall nicht besser als eine einfach verknüpfte Liste. – duffymo
+0
Es gibt selbstabgleichende Binärbäume, z.B. [AVL-Bäume] (https://en.wikipedia.org/wiki/AVL_tree) oder [rot-schwarze Bäume] (https://en.wikipedia.org/wiki/Red-black_tree). – user3386109
+0
ja @ user3386109, aber ohne Klärung wird davon ausgegangen, dass es keine Bilanzierungsstrategie gibt. – lrleon
4
Wenn Sie einen "reinen" binären Suchbaum haben, der keine Balancierung durchführt, dann ist die Worst-Case-Laufzeit für das Einfügen eines Elements Θ (n). Dies passiert, wenn Sie einen degenerierten binären Suchbaum haben (einer, bei dem jeder Knoten genau ein Kind hat) und das Element, das Sie am Ende einfügen, endet als Kind des tiefsten Knotens. Wenn Sie beispielsweise versuchen, eine BST zu erstellen, indem Sie die Zahlen 1, 2, 3, ..., n so eingeben, dass Sie bei jedem Schritt entweder die kleinste oder die größte der verbleibenden Zahlen einfügen, wird dieser Fall ausgelöst .
Wenn Sie einen selbstbalancierenden binären Suchbaum verwenden, z. B. einen AVL-Baum oder einen Rot/Schwarz-Baum, ist die Worst-Case-Laufzeit Θ (log n), da diese Bäume die Höhe des Baumes nie garantieren überschreitet Θ (log n) und die Laufzeit einer Insertion ist im schlimmsten Fall proportional zur Höhe des Baumes.
Was denkst du? O (n) falls du den ganzen Baum durchqueren musst. – Vucko