Un arbre binaire de recherche
est un arbre binaire étiqueté, dont les étiquettes sont comparables, tel
que l'étiquette de la racine est plus grande que les étiquettes du
sous-arbre gauche et plus petite que les étiquettes du sous-arbre droit.
Cette structure permet de réaliser des opérations d'insertion, de
recherche et de suppression avec en coût en O(h), où h est la
hauteur de l'arbre (la longueur maximale d'un chemin de la racine à une
feuille). Or, la hauteur d'un arbre binaire comportant n n
uds
est comprise entre 
et n+1 ; les opérations ne sont donc pas
toujours efficaces. De plus, l'insertion de nouveaux nuds dans un
arbre peut dégrader les performances des opérations ultérieures. Par
exemple, si l'on insère successivement n nuds d'étiquettes
croissantes, l'arbre obtenu sera linéaire de hauteur n+1, ce qui est
le pire des cas. Il est possible de réarranger l'arbre après chaque
insertion ou suppression, de manière à conserver une configuration
favorable. Si l'on adopte une définition stricte de ce qu'est un arbre
équilibré, les réarrangements peuvent être très coûteux. Une
définition plus tolérante des déséquilibres permet de réaliser ces
réarrangements moins souvent, donc à un moindre coût global : on fait en
sorte qu'aucun chemin de la racine vers une feuille ne soit plus de deux
fois plus long qu'un autre. Cette contrainte est respectée grâce à un
coloriage des nuds. C'est l'idée des arbres bicolores (ou rouges et
noirs), qui sont des sont des arbres binaires de recherche
approximativement équilibrés introduits par Bayer en 1972.
Un arbre bicolore est une arbre binaire de
recherche dont les nuds sont colorés en rouge ou en noir et
vérifiant les propriétés suivantes :
ud est rouge, ses deux enfants sont noirs ;
ud, tous les chemins menant de ce nud à
une feuille ont le même nombre de nuds noirs.
Les arbres bicolores forment la base des implémentations TreeSet TreeMap des interfaces Set et Map du paquet java.util de Java 2.