Un arbre rouge-noir est un arbre binaire de recherche qui inclut un bit de stockage supplémentaire par nœud, indiquant sa couleur, qui peut être ROUGE ou NOIR. En contrôlant la coloration des nœuds le long de n'importe quel chemin de la racine à une feuille, les arbres rouges-noirs garantissent que la longueur de ces chemins ne dépasse pas deux fois celle des autres chemins, assurant ainsi une approximation de l'équilibre de l'arbre.
Chaque nœud de l'arbre contient plusieurs champs, notamment la couleur, la clé, les nœuds enfants gauche et droit, et un pointeur p. Si un enfant ou le parent d'un nœud n'existe pas, le champ pointeur correspondant du nœud contient la valeur NIL. Les NIL sont considérés comme des pointeurs vers des nœuds externes (feuilles) de l'arbre binaire de recherche, tandis que les nœuds internes de l'arbre, avec des clés, sont considérés comme des nœuds normaux.
Pour qu'un arbre binaire de recherche soit classé comme un arbre rouge-noir, il doit respecter les propriétés suivantes :
Chaque nœud est de couleur soit ROUGE, soit NOIR.
La racine de l'arbre est NOIRE.
Chaque feuille (NIL) est NOIRE.
Si un nœud est de couleur ROUGE, alors ses deux enfants sont de couleur NOIRE.
Pour chaque nœud, tous les chemins reliant ce nœud à des feuilles contiennent le même nombre de nœuds NOIRS.
Ces propriétés garantissent que la hauteur noire de l'arbre est équilibrée, ce qui maintient la performance de l'arbre en O(log n), où "n" est le nombre de nœuds dans l'arbre. Les arbres rouges-noirs sont largement utilisés en informatique pour garantir des performances constantes lors de la gestion d'ensembles de données ordonnées.