My IT Utilities

Arbre AVL

Partez d'un arbre AVL aléatoire et insérez, recherchez ou supprimez des valeurs pas à pas : voyez le facteur d'équilibre de chaque nœud, les rotations LL, RR, LR et RL, sa forme en tableau et le code C++ mis en évidence.

Tout est simulé dans ce navigateur ; rien n'est envoyé à un serveur.

Aucune étape

Aucune étape

Arbre AVL

Indice du tableau · Facteur d'équilibre

60[0]+145[1]+185[2]+167[5]018[3]-153[4]028[8]0

Forme en tableau

Les enfants de l'indice i sont en 2i+1 et 2i+2.

  • Sans rapport
  • Déjà parcouru
  • En comparaison
  • Trouvé
  • Nouveau
  • À supprimer
  • Successeur
  • Déséquilibré
  • Pivot

Aucune étape

Code

#include <iostream>
#include <algorithm>
using namespace std;
class Node { // Un nœud contient sa valeur et des pointeurs vers ses deux enfants
private: // Attributs privés : seules les méthodes y touchent
int value;
Node* left;
Node* right;
public:
Node(int v) : value(v), left(nullptr), right(nullptr) {}
int getValue() const { return value; }
Node* getLeft() const { return left; }
Node* getRight() const { return right; }
void setValue(int v) { value = v; }
void setLeft(Node* n) { left = n; }
void setRight(Node* n) { right = n; }
};
int height(Node* n) { // Hauteur : une feuille vaut 1 et un emplacement vide (nullptr) vaut 0
if (n == nullptr) return 0;
return 1 + max(height(n->getLeft()), height(n->getRight()));
}
int balanceFactor(Node* n) { // Facteur d'équilibre : hauteur gauche moins hauteur droite
return height(n->getLeft()) - height(n->getRight());
}
Node* rotateRight(Node* y) { // Rotation simple à droite : l'enfant gauche x monte et y descend
Node* x = y->getLeft();
y->setLeft(x->getRight());
x->setRight(y);
return x;
}
Node* rotateLeft(Node* x) { // Rotation simple à gauche : l'enfant droit y monte et x descend
Node* y = x->getRight();
x->setRight(y->getLeft());
y->setLeft(x);
return y;
}
Node* rebalance(Node* n) { // Renvoie la racine du sous-arbre, équilibré
int bf = balanceFactor(n); // Le facteur d'équilibre du nœud est calculé
if (bf > 1) { // Déséquilibre à gauche. Si l'enfant gauche n'est pas déséquilibré à droite, c'est le cas LL
if (balanceFactor(n->getLeft()) < 0) // L'enfant gauche est déséquilibré à droite : cas LR, rotation à gauche d'abord
n->setLeft(rotateLeft(n->getLeft())); // Première rotation du cas LR
return rotateRight(n); // Rotation à droite : résout LL et la seconde moitié de LR
}
if (bf < -1) { // Déséquilibre à droite. Si l'enfant droit n'est pas déséquilibré à gauche, c'est le cas RR
if (balanceFactor(n->getRight()) > 0) // L'enfant droit est déséquilibré à gauche : cas RL, rotation à droite d'abord
n->setRight(rotateRight(n->getRight())); // Première rotation du cas RL
return rotateLeft(n); // Rotation à gauche : résout RR et la seconde moitié de RL
}
return n; // Le facteur est entre -1 et 1 : aucune rotation nécessaire
}
Node* insert(Node* root, int v) { // Insère v dans l'arbre AVL et renvoie la racine
if (root == nullptr) // Emplacement vide : le nouveau nœud va ici
return new Node(v); // Crée le nouveau nœud
if (v < root->getValue()) // Les valeurs plus petites vont à gauche et les plus grandes à droite
root->setLeft(insert(root->getLeft(), v)); // Descend dans le sous-arbre gauche
else
root->setRight(insert(root->getRight(), v)); // Descend dans le sous-arbre droit
return rebalance(root); // Au retour de chaque appel, l'équilibre du nœud est vérifié
}
int main() {
Node* root = buildTree(); // L'arbre affiché, déjà construit
root = insert(root, v); // Premier appel, depuis main
return 0; // Fin de l'opération
}

Cet outil part d'un arbre AVL aléatoire, un arbre binaire de recherche qui reste équilibré, et vous permet de le modifier à la main : saisissez une valeur de 1 à 99 et appuyez sur Insérer, Chercher ou Supprimer. Chaque nœud affiche son facteur d'équilibre, la différence de hauteur entre ses sous-arbres, et son indice dans le tableau. Quand un nœud atteint le facteur 2 ou -2, l'animation le marque et applique la bonne rotation : LL, RR, LR ou RL. En dessous, le même arbre apparaît sous forme de tableau et le code C++ surligne la ligne exécutée. Tout est simulé dans votre navigateur.

Comment l'utiliser

  1. Ajustez la taille de l'arbre avec le curseur ou appuyez sur Générer un nouvel arbre pour changer le point de départ.
  2. Saisissez une valeur de 1 à 99 et appuyez sur Insérer, Chercher ou Supprimer ; l'animation démarre d'elle-même.
  3. Observez le facteur d'équilibre sous chaque nœud et la rotation appliquée quand il atteint 2 ou -2.
  4. Avancez ou reculez, et comparez l'arbre à sa forme tableau et à la ligne C++ surlignée.

Questions fréquentes

Qu'est-ce qu'un arbre AVL et que garantit-il ?
C'est un arbre binaire de recherche qui se rééquilibre lui-même : à chaque nœud, la différence entre la hauteur du sous-arbre gauche et celle du droit vaut au plus 1. Cette différence s'appelle le facteur d'équilibre et vaut -1, 0 ou 1 dans un AVL valide. Grâce à cela, la hauteur croît de façon logarithmique avec le nombre de nœuds.
Quels sont les quatre cas de rotation et quand utiliser chacun ?
Si un nœud se retrouve avec le facteur 2 et que son enfant gauche penche à gauche, c'est le cas LL et une simple rotation à droite suffit. Si l'enfant penche à droite, c'est LR : l'enfant subit une rotation à gauche puis le nœud une rotation à droite. Avec le facteur -2, c'est symétrique : RR se résout par une simple rotation à gauche, et RL par une rotation à droite de l'enfant suivie d'une rotation à gauche.
Combien coûtent l'insertion, la recherche et la suppression par rapport à un ABR ?
Dans un AVL, les trois opérations prennent un temps logarithmique dans le pire cas, car la hauteur n'explose jamais. Dans un ABR simple, le coût dépend de la hauteur, qui peut devenir linéaire si les valeurs sont insérées dans l'ordre et que l'arbre dégénère en liste. En contrepartie, l'AVL effectue quelques rotations lors des insertions et suppressions.
Comment un AVL est-il stocké dans un tableau et que signifie l'indice au-dessus de chaque nœud ?
En disposition de tas : la racine va à l'indice 0 et les enfants de l'indice i en 2i+1 et 2i+2. Le nombre entre crochets au-dessus de chaque nœud est cette position, et il correspond à la case du tableau où sa valeur apparaît. Si des enfants manquent, les positions intermédiaires restent vides.

Outils associés