Arbre bicolore

Un arbre bicolore, ou arbre rouge-noir (en anglais red–black tree) ou arbre rouge et noir est un type particulier d'arbre binaire de recherche équilibré, 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 nomme symmetric binary B-trees (littéralement « arbres B binaires symétriques »). Chaque nœud de l'arbre possède en plus de ses données propres un attribut binaire qui est souvent interprété comme sa « couleur » (rouge ou noir). Cet attribut permet de garantir l'équilibre de l'arbre : lors de l'insertion ou de la suppression d'éléments, certaines propriétés sur les relations entre les nœuds et leurs couleurs doivent être maintenues, ce qui empêche l'arbre de devenir trop déséquilibré, y compris dans le pire des cas. Durant une insertion ou une suppression, les nœuds sont parfois réarrangés ou changent leur couleur afin que ces propriétés soient conservées. Grâce à ces réarrangements ou coloriages des nœuds, la complexité en temps des opérations d'insertion, de recherche et de suppression est logarithmique en rapport au nombre d'éléments de la structure. De plus, par rapport à un arbre binaire basique, cette structure est économe en mémoire puisque chaque nœud ne requiert qu'un bit supplémentaire pour stocker la couleur.