Un ABR simple peut dégénérer en liste chaînée (opérations O(n)) si les clés arrivent dans un ordre trié. Les ABR auto-équilibrés — comme les arbres AVL et les arbres rouge-noir — effectuent automatiquement des rotations de nœuds après les insertions/suppressions pour maintenir une hauteur ~, garantissant des opérations .
log nUnbalanced (insert 1,2,3,4): Balanced after rotations:
1 2
\ / \
2 1 3
\ \
3 4
height ~ n (BAD) height ~ log n (GOOD)
| Arbre AVL | Arbre rouge-noir | |
|---|---|---|
| Rigueur d'équilibre | stricte (équilibrée en hauteur) | plus souple |
| Recherches | plus rapides (plus courts) | légèrement plus lentes |
| Insertion/suppression | plus de rotations | moins de rotations |
| Optimal pour | charges de lecture lourdes | charges d'écriture lourdes |
| Opération | Temps |
|---|---|
| search | O(log n) |
| insert | O(log n) |
| delete | O(log n) |
Les deux maintiennent l'équilibre via des rotations — des restructurations locales O(1) qui préservent l'ordre ABR tout en réduisant la hauteur.
Les arbres équilibrés soutiennent les cartes et ensembles ordonnés dans les bibliothèques standard (par exemple, Java TreeMap, C++ std::map utilisent des arbres rouge-noir), offrant une itération triée plus des opérations logarithmiques garanties.
Ils sont la réponse quand vous avez besoin de l'ordre d'un ABR et d'une garantie de performance stricte contre les entrées adversariales.