Les arbres binaires de recherche

Un arbre binaire de recherche équilibré de 1023 clés trouve n'importe laquelle en 10 comparaisons au plus ; construit à partir d'une entrée triée, les mêmes clés peuvent en demander 1023.

La recherche dichotomique, inscrite dans la forme

La recherche dichotomique dans un tableau trié trouve une clé en environ log₂ n vérifications, mais insérer dans un tableau trié déplace des valeurs. Une table de hachage insère rapidement, mais elle oublie l'ordre : elle ne peut pas facilement donner la plus petite clé ni la clé suivant 40. Un arbre binaire de recherche (ABR) vise les deux. Il est fait de nœuds, comme une liste chaînée, mais chaque nœud a deux pointeurs, left et right. Le nœud du haut est la racine ; un nœud sans enfants est une feuille.

Une seule règle en fait un arbre de recherche : pour chaque nœud, toutes les clés de son sous-arbre gauche sont plus petites, et toutes les clés de son sous-arbre droit sont plus grandes. Pour chercher une clé, on part de la racine et on compare. Égale : trouvée. Plus petite : on va à gauche ; plus grande : on va à droite. Chaque comparaison écarte tout un sous-arbre, comme la recherche dichotomique écarte la moitié de la liste. Chercher 60 dans l'arbre 50, 30, 70, 20, 40, 60, 80 compare avec 50, puis 70, puis 60 : 3 comparaisons.

L'insertion suit le même chemin. On va à gauche ou à droite jusqu'à ce que le pointeur voulu soit vide, et on y accroche le nouveau nœud. Insérer 45 compare avec 50 (à gauche), 30 (à droite) et 40 (à droite) ; 40 n'a pas d'enfant droit, donc 45 le devient. Supprimer un nœud qui n'est pas une feuille demande une idée de plus : les notes du MIT échangent son élément avec la clé suivante ou précédente dans l'ordre et suppriment à cet endroit à la place. La règle de comptage du labo est une comparaison par nœud du chemin.

La hauteur fait tout

Combien de comparaisons une recherche peut-elle demander ? Au plus une par niveau : le coût dépend donc de la hauteur de l'arbre, le nombre d'arêtes du plus long chemin de la racine jusqu'à une feuille. Les notes du MIT le disent ainsi : les opérations sur l'arbre s'exécutent en temps O(h). L'arbre 50, 30, 70, 20, 40, 60, 80 a une hauteur de 2 : aucune recherche ne demande donc plus de 3 comparaisons. Un arbre parfaitement équilibré de 1023 nœuds a une hauteur de 9 et demande au plus 10 comparaisons.

Mais la forme dépend de l'ordre d'insertion. Insère 10, 20, 30, 40, 50, 60, 70 dans l'ordre croissant : chaque clé est plus grande que toutes les précédentes, donc chaque nouveau nœud va à droite du dernier. L'arbre devient une chaîne de hauteur 6, et chercher 70 demande 7 comparaisons : une liste chaînée avec des pointeurs en trop. Avec 1023 clés triées, la pire recherche demande 1023 comparaisons au lieu de 10.

Les arbres équilibrés corrigent cela en se réorganisant après chaque insertion ou suppression. Le premier modèle a été l'arbre AVL, de Georgy Adelson-Velsky et Evgenii Landis en 1962, que traite le cours 7 du MIT. Il maintient, à chaque nœud, un écart d'au plus 1 entre les hauteurs des deux sous-arbres, et répare tout déséquilibre par de petits mouvements locaux appelés rotations. La hauteur reste ainsi en O(log n) : recherche, insertion et suppression restent en O(log n), quel que soit l'ordre d'arrivée des clés.

Les clés dans l'ordre, gratuitement

Un ABR garde plus que l'appartenance. Visite le sous-arbre gauche, puis le nœud, puis le sous-arbre droit, de façon récursive, et les clés sortent dans l'ordre croissant. Ce parcours infixe (le MIT l'appelle ordre de parcours) permet à un ABR de répondre à « plus petite clé », « plus grande clé » et « clé suivant 40 », les opérations d'ordre de l'interface d'ensemble du MIT qu'une table de hachage ne sait pas faire rapidement.