A Rappels algorithmiques
405
Fig. A.3 Trois arbres d’expressions booléennes : le second se déduit du premier, et le troisième
du second, par une rotation droite ; ces trois arbres représentent trois expressions équivalentes,
mais de hauteurs respectives 5, 4 et 3. Pour chaque rotation, nous indiquons par une flèche colorée
vers l’arbre initial le sommet « racine » pour cette opération, puis ce sommet garde la couleur de
la flèche dans l’arbre obtenu après rotation
A.2 Arbres binaires de recherche
La structure de données est la même que celle des arbres binaires : un nœud avec
deux fils. La contrainte d’ordre sur les valeurs des clés n’a pas de traduction directe
sur la définition de la structure de données ; elle est en fait implémentée par les
algorithmes de manipulation des arbres eux-mêmes.
405
Fig. A.3 Trois arbres d’expressions booléennes : le second se déduit du premier, et le troisième
du second, par une rotation droite ; ces trois arbres représentent trois expressions équivalentes,
mais de hauteurs respectives 5, 4 et 3. Pour chaque rotation, nous indiquons par une flèche colorée
vers l’arbre initial le sommet « racine » pour cette opération, puis ce sommet garde la couleur de
la flèche dans l’arbre obtenu après rotation
A.2 Arbres binaires de recherche
La structure de données est la même que celle des arbres binaires : un nœud avec
deux fils. La contrainte d’ordre sur les valeurs des clés n’a pas de traduction directe
sur la définition de la structure de données ; elle est en fait implémentée par les
algorithmes de manipulation des arbres eux-mêmes.