404
A Rappels algorithmiques
Fig. A.2 L’effet d’une rotation droite sur un arbre binaire
A.1.4 Rotations d’arbres binaires
Nous définissons dans cette section la rotation droite dont l’effet est décrit dans la
figure A.2, et l’algorithme donné ci-dessous. Il existe naturellement une rotation
gauche, qui se déduit aisément de la rotation droite par symétrie.
Les rotations sont un outil de choix pour rééquilibrer les arbres binaires, par
exemple les arbres binaires de recherche : elles ne modifient pas l’ordre préfixe
des clés, et une rotation appliquée à un arbre binaire de recherche fournit un autre
arbre binaire de recherche. Elles interviennent notamment dans les algorithmes de
mise à jour des arbres AVL [50, 111]. Elles permettent aussi de concevoir des
algorithmes auto-adaptatifs qui font remonter vers la racine de l’arbre les clés les
plus fréquemment recherchées (que l’arbre soit organisé en arbre de recherche,
ou non). Nous donnons dans la figure A.3 un exemple de leur effet sur un arbre
représentant une expression booléenne : deux rotations successives permettent de
transformer l’arbre en un arbre représentant une expression calculant la même
fonction booléenne que l’arbre initial.
Fonction rotationDroite(Arbre A)
// Précondition : A est un arbre non vide, dont l’enfant droit est également
non vide.
// Postcondition : retourne A, qui est maintenant l’arbre obtenu à partir de
l’arbre de départ par une rotation droite.
// Variable locale : Arbre temp
temp = A.droit
A.droit = temp.gauche
temp.gauche = A
A = temp
retourner A
A Rappels algorithmiques
Fig. A.2 L’effet d’une rotation droite sur un arbre binaire
A.1.4 Rotations d’arbres binaires
Nous définissons dans cette section la rotation droite dont l’effet est décrit dans la
figure A.2, et l’algorithme donné ci-dessous. Il existe naturellement une rotation
gauche, qui se déduit aisément de la rotation droite par symétrie.
Les rotations sont un outil de choix pour rééquilibrer les arbres binaires, par
exemple les arbres binaires de recherche : elles ne modifient pas l’ordre préfixe
des clés, et une rotation appliquée à un arbre binaire de recherche fournit un autre
arbre binaire de recherche. Elles interviennent notamment dans les algorithmes de
mise à jour des arbres AVL [50, 111]. Elles permettent aussi de concevoir des
algorithmes auto-adaptatifs qui font remonter vers la racine de l’arbre les clés les
plus fréquemment recherchées (que l’arbre soit organisé en arbre de recherche,
ou non). Nous donnons dans la figure A.3 un exemple de leur effet sur un arbre
représentant une expression booléenne : deux rotations successives permettent de
transformer l’arbre en un arbre représentant une expression calculant la même
fonction booléenne que l’arbre initial.
Fonction rotationDroite(Arbre A)
// Précondition : A est un arbre non vide, dont l’enfant droit est également
non vide.
// Postcondition : retourne A, qui est maintenant l’arbre obtenu à partir de
l’arbre de départ par une rotation droite.
// Variable locale : Arbre temp
temp = A.droit
A.droit = temp.gauche
temp.gauche = A
A = temp
retourner A