Comment déterminer l'efficacité de la recherche dans un arbre de données déséquilibré?

L'efficacité de la recherche dans un arbre non équilibré est déterminée par la profondeur du nœud où se trouve l'élément recherché. Dans le pire cas, si l'arbre se dégrade en une liste, le temps de recherche devient linéaire — O(n). En moyenne, l'efficacité dépend de la structure de l'arbre et de la distribution des données. Pour l'évaluer, on utilise généralement la hauteur de l'arbre : plus l'arbre est haut, plus la recherche est longue. En Go, on peut implémenter la recherche dans un arbre binaire ainsi :

func search(node *Node, key int) *Node {
    if node == nil || node.key == key {
        return node
    }
    if key < node.key {
        return search(node.left, key)
    }
    return search(node.right, key)
}

Si l'arbre n'est pas équilibré, la profondeur peut être grande, ce qui réduit l'efficacité.