next up previous contents index
Next: Algorithmes gloutons Up: Arbres binaires étiquetés Previous: Arbres binaires étiquetés

Arbres bicolores

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\oeuds est comprise entre $\log_2 n$ et n+1 ; les opérations ne sont donc pas toujours efficaces. De plus, l'insertion de nouveaux n\oeuds dans un arbre peut dégrader les performances des opérations ultérieures. Par exemple, si l'on insère successivement n n\oeuds 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 n\oeuds. 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 n\oeuds sont colorés en rouge ou en noir et vérifiant les propriétés suivantes :

Les arbres bicolores forment la base des implémentations TreeSet TreeMap des interfaces Set et Map du paquet java.util de Java 2.


next up previous contents index
Next: Algorithmes gloutons Up: Arbres binaires étiquetés Previous: Arbres binaires étiquetés
R. Lalement
2000-10-23