Wie lange arbeitet der Suchbaum?

Die Suchzeit in einem Baum hängt vom Baumtyp und der Operation ab. Für balancierte binäre Suchbäume (z.B. AVL, Rot-Schwarz-Baum) arbeiten Suche, Einfügen und Löschen in O(log n), wobei n die Anzahl der Elemente ist. Im schlimmsten Fall kann die Suche bei einem unausgeglichenen binären Baum auf O(n) degradieren. Zum Beispiel kann man in Go eine binäre Suche in einem sortierten Slice in O(log n) implementieren:

func binarySearch(arr []int, target int) int {
    left, right := 0, len(arr)-1
    for left <= right {
        mid := left + (right-left)/2
        if arr[mid] == target {
            return mid
        } else if arr[mid] < target {
            left = mid + 1
        } else {
            right = mid - 1
        }
    }
    return -1 // nicht gefunden
}