Page d'accueil	encyclopedie-enligne.com en page d'accueil
Liste Articles: [0-A] [A-C] [C-F] [F-J] [J-M] [M-P] [P-S] [S-Z] | Liste Catégories | Une page au hasard | Pages liées

Arbre balancé

Les arbres balancés sont souvent appelés arbres à critère d'équilibre.

Les arbres binaires de recherche présentent un cas de dégénérescence les rendant peu utiles 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

Dans ce type d'arbre le nombre de nœuds dans le SAD et le SAG doivent différer au plus de un. 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)

Arbre binaire a critère d'équilibre partiel

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

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