Les arbres rouges et noirs et les tas

Même si les arbres AVL et les B-arbres possèdent des propriétés intéressantes, ils n’en demeurent pas moins que des désavantages subsistent pour quelques applications. Par exemple, les arbres AVL peuvent nécessiter plusieurs rotations après une suppression; les B-arbres quant à eux peuvent nécessiter plusieurs opérations de regroupements ou d’éclatement après une opération insertion ou de suppression. La structure de données d’arbre rouge et noir, discutée dans ce chapitre, ne possède pas ce désavantage car ne nécessitant qu’un temps de O(1) après une mise à jour pour conserver sa propriété d’arbre équilibré.

Un arbre rouge et noir est un arbre binaire de recherche où chaque nœud est de couleur rouge ou noire de telle sorte que 1. les feuilles (null) sont noires, 2. les enfants d’un nœud rouge sont noirs, 3. le nombre de nœuds noirs le long d’une branche de la racine à une feuille est indépendant  de la branche. Autrement dit, pour tout noeud de l’arbre, les chemins de ce nœud vers les feuilles (nœud sentinel) qui en dépendent ont le même nombre de noeuds noirs.  Par commodité, on remplace les pointeurs null vers des sous-arbres vides par des feuilles sans clés. On les appelle nœuds externes. Les nœuds internes sont ceux qui ne sont pas externes.

La première condition est simplement technique et sans grande importance. La seconde condition stipule que les nœuds rouges ne sont pas trop nombreux. La dernière condition est une condition d’équilibre. Elle signifie que si on oublie les nœuds rouges d’un arbre on obtient un arbre binaire parfaitement équilibré. Dans un arbre rouge et noir, on peut toujours supposer que la racine est noire. Si elle est rouge, on change sa couleur en noire et toutes les propriétés restent vérifiées.  Exercice: Montrer que l’on ne peut pas avoir deux nœuds rouges successifs le long d’un chemin d’un arbre rouge et noir (ARN). En contrôlant cette information de couleur dans chaque nœud, on garantit qu’aucun chemin ne peut être deux fois plus long que n’importe quel autre chemin, de sorte que l’arbre reste équilibré. Même si l’équilibrage n’est pas parfait, on montre que toutes les opérations de recherche, d’insertion et de suppression sont en O(logn).

Les arbres rouges et noirs sont relativement bien équilibrés. La hauteur d’un arbre rouge et noir est de l’ordre de grandeur de log(n) où n est le nombre d’éléments dans l’arbre. En effet, la hauteur h d’un arbre rouge et noir ayant n éléments vérifie l’inégalité Soit h la hauteur d’un arbre rouge-noir, la moitié au moins des nœuds vers une feuille doivent être noirs. Autrement dit, la hauteur noire d’un arbre rouge-noir est au moins h/2. Nous pouvons donc écrire :  Les rotations sont des modifications locales d’un arbre binaire. Elles consistent à échanger un nœud avec l’un de ses fils. Dans la rotation droite, un nœud devient le fils droit du nœud qui était son fils gauche. Dans la rotation gauche, un nœud devient le fils gauche du nœud qui était son fils droit. Les rotations gauche et droite sont inverses l’une de l’autre. Elle sont illustrées à la figure ci-dessous. Dans les figures, les lettres majuscules comme A, B et C désignent des sous-arbres.

L’insertion d’une valeur dans un arbre rouge et noir commence par l’insertion usuelle d’une valeur dans un arbre binaire de recherche. Le nouveau nœud devient rouge de telle sorte que la propriété (3) reste vérifiée. Par contre, la propriété (2) n’est plus nécessairement vérifiée. Si le père du nouveau nœud est également rouge, la propriété (2) est violée. Afin de rétablir la propriété (2), l’algorithme effectue des modifications dans l’arbre à l’aide de rotations. Ces modifications ont pour but de rééquilibrer l’arbre.  Cas 0 : le nœud père p est la racine de l’arbre Le nœud père devient alors noir. La propriété (2) est maintenant vérifiée et la propriété (3) le reste. C’est le seul cas où la hauteur noire de l’arbre augmente.