Arbre équilibré

Un article de Wikipédia, l'encyclopédie libre.

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.

Sommaire 1 Arbres binaires de recherche bien équilibrés 1.1 Arbre binaire à critère d'équilibre total 1.2 Arbre binaire à critère d'équilibre partiel 1.3 Arbre rouge-noir 2 Voir aussi

[modifier] Arbres binaires de recherche bien équilibrés

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).

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

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(log₂ N).

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

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).

[modifier] Arbre rouge-noir

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

[modifier] Voir aussi

• 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.