Algorithmen und Datenstrukturen · Junior · Frage 50 von 75
Wie lange dauert die Suche nach einem Wert in einem balancierten BST mit n Knoten?
- 1O(log n)
- 2O(n)
- 3O(1)
Antwort zeigen
Richtige Antwort: O(log n)
Erklärung
Jeder Schritt geht eine Ebene tiefer, und ein balancierter Baum hat etwa log₂ n Ebenen. Entartet der Baum zu einer Kette (etwa nach dem Einfügen sortierter Werte), wird die Suche O(n).