Arbre équilibré
De Wikipedia, l'encyclopédie encyclopedia
Pour les articles homonymes, voir Arbre (homonymie).
En informatique, un arbre équilibré, aussi appelé arbre à critère d'équilibre, est un arbre qui maintient une profondeur équilibrée entre ses branches. Cela a l'avantage que le nombre de pas pour accéder à la donnée d'une clé est en moyenne minimisé, et ce nombre est égal (+/- 1) quelle que soit la clé.
Cet article ne cite pas suffisamment ses sources ().
Si vous disposez d'ouvrages ou d'articles de référence ou si vous connaissez des sites web de qualité traitant du thème abordé ici, merci de compléter l'article en donnant les références utiles à sa vérifiabilité et en les liant à la section « Notes et références ».
En pratique : Quelles sources sont attendues ? Comment ajouter mes sources ?
Le but est d'éviter de construire des arbres dits dégénérés (arbres peignes), dans lesquels certains chemins d'accès aux données sont d'une longueur disproportionnée. Cela peut être très avantageux lorsqu'on réutilise l'arbre ainsi construit : en effet, utiliser un arbre équilibré permet d'avoir un temps de recherche de complexité logarithmique dans le pire des cas au lieu d'une complexité linéaire, comme c'est parfois le cas pour des arbres dégénérés.