Arbre AVL
Dernière mise à jour
Un arbre AVL est un arbre binaire de recherche auto-équilibré. Il fonctionne comme un ABR normal, mais après chaque insertion il vérifie le facteur d'équilibre de chaque ancêtre - la différence de hauteur entre ses sous-arbres gauche et droit - et si un nœud devient déséquilibré (une différence supérieure à 1), il effectue des rotations pour rétablir l'équilibre. Appuyez sur lecture ci-dessus pour voir les valeurs insérées et l'arbre pivoter pour retrouver sa forme.
Comme il ne laisse jamais l'arbre pencher plus que légèrement, un arbre AVL garantit une hauteur en O(log n), de sorte que la recherche, l'insertion et la suppression sont toujours en O(log n) - même pour une entrée triée qui ruinerait un ABR ordinaire. Le coût réside dans les rotations supplémentaires et la tenue des hauteurs à chaque insertion.
Complexité en temps et en espace
| Opération | Complexité | Notes |
|---|---|---|
| Recherche | O(log n) | La hauteur est toujours ~1.44 log n |
| Insertion | O(log n) | Plus O(1) rotations |
| Suppression | O(log n) | Plus O(log n) rotations |
| Espace | O(n) | Un champ de hauteur par nœud |
Les quatre cas de rotation
| Cas | Déséquilibre | Correction |
|---|---|---|
| Gauche-Gauche | Lourd sur la gauche de l'enfant gauche | Une rotation à droite |
| Droite-Droite | Lourd sur la droite de l'enfant droit | Une rotation à gauche |
| Gauche-Droite | Lourd sur la droite de l'enfant gauche | Rotation à gauche puis à droite |
| Droite-Gauche | Lourd sur la gauche de l'enfant droit | Rotation à droite puis à gauche |
Exemple résolu
Insertion de [10, 20, 30, 40, 50, 25] une valeur à la fois :
| Étape | Structure | Action |
|---|---|---|
Insérer 10 | 10 | Le premier nœud devient la racine ; équilibré |
Insérer 20 | 10(_, 20) | Va à droite de 10 ; toujours équilibré |
Insérer 30 | 20(10, 30) | Droite-Droite en 10, donc une rotation à gauche hisse 20 à la racine |
Insérer 40 | 20(10, 30(_, 40)) | Va à droite de 30 ; tous les facteurs d'équilibre restent dans ±1 |
Insérer 50 | 20(10, 40(30, 50)) | Droite-Droite en 30, donc une rotation à gauche en 30 hisse 40 |
Insérer 25 | 30(20(10, 25), 40(_, 50)) | Droite-Gauche en 20 : rotation à droite du sous-arbre de 40, puis rotation à gauche de 20 |
Quand utiliser un arbre AVL
| À utiliser quand | À éviter quand |
|---|---|
| Les recherches dépassent largement les insertions et vous voulez la hauteur la plus compacte possible | Les insertions et suppressions dominent - les rotations et le rééquilibrage supplémentaires coûtent plus qu'un arbre rouge-noir |
Vous avez besoin d'un pire cas garanti en O(log n), même pour une entrée adverse ou triée | Une simple table de hachage suffirait - vous n'avez pas besoin de parcours ordonné ni de requêtes par plage |
| Vous avez besoin d'opérations ordonnées : parcours en ordre, prédécesseur/successeur, requêtes par plage | Le jeu de données est minuscule - un ABR simple ou un tableau trié est plus simple et assez rapide |
| Les données peuvent arriver déjà triées, ce qui transformerait un ABR non équilibré en liste chaînée | Vous ne pouvez pas vous permettre la mémoire supplémentaire du champ de hauteur par nœud dans un espace très restreint |
Code de AVL Tree
Une implémentation propre et exécutable de AVL Tree en Python, JavaScript, Java, C++, C. Choisissez un langage, copiez le code ou ouvrez-le préchargé dans le Playground Coddy.
Code de AVL Tree en Python
Python
1class Node:2 def __init__(self, key):3 self.key = key4 self.left = None5 self.right = None6 self.height = 17
8
9def height(node):10 return node.height if node else 011
12
13def update(node):14 node.height = 1 + max(height(node.left), height(node.right))15
16
17def rotate_right(y):18 x = y.left19 y.left = x.right20 x.right = y21 update(y)22 update(x)23 return x24
25
26def rotate_left(x):27 y = x.right28 x.right = y.left29 y.left = x30 update(x)31 update(y)32 return y33
34
35def insert(node, key):36 if node is None:37 return Node(key)38 if key < node.key:39 node.left = insert(node.left, key)40 else:41 node.right = insert(node.right, key)42 update(node)43 balance = height(node.left) - height(node.right)44 # Four imbalance cases: LL, RR, LR, RL45 if balance > 1 and key < node.left.key:46 return rotate_right(node)47 if balance < -1 and key > node.right.key:48 return rotate_left(node)49 if balance > 1:50 node.left = rotate_left(node.left)51 return rotate_right(node)52 if balance < -1:53 node.right = rotate_right(node.right)54 return rotate_left(node)55 return node56
57
58def inorder(node):59 if node is None:60 return []61 return inorder(node.left) + [node.key] + inorder(node.right)62
63
64root = None65for key in [10, 20, 30, 40, 50, 25]:66 root = insert(root, key)67
68print("Inorder:", inorder(root))69print("Root:", root.key, "| tree height:", root.height)Code de AVL Tree en JavaScript
JavaScript
1class Node {2 constructor(key) {3 this.key = key;4 this.left = null;5 this.right = null;6 this.height = 1;7 }8}9
10const height = (n) => (n ? n.height : 0);11const update = (n) => {12 n.height = 1 + Math.max(height(n.left), height(n.right));13};14const balance = (n) => height(n.left) - height(n.right);15
16function rotateRight(y) {17 const x = y.left;18 y.left = x.right;19 x.right = y;20 update(y);21 update(x);22 return x;23}24
25function rotateLeft(x) {26 const y = x.right;27 x.right = y.left;28 y.left = x;29 update(x);30 update(y);31 return y;32}33
34function insert(node, key) {35 if (!node) return new Node(key);36 if (key < node.key) node.left = insert(node.left, key);37 else node.right = insert(node.right, key);38 update(node);39 const b = balance(node);40 // Four rebalancing cases: LL, RR, LR, RL41 if (b > 1 && key < node.left.key) return rotateRight(node);42 if (b < -1 && key > node.right.key) return rotateLeft(node);43 if (b > 1) {44 node.left = rotateLeft(node.left);45 return rotateRight(node);46 }47 if (b < -1) {48 node.right = rotateRight(node.right);49 return rotateLeft(node);50 }51 return node;52}53
54function inorder(node, out = []) {55 if (!node) return out;56 inorder(node.left, out);57 out.push(node.key);58 inorder(node.right, out);59 return out;60}61
62let root = null;63for (const key of [10, 20, 30, 40, 50, 25]) root = insert(root, key);64console.log("Root after rebalancing:", root.key);65console.log("Inorder:", inorder(root).join(" "));Code de AVL Tree en Java
Java
1public class Main {2 static class Node {3 int key, height = 1;4 Node left, right;5 Node(int key) { this.key = key; }6 }7
8 static int height(Node n) { return n == null ? 0 : n.height; }9 static int balance(Node n) { return n == null ? 0 : height(n.left) - height(n.right); }10 static void update(Node n) { n.height = 1 + Math.max(height(n.left), height(n.right)); }11
12 static Node rotateRight(Node y) {13 Node x = y.left;14 y.left = x.right;15 x.right = y;16 update(y); update(x);17 return x;18 }19
20 static Node rotateLeft(Node x) {21 Node y = x.right;22 x.right = y.left;23 y.left = x;24 update(x); update(y);25 return y;26 }27
28 static Node insert(Node node, int key) {29 if (node == null) return new Node(key);30 if (key < node.key) node.left = insert(node.left, key);31 else node.right = insert(node.right, key);32 update(node);33 int b = balance(node);34 // Four imbalance cases: LL, RR, LR, RL35 if (b > 1 && key < node.left.key) return rotateRight(node);36 if (b < -1 && key > node.right.key) return rotateLeft(node);37 if (b > 1) { node.left = rotateLeft(node.left); return rotateRight(node); }38 if (b < -1) { node.right = rotateRight(node.right); return rotateLeft(node); }39 return node;40 }41
42 static void inorder(Node n, StringBuilder sb) {43 if (n == null) return;44 inorder(n.left, sb);45 sb.append(n.key).append(" ");46 inorder(n.right, sb);47 }48
49 public static void main(String[] args) {50 Node root = null;51 int[] keys = {10, 20, 30, 40, 50, 25};52 for (int k : keys) root = insert(root, k);53 StringBuilder sb = new StringBuilder();54 inorder(root, sb);55 System.out.println("Inorder: " + sb.toString().trim());56 System.out.println("Root after rebalancing: " + root.key + " (height " + root.height + ")");57 }58}Code de AVL Tree en C++
C++
1#include <algorithm>2#include <iostream>3
4struct Node {5 int value;6 int height = 1;7 Node* left = nullptr;8 Node* right = nullptr;9 explicit Node(int v) : value(v) {}10};11
12int height(const Node* n) { return n ? n->height : 0; }13int balanceFactor(const Node* n) { return height(n->left) - height(n->right); }14void updateHeight(Node* n) {15 n->height = 1 + std::max(height(n->left), height(n->right));16}17
18Node* rotateRight(Node* y) {19 Node* x = y->left;20 y->left = x->right;21 x->right = y;22 updateHeight(y);23 updateHeight(x);24 return x;25}26
27Node* rotateLeft(Node* x) {28 Node* y = x->right;29 x->right = y->left;30 y->left = x;31 updateHeight(x);32 updateHeight(y);33 return y;34}35
36Node* insert(Node* node, int value) {37 if (node == nullptr) return new Node(value);38 if (value < node->value) node->left = insert(node->left, value);39 else node->right = insert(node->right, value);40 updateHeight(node);41 int balance = balanceFactor(node);42 // Four rebalancing cases: LL, RR, LR, RL43 if (balance > 1 && value < node->left->value) return rotateRight(node);44 if (balance < -1 && value > node->right->value) return rotateLeft(node);45 if (balance > 1) {46 node->left = rotateLeft(node->left);47 return rotateRight(node);48 }49 if (balance < -1) {50 node->right = rotateRight(node->right);51 return rotateLeft(node);52 }53 return node;54}55
56void inorder(const Node* n) {57 if (n == nullptr) return;58 inorder(n->left);59 std::cout << n->value << "(h" << n->height << ") ";60 inorder(n->right);61}62
63int main() {64 Node* root = nullptr;65 for (int value : {10, 20, 30, 40, 50, 25}) root = insert(root, value);66 std::cout << "Root after rebalancing: " << root->value << "\n";67 std::cout << "In-order: ";68 inorder(root);69 std::cout << "\n";70 return 0;71}Code de AVL Tree en C
C
1#include <stdio.h>2#include <stdlib.h>3
4typedef struct Node {5 int value, height;6 struct Node* left;7 struct Node* right;8} Node;9
10int height(const Node* n) { return n ? n->height : 0; }11int balanceFactor(const Node* n) { return height(n->left) - height(n->right); }12int maxInt(int a, int b) { return a > b ? a : b; }13
14Node* newNode(int value) {15 Node* n = calloc(1, sizeof(Node));16 n->value = value;17 n->height = 1;18 return n;19}20
21void updateHeight(Node* n) {22 n->height = 1 + maxInt(height(n->left), height(n->right));23}24
25Node* rotateRight(Node* y) {26 Node* x = y->left;27 y->left = x->right;28 x->right = y;29 updateHeight(y);30 updateHeight(x);31 return x;32}33
34Node* rotateLeft(Node* x) {35 Node* y = x->right;36 x->right = y->left;37 y->left = x;38 updateHeight(x);39 updateHeight(y);40 return y;41}42
43Node* insert(Node* node, int value) {44 if (node == NULL) return newNode(value);45 if (value < node->value) node->left = insert(node->left, value);46 else node->right = insert(node->right, value);47 updateHeight(node);48 int balance = balanceFactor(node);49 // Four rebalancing cases: LL, RR, LR, RL50 if (balance > 1 && value < node->left->value) return rotateRight(node);51 if (balance < -1 && value > node->right->value) return rotateLeft(node);52 if (balance > 1) {53 node->left = rotateLeft(node->left);54 return rotateRight(node);55 }56 if (balance < -1) {57 node->right = rotateRight(node->right);58 return rotateLeft(node);59 }60 return node;61}62
63void inorder(const Node* n) {64 if (n == NULL) return;65 inorder(n->left);66 printf("%d(h%d) ", n->value, n->height);67 inorder(n->right);68}69
70int main(void) {71 int values[] = {10, 20, 30, 40, 50, 25};72 Node* root = NULL;73 for (int i = 0; i < 6; i++) root = insert(root, values[i]);74 printf("Root after rebalancing: %d\n", root->value);75 printf("In-order: ");76 inorder(root);77 printf("\n");78 return 0;79}FAQ sur l'arbre AVL
Qu'est-ce qu'un facteur d'équilibre dans un arbre AVL ?
Le facteur d'équilibre d'un nœud est la hauteur de son sous-arbre gauche moins la hauteur de son sous-arbre droit. Un arbre AVL maintient le facteur d'équilibre de chaque nœud à -1, 0 ou +1 ; si une insertion le pousse hors de cette plage, une rotation rétablit l'équilibre.
Quelle est la différence entre un arbre AVL et un arbre rouge-noir ?
Les deux sont des ABR auto-équilibrés avec des opérations en
O(log n). Les arbres AVL sont plus strictement équilibrés, donc les recherches sont légèrement plus rapides, mais ils peuvent faire plus de rotations à l'insertion/suppression. Les arbres rouge-noir sont plus lâchement équilibrés, favorisant moins de rotations - c'est pourquoi de nombreuses bibliothèques standard les utilisent pour les maps et les ensembles.Pourquoi utiliser un arbre AVL plutôt qu'un arbre binaire de recherche ordinaire ?
Un ABR ordinaire peut se dégrader en opérations
O(n) si les valeurs arrivent triées, formant une chaîne déséquilibrée. Un arbre AVL pivote pour rester équilibré, garantissant une hauteur et des opérations en O(log n) quel que soit l'ordre d'insertion.Un arbre AVL est-il meilleur qu'un arbre rouge-noir pour un index de base de données ?
Cela dépend de la charge de travail. Les arbres AVL sont plus rigidement équilibrés, ils gagnent donc quand les lectures dominent et que vous voulez les chemins de recherche les plus courts possibles. Mais la plupart des bases de données et bibliothèques de langages choisissent des arbres rouge-noir (ou des arbres B) car ils se rééquilibrent avec moins de rotations sur des charges à forte écriture, ce qui compte davantage quand les insertions et suppressions sont fréquentes.
Combien de rotations une seule insertion AVL nécessite-t-elle ?
Au plus une rotation - simple ou double (en deux étapes) - est nécessaire pour rééquilibrer l'arbre après l'insertion d'une valeur. En effet, une insertion augmente la hauteur d'un sous-arbre d'au plus un, donc une seule correction au niveau de l'ancêtre déséquilibré le plus bas suffit. La suppression est différente : elle peut nécessiter jusqu'à
O(log n) rotations à mesure que le rééquilibrage se propage vers la racine.Dois-je mettre à jour les hauteurs des nœuds après chaque rotation ?
Oui - une erreur courante consiste à faire pivoter correctement les pointeurs mais à oublier de recalculer la hauteur des deux nœuds concernés. Après chaque rotation, vous devez d'abord mettre à jour la hauteur du nœud rétrogradé puis celle du nœud promu, car la hauteur du nœud promu dépend de ses nouveaux enfants. Omettre cela laisse des facteurs d'équilibre obsolètes qui faussent les décisions de rééquilibrage futures.
Ressources associées
Plus de visualisations
