Algorithmen und Datenstrukturen · Junior · Frage 51 von 75
Was passiert, wenn man die Werte 1, 2, 3, 4, 5 der Reihe nach in einen einfachen (nicht balancierenden) BST einfügt?
- 1Der Baum balanciert sich automatisch
- 2Das Einfügen scheitert, weil die Werte zufällig sein müssen
- 3Der Baum wird zur Kette, und Operationen verschlechtern sich zu O(n)
Antwort zeigen
Richtige Antwort: Der Baum wird zur Kette, und Operationen verschlechtern sich zu O(n)
Erklärung
Jeder neue Wert ist größer als alle vorigen und geht nach rechts, der Baum wird also zur verketteten Liste. Selbstbalancierende Bäume (AVL, Rot-Schwarz) rotieren Knoten, um die Höhe bei O(log n) zu halten.