application arbre binaire avl, rouge-noir avec C# + coude source

Les arbres rouges et noirs sont une variante des arbres binaires de recherche. Leur intérêt principal est qu'ils sont relativement équilibrés. On considère ici des arbres binaires de recherche où les valeurs sont portées par les nœuds internes. Les feuilles ne sont pas prises en compte dans la hauteur de l'arbre.

Définition

Un arbre rouge et noir est un arbre binaire de recherche ou chaque nœud est de couleur rouge ou noire de telle sorte que

1. les feuilles sont noires,
2. les fils 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.

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 s'il 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.

lien de téléchargement :  parc ici

mot de passe winrar : progduzero.com