Πόσο χρόνο λειτουργεί το δέντρο αναζήτησης;

Ο χρόνος αναζήτησης σε ένα δέντρο εξαρτάται από τον τύπο του δέντρου και την λειτουργία. Για ισορροπημένα δυαδικά δέντρα αναζήτησης (π.χ., AVL, κόκκινο-μαύρο δέντρο), η αναζήτηση, η εισαγωγή και η διαγραφή λειτουργούν σε O(log n), όπου n είναι ο αριθμός των στοιχείων. Στην χειρότερη περίπτωση, για ένα μη ισορροπημένο δυαδικό δέντρο, η αναζήτηση μπορεί να υποβαθμιστεί σε O(n). Για παράδειγμα, στη Go, μπορεί να υλοποιηθεί μια δυαδική αναζήτηση σε μια ταξινομημένη λίστα σε O(log n):

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 // δεν βρέθηκε
}