Arbres binaires [Résolu]

Si c'est un arbre équilibre (arbre rouge noir par exemple) c'est du O(log(n))
http://en.wikipedia.org/wiki/Red-black_tree

Preuve "intuitive" : l'arbre est équilibré et à chaque branchement chaque individu est séparé en deux groupes de même taille (à 1 près). La hauteur de l'arbre est donc vérifie donc 2^h = n, soit h = log(n)/log(2). Comme il y a autant d'évaluation que d'étage dans l'arbre (soit h), la complexité est bien du O(log(n))

Bonne chance