Arbres binaires de recherche équilibrés (AVL)
On souhaite implémenter une structure de données permettant de gérer un dictionnaire de contacts, où chaque contact est identifié par un entier strictement positif (par exemple un identifiant unique).
On veut pouvoir :
- insérer un nouvel identifiant,
- rechercher un identifiant,
- garantir que ces opérations restent efficaces, même après un très grand nombre d'insertions.
Pour cela, on utilise un arbre binaire de recherche vérifiant de plus une condition de bon équilibre précise.
Représentation de l'arbre
Dans tout le problème, on utilisera la représentation suivante en Python :
- un arbre vide est représenté par None,
- un nœud est une liste de la forme :
[a, g, d]
où :
- a est la valeur entière stockée dans le nœud (l'identifiant),
- g est le sous-arbre gauche,
- d est le sous-arbre droit,
eux-mêmes représentés de la même manière (ou None s'ils sont vides).
On suppose que l'arbre vérifie toujours la propriété d'arbre binaire de recherche :
- toutes les valeurs du sous-arbre gauche sont strictement inférieures à la valeur du nœud ;
- toutes les valeurs du sous-arbre droit sont strictement supérieures à la valeur du nœud.
Écrire une fonction hauteur(a) qui retourne la hauteur de l'arbre a. (La hauteur d'un arbre vide est -1 par convention)
Exemple
arbre1 = [20, [12, None, None], [30, [25, None, None], [34, None, None]]]
2
def hauteur(a):
if a is None:
return -1
return 1 + max(hauteur(a[1]), hauteur(a[2]))
On définit le facteur d'équilibre d'un nœud (arbre non vide) a = [x, g, d] par :
$$\text{equilibre(a)} = \text{hauteur(g)} - \text{hauteur(d)}$$
Écrire une fonction equilibre(a) qui retourne le facteur d'équilibre du nœud a. Si a est vide, on pourra retourner 0 par convention.
Exemple
arbre1 = [20, [12, None, None], [30, [25, None, None], [34, None, None]]]
-1
def equilibre(a):
if a is None:
return 0
return hauteur(a[1]) - hauteur(a[2])
On dira qu'un arbre est bien équilibré si, pour tout nœud p de l'arbre, on a : $$-1 \leq \text{equilibre}(p) \leq 1.$$ Écrire une fonction est_bien_equilibre(a) qui retourne True si l'arbre a est bien équilibré, False sinon.
Exemple
arbre1 = [20, [12, None, None], [30, [25, None, None], [34, None, None]]]
True
def est_bien_equilibre(a):
if a is None:
return True
# Vérifier l'équilibre du nœud courant
if abs(equilibre(a)) > 1:
return False
# Vérifier récursivement les sous-arbres
return est_bien_equilibre(a[1]) and est_bien_equilibre(a[2])
Après une insertion, il est possible que certains nœuds deviennent trop « penchés » vers la gauche ou vers la droite. On veut alors réorganiser localement l'arbre autour de ce nœud, sans toucher au reste de l'arbre, tout en conservant :
- la propriété d'arbre binaire de recherche ;
- autant que possible, une bonne hauteur.
Pour cela, on utilise deux opérations élémentaires : rotation gauche et rotation droite.
Soit un nœud non vide a = [x, g, d] dont le sous-arbre droit d est lui-même non vide. On note d = [y, b, c].
La rotation gauche autour de a transforme :
- l'ancienne racine locale a en fils gauche de d,
- le sous-arbre b (gauche de d) en nouveau sous-arbre droit de a,
- d devient la nouvelle racine locale.
Écrire une fonction rotation_gauche(a) qui effectue une rotation gauche autour de la racine a (non vide), en supposant que son sous-arbre droit est non vide. La fonction retourne le nouvel arbre.
Exemple
arbre1 = [20, [12, None, None], [30, [25, None, None], [34, None, None]]]
[30, [20, [12, None, None], [25, None, None]], [34, None, None]]
def rotation_gauche(a):
# a = [x, g, d] avec d non vide
x, g, d = a
# d = [y, b, c]
y, b, c = d
# Nouvel arbre : [y, [x, g, b], c]
return [y, [x, g, b], c]
De manière symétrique, soit un nœud non vide a = [x, g, d] dont le sous-arbre gauche g est lui-même non vide. On note g = [y, b, c].
La rotation droite autour de a transforme :
- l'ancienne racine locale a en fils droit de g,
- le sous-arbre c (droit de g) en nouveau sous-arbre gauche de a,
- g devient la nouvelle racine locale.
Écrire une fonction rotation_droite(a) qui effectue une rotation droite autour de la racine a (non vide), en supposant que son sous-arbre gauche est non vide. La fonction retourne le nouvel arbre.
Exemple
[30, [20, [12, None, None], [25, None, None]], [34, None, None]]
[20, [12, None, None], [30, [25, None, None], [34, None, None]]]
def rotation_droite(a):
# a = [x, g, d] avec g non vide
x, g, d = a
# g = [y, b, c]
y, b, c = g
# Nouvel arbre : [y, b, [x, c, d]]
return [y, b, [x, c, d]]
On considère maintenant un nœud a (arbre non vide) dont les sous-arbres gauche et droit sont déjà bien équilibrés, mais pour lequel a lui-même peut être déséquilibré.
On admet que, dans les situations qui nous intéressent, le déséquilibre maximal est :
- equilibre(a) = 2 (trop penché à gauche),
- ou equilibre(a) = -2 (trop penché à droite).
Dans chaque cas, il est possible de corriger le déséquilibre en utilisant une ou deux rotations au niveau de a et de son fils direct.
Rotation simple
Une rotation simple est utilisée lorsque le déséquilibre est "linéaire", c'est-à-dire que les noeuds sont alignés dans la même direction (tous à gauche ou tous à droite).
Il existe deux types de rotations simples comme vu dans la partie 1 : gauche et droite.
Rotation droite:
Quand l'utiliser? Lorsque la balance d'un noeud est +2 (sous-arbre gauche trop lourd) et que la balance de son fils gauche est positive ou nulle (+1 ou 0). C'est le cas "Gauche-Gauche".
Rotation gauche :
Quand l'utiliser? Lorsque la balance d'un noeud est -2 (sous-arbre droit trop lourd) et que la balance de son fils droit est négative ou nulle (-1 ou 0). C'est le cas "Droit-Droit".
Rotation double
Une rotation double est utilisée lorsque le déséquilibre est "croisé", c'est-à-dire que les noeuds sont alignés en zigzag (un à gauche, l'autre à droite, ou vice versa).
Il existe deux types de rotations doubles : gauche-droite et droite-gauche.
Rotation gauche-droite :
Quand l'utiliser? Lorsque la balance d'un noeud est +2 (sous-arbre gauche trop lourd) et que la balance de son fils gauche est négative (-1). C'est le cas "Gauche-Droite".
Le déséquilibre est à gauche mais intérieur → rotation double.
Étape 1 — Rotation simple gauche sur 10:
Étape 2 — Rotation simple droite sur 20:
Rotation droite-gauche :
Quand l'utiliser? Lorsque la balance d'un noeud est -2 (sous-arbre droit trop lourd) et que la balance de son fils droit est positive (+1). C'est le cas "Droit-Gauche".
Le déséquilibre est à droite mais intérieur → rotation double.
Étape 1 — Rotation simple droite sur 20:
Étape 2 — Rotation simple gauche sur 10:
Écrire une fonction reequilibrer(a) qui prend en entrée la racine d'un arbre non vide a.
- On suppose que les sous-arbres gauche et droit de a sont déjà bien équilibrés (leur facteur d'équilibre est dans {-1, 0, 1}), mais que le facteur d'équilibre de a lui-même peut être 2 ou -2.
- La fonction doit appliquer les rotations (simple ou double) nécessaires pour rétablir l'équilibre (c'est-à-dire ramener le facteur d'équilibre de la nouvelle racine locale dans {-1, 0, 1}) et retourner la nouvelle racine locale de l'arbre équilibré.
Cas à traiter :
- Rotation droite simple : equilibre(a) = 2 et equilibre(a[1]) >= 0 (cas Gauche-Gauche)
- Rotation gauche simple : equilibre(a) = -2 et equilibre(a[2]) <= 0 (cas Droit-Droit)
- Rotation double gauche-droite : equilibre(a) = 2 et equilibre(a[1]) = -1
- Rotation double droite-gauche : equilibre(a) = -2 et equilibre(a[2]) = 1
Exemple
arbre2 = [20, [10, [2, None, None], [15, [12, None, None], [17, None, None]]], [26, None, None]]
[15,
[10, [2, None, None], [12, None, None]],
[20, [17, None, None], [26, None, None]]]
def reequilibrer(a):
if a is None:
return None
eq = equilibre(a)
# Cas Gauche-Gauche ou Gauche-Droit
if eq > 1:
if equilibre(a[1]) >= 0:
# Cas Gauche-Gauche : rotation droite simple
return rotation_droite(a)
else:
# Cas Gauche-Droit : double rotation
a[1] = rotation_gauche(a[1])
return rotation_droite(a)
# Cas Droit-Droit ou Droit-Gauche
if eq < -1:
if equilibre(a[2]) <= 0:
# Cas Droit-Droit : rotation gauche simple
return rotation_gauche(a)
else:
# Cas Droit-Gauche : double rotation
a[2] = rotation_droite(a[2])
return rotation_gauche(a)
# Déjà équilibré
return a
On veut maintenant insérer une nouvelle clé x dans l'arbre, de manière à :
- respecter la propriété d'arbre binaire de recherche ;
- corriger localement le déséquilibre éventuel.
On suppose que toutes les clés sont distinctes : si x est déjà présent, l'arbre ne doit pas être modifié.
Écrire une fonction inserer(a, x) qui, étant donné un arbre binaire de recherche a et une clé x, insère cette clé dans l'arbre tout en maintenant la propriété d'ordre d'un arbre binaire de recherche,
- puis rééquilibre localement le nœud si cela est nécessaire.
- La fonction doit retourner le nouvel arbre obtenu après insertion.
Exemple
Après insertion de 2, l'arbre devient déséquilibré :
Après rééquilibrage, l'arbre devient équilibré :
arbre = [10, [5, [4, [3, None, None], None], [8, None, None]], [15, [12, None, None], [18, None, None]]]
x = 2
[10,
[5,
[3,
[2, None, None],
[4, None, None]],
[8, None, None]],
[15, [12, None, None], [18, None, None]]]
def inserer(a, x):
if a is None:
return [x, None, None]
val, g, d = a
if x < val:
g = inserer(g, x)
elif x > val:
d = inserer(d, x)
else:
# x déjà présent, pas de modification
return a
# Créer le nouveau nœud avec les sous-arbres modifiés
nouveau = [val, g, d]
# Rééquilibrer si nécessaire
return reequilibrer(nouveau)
On se place maintenant dans le cas de la suppression d'une clé dans un arbre. Lorsqu'on supprime une valeur dans un arbre binaire ordonné, trois situations peuvent se présenter :
- le noeud est une feuille;
- le noeud possède un seul enfant;
- le noeud possède deux enfants, auquel cas sa valeur doit être remplacée par celle de son successeur dans le sous-arbre droit (le plus petit élément de ce sous-arbre), puis ce successeur doit être supprimé.
Après cette suppression classique, il se peut que l'arbre perde sa propriété d'équilibre : il faut alors restaurer l'équilibre en appliquant une rotation simple ou double, selon la configuration des sous-arbres.
Écrire une fonction successeur(a) qui prend en paramètre un sous-arbre a non vide et qui retourne la plus petite valeur contenue dans ce sous-arbre.
def successeur(a):
if a is None:
return None
# Aller le plus à gauche possible
while a[1] is not None:
a = a[1]
return a[0]
Écrire une fonction supprimer(a, x) qui :
- recherche la clé x dans l'arbre a ;
- la supprime en respectant les trois cas classiques de suppression dans un arbre ordonné ;
- si nécessaire, rééquilibre localement le nœud courant en appliquant une rotation simple ou double ;
- retourne l'arbre résultant.
Exemple
arbre4 = [10, [5, [4, [3, None, None], None], [8, None, None]], [15, [12, None, None], [18, None, None]]]
x = 5
[10,
[4, [3, None, None], [8, None, None]],
[15, [12, None, None], [18, None, None]]]
def supprimer(a, x):
if a is None:
return None
val, g, d = a
if x < val:
g = supprimer(g, x)
elif x > val:
d = supprimer(d, x)
else:
# Cas 1 : nœud feuille
if g is None and d is None:
return None
# Cas 2 : un seul enfant
if g is None:
return d
if d is None:
return g
# Cas 3 : deux enfants
# Remplacer par le successeur (plus petit du sous-arbre droit)
succ = successeur(d)
d = supprimer(d, succ)
a = [succ, g, d]
return reequilibrer(a)
# Créer le nouveau nœud et rééquilibrer
nouveau = [val, g, d]
return reequilibrer(nouveau)
Une application très utile des arbres équilibrés : récupérer rapidement les valeurs dans un intervalle. On souhaite extraire uniquement les éléments compris entre deux bornes G et D.
Écrire une fonction récursive elements_intervalle(a, G, D) qui retourne une liste contenant toutes les valeurs v de l'arbre telles que G ≤ v ≤ D, dans l'ordre croissant.
Exploiter la structure équilibrée pour éviter un simple parcours complet.
Exemple
arbre3 = [15, [10, [5, None, None], [12, None, None]], [20, [17, None, None], [26, None, None]]]
G = 14
D = 22
[15, 17, 20]
def elements_intervalle(a, G, D):
if a is None:
return []
val, g, d = a
resultat = []
# Si val est dans l'intervalle, on pourra l'ajouter
if G <= val <= D:
# D'abord les éléments plus petits (gauche)
resultat.extend(elements_intervalle(g, G, D))
# Puis la valeur courante
resultat.append(val)
# Enfin les éléments plus grands (droite)
resultat.extend(elements_intervalle(d, G, D))
elif val < G:
# Si val < G, tout ce qui est à gauche est aussi < G
# Donc on cherche seulement à droite
resultat.extend(elements_intervalle(d, G, D))
else: # val > D
# Si val > D, tout ce qui est à droite est aussi > D
# Donc on cherche seulement à gauche
resultat.extend(elements_intervalle(g, G, D))
return resultat
Optimisation
Cette implémentation exploite la propriété d'ordre de l'arbre pour ne parcourir que les branches susceptibles de contenir des valeurs dans l'intervalle, ce qui est plus efficace qu'un parcours complet dans un grand arbre équilibré.
Discussion (0)
Soyez le premier à laisser un commentaire !
Laisser un commentaire
Votre commentaire sera visible après modération.