Arbre équilibré

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
Page d'aide sur l'homonymie Pour les articles homonymes, voir Arbre (homonymie).
Exemple d'arbre non équilibré
Exemple d'arbre équilibré

En informatique, un arbre équilibré, aussi appelé arbre à critère d'équilibre, est un arbre qui possède un critère d'équilibre par rapport, par exemple, au nombre de nœuds de ses fils et dont les arbres fils sont eux-mêmes équilibrés.

Le but est d'éviter de construire des arbres dégénérés (arbres peignes), par exemple lors de constructions automatisées d'arbres par un programme. Cela peut être très avantageux lorsqu'on réutilise l'arbre ainsi construit. En effet, utiliser un arbre équilibré permet d'avoir une 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.

Arbres binaires de recherche bien équilibrés[modifier | modifier le code]

Les arbres binaires de recherche présentent des cas de dégénérescence les rendant trop lents dans beaucoup de cas. Une amélioration consiste à ajouter à leurs spécifications un critère d'équilibre imposant des restrictions sur le sous-arbre droit (SAD) et gauche (SAG).

Arbre binaire à critère d'équilibre total[modifier | modifier le code]

Avec ce type d'arbre, l'arbre doit être complet c'est-à-dire que, si sa profondeur est n, le niveau n-1 est entièrement rempli. Cette approche est très rarement utile, une insertion pouvant demander la réorganisation de l'arbre entier. Insertion et suppression en O(N), recherche en O(log2 N).

Arbre binaire à critère d'équilibre partiel[modifier | modifier le code]

Dans un arbre AVL, la hauteur du SAG et celle du SAD diffèrent au plus de un. Le nombre de réorganisations maximum est en O(log N), c'est-à-dire la hauteur de l'arbre. L'insertion, la recherche et la suppression sont en O(log N).

Arbre rouge-noir[modifier | modifier le code]

Arbre SBB ou arbre rouge-noir : un arbre équilibré où la profondeur maximum de l'arbre en 2 × log2 (N + 1).

Voir aussi[modifier | modifier le code]

  • Il existe une structure de donnée "hybride" qui ressemble à un arbre et dont les feuilles forment une liste chaînée : la skip-list. Elle possède aussi un critère d'équilibre ; mais celui-ci est probabiliste, et non déterministe.