Laufzeiten für Suchbäume

• Laufzeit für Suchen ist proportional zur Höhe des Baumes (= längster Weg von Wurzel zu Blatt).
• wenn der Baum gut balanciert ist, dann enthält er bei Höhe h ungefähr n = 2^h Knoten
• Laufzeit ist $\sim$ h $\sim$ log₂n
• Beispiel: wenn Suchen in 1000 Knoten 1 Sekunden dauert, dann für 1000000 Knoten 2 Sekunden, 1000000000 Knoten 3 Sekunden usw.