Combien de temps fonctionne l'arbre de recherche?

Le temps de recherche dans un arbre dépend du type d'arbre et de l'opération. Pour les arbres binaires de recherche équilibrés (par exemple, AVL, arbre rouge-noir), la recherche, l'insertion et la suppression fonctionnent en O(log n), où n est le nombre d'éléments. En cas défavorable, pour un arbre binaire non équilibré, la recherche peut se dégrader en O(n). Par exemple, en Go, on peut implémenter une recherche binaire sur un slice trié en 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 // non trouvé
}