On insère dans cet ordre les valeurs 1, 2, 3, …, 1000 dans un arbre binaire de recherche vide (sans aucun rééquilibrage). Lors de la recherche de 1000 dans cet arbre, combien de nœuds sont comparés, à partir de la racine, avant de le trouver ?

Réponse : C. 1000

Quand les valeurs sont insérées dans l'ordre croissant, chaque nouvelle valeur devient l'enfant droit du maximum précédent : l'arbre devient une chaîne unique qui ne s'étend que vers la droite (hauteur 999). 1000 se trouve tout en bas : il est donc comparé aux 1000 nœuds 1, 2, …, 1000, soit O(n), comme le parcours d'une liste chaînée depuis le début. Un arbre équilibré n'aurait qu'environ log₂ 1000 ≈ 10 niveaux ; utiliser un arbre binaire de recherche auto-équilibré comme un arbre AVL ou un arbre rouge-noir, qui se réorganise à chaque insertion et suppression, maintient donc le pire cas en O(log n).