Arbre équilibré

Arbre équilibré
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.

Sommaire

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

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

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

Arbre rouge-noir

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

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.

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Arbre équilibré de Wikipédia en français (auteurs)

Игры ⚽ Нужно решить контрольную?

Regardez d'autres dictionnaires:

  • Arbre equilibre — 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… …   Wikipédia en Français

  • 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… …   Wikipédia en Français

  • Arbre balancé — Arbre B Schéma définissant un arbre B. Un arbre B (appelé aussi B arbre par analogie au terme anglais « B tree ») est un arbre équilibré qui est principalement mis en œuvre dans les mécanismes de gestion de bases de données et de… …   Wikipédia en Français

  • Arbre Binaire De Recherche — Exemple représentant un arbre binaire de recherche En informatique, un arbre binaire de recherche (ABR) est un arbre binaire dans lequel chaque nœud possède une clé, telle que chaque nœud du sous arbre gauche ait une clé inférieure ou égale à… …   Wikipédia en Français

  • Arbre B — Schéma définissant un arbre B. En informatique un arbre B (appelé aussi B arbre par analogie au terme anglais « B tree ») est une structure de données en arbre équilibré. Les arbres B sont principalement mis en œuvre dans les mécanismes …   Wikipédia en Français

  • Arbre kd — Un arbre kd (ou kd tree, pour k dimensional tree) est une structure de données de partition de l espace permettant de stocker des points, et de faire des recherches (recherche par plage, plus proche voisin, etc.) plus rapidement qu en parcourant… …   Wikipédia en Français

  • Arbre (homonymie) — Cette page d’homonymie répertorie les différents sujets et articles partageant un même nom. Sur les autres projets Wikimedia : « arbre », sur le Wiktionnaire (dictionnaire universel) Au sens premier, le mot arbre, désigne en… …   Wikipédia en Français

  • Arbre binaire de recherche — Pour les articles homonymes, voir Arbre (homonymie). Exemple représentant un arbre binaire de recherche En informatique, un arbre binaire de recherche (ABR) est un …   Wikipédia en Français

  • Arbre Andelson-Velskii et Landis — Arbre AVL Pour les articles homonymes, voir AVL. Un exemple d arbre non AVL. En informatique, les arbres AVL ont été his …   Wikipédia en Français

  • Arbre avl — Pour les articles homonymes, voir AVL. Un exemple d arbre non AVL. En informatique, les arbres AVL ont été his …   Wikipédia en Français

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”