Arbre rouge et noir

Arbre bicolore

Un arbre bicolore ou arbre rouge et noir est un type particulier d'arbre binaire de recherche, qui est une structure de données utilisée en informatique théorique. Les arbres bicolores ont été inventés en 1972 par Rudolf Bayer qui les nomma "symetric binary B-trees". Leur principal intérêt réside dans la complexité logarithmique des opérations suivantes : l'insertion, la recherche et la suppression. Ils sont cependant assez complexes à mettre en œuvre, car les opérations d'insertion et de suppression font appel à de nombreuses études de cas. Enfin, ils sont isomorphes aux arbres 2-3-4.

Sommaire

Utilisation et avantages

Les arbres bicolores, ainsi que les arbres AVL, offrent la meilleure garantie sur le temps d'insertion, de suppression et de recherche dans les cas défavorables. Ceci leur permet non seulement d'être alors utilisables dans des applications en temps réel, mais aussi de servir comme fondement d'autres structures de données à temps d'exécution garanti dans les cas défavorables, par exemple en géométrie algorithmique.

Propriétés

Exemple d'arbre bicolore

Un arbre bicolore est un arbre binaire de recherche dans lequel chaque nœud a un attribut supplémentaire : sa couleur, qui est soit rouge soit noire. En plus des restrictions imposées aux arbres binaires de recherche, on ajoute les règles suivantes :

  1. Un nœud est soit rouge soit noir.
  2. La racine est noire.
  3. Toutes les feuilles sont noires (ou nil).
  4. Si un nœud est rouge, ses deux descendants sont noirs.
  5. Le chemin de chaque feuille à la racine contient le même nombre de nœuds noirs.


Ces contraintes impliquent une propriété importante des arbres bicolores : le chemin le plus long possible d'une racine à une feuille ne peut être deux fois plus long que le plus petit possible. On a ainsi un arbre presque équilibré. Comme les opérations d'insertion, de recherche et de suppression requièrent dans le pire des cas un temps proportionnel à la taille de l'arbre, les arbres bicolores restent efficaces, contrairement aux arbres binaires de recherche ordinaires.

Pour comprendre comment ces contraintes garantissent la propriété ci-dessus, il suffit de s'apercevoir qu'aucun chemin ne peut avoir deux nœuds rouges consécutifs à cause de la propriété 4. Le plus petit chemin théorique de la racine à une feuille ne contient alors que des nœuds noirs tandis que le plus grand alterne entre les nœuds rouges et noirs. Et comme d'après la propriété 5, chacun de ces chemins contiennent le même nombre de nœuds noirs, le plus grand chemin ne peut être deux fois plus grand que le plus petit.

Une source de confusion usuelle avec ces propriétés est qu'elles sont écrites dans l'hypothèse où chaque feuille de l'arbre sont des « feuilles nil », qui ne contiennent pas de données et qui servent à montrer que l'arbre s'arrête ici. Ces nœuds sont souvent omis dans les dessins, qui semblent alors être en contradiction avec la propriété 3 alors qu'ils ne le sont pas.

Opérations

La recherche sur un arbre bicolore s'effectue exactement comme dans les arbres binaires de recherche. Cependant, après une insertion ou une suppression, les propriétés de l'arbre bicolore peuvent être violées. La restauration de ces propriétés requiert un petit nombre (O(ln n)) de modifications des couleurs (qui sont très rapides en pratique) et pas plus de trois rotations (deux pour l'insertion). Ceci permet d'avoir une insertion et une suppression en O(ln n) mais complique grandement les opérations à cause du grand nombre de cas à étudier.

Insertion

Première étape : descendre à partir de la racine à la recherche de la feuille où il faut insérer l'élément.

Deuxième étape : sur ce chemin, lorsqu'un nœud A a ses deux fils rouges, on inverse les couleurs de A et de ses fils. De plus, si le père de A est lui-même rouge, il faut faire une rotation sur le grand-père de A avant de poursuivre la descente.

Troisième étape : l'ajout proprement dit se fait toujours sur 1 nœud rouge car le nouvel élément est ajouté en tant que jumeau. Dans le cas où le père du nœud ajouté est rouge mais n'a pas de père rouge, il faut effectuer une rotation comme à la deuxième étape.

Suppression

La suppression commence par une recherche du noeud à supprimer Nsup Supprimer Nsup à partir d’un arbre ordonné Rééquilibrage de l’arbre Si le noeud supprimé est un noeud rouge, les quatre conditions sont toujours satisfaites Si le noeud supprimé est noir, on viole la condition 4 – Réorganisation de l’arbre en remontant vers la racine

Voir aussi

Références

Ce document provient de « Arbre bicolore ».

Wikimedia Foundation. 2010.

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

Regardez d'autres dictionnaires:

  • Arbre rouge-noir — Arbre bicolore Un arbre bicolore ou arbre rouge et noir est un type particulier d arbre binaire de recherche, qui est une structure de données utilisée en informatique théorique. Les arbres bicolores ont été inventés en 1972 par Rudolf Bayer qui… …   Wikipédia en Français

  • Arbre Bicolore — Un arbre bicolore ou arbre rouge et noir est un type particulier d arbre binaire de recherche, qui est une structure de données utilisée en informatique théorique. Les arbres bicolores ont été inventés en 1972 par Rudolf Bayer qui les nomma… …   Wikipédia en Français

  • Arbre bicolore — Un arbre bicolore ou arbre rouge et noir est un type particulier d arbre binaire de recherche, qui est une structure de données utilisée en informatique théorique. Les arbres bicolores ont été inventés en 1972 par Rudolf Bayer qui les nomma… …   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

  • noir — noir, noire [ nwar ] adj. et n. • XIIe ; neir 1080; lat. niger I ♦ Adj. A ♦ (Concret) 1 ♦ Se dit de l aspect d un corps dont la surface ne réfléchit aucune radiation visible, dont la couleur est aussi sombre que possible (⇒ noirceur; noircir;… …   Encyclopédie Universelle

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

  • 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 Binaire — En informatique, un arbre binaire est une structure de données qui peut se représenter sous la forme d une hiérarchie dont chaque élément est appelé nœud, le nœud initial étant appelé racine. Dans un arbre binaire, chaque élément possède au plus… …   Wikipédia en Français

Share the article and excerpts

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