Discussion :

[javast]

Bonsoir,

Je suis entrain de lire un cours sur les arbres rouge et noirs, et je bloque sur l'algorithme de l'insertion d'un nouveau noeud surtout au niveau du changement des couleurs
si quelqu'un peut m'expliquer d'une manière claire et facile l'insertion dans un arbre avec un petit exemple ça serait gentil

Merci

[Franck Dernoncourt]

http://en.wikipedia.org/wiki/Red%E2%...tree#Insertion ?

[javast]

Bonjour,
Merci Franck Dernoncourt pour ta réponse, donc au fait j'ai essayé d'appliquer le code sur un arbre que le prof nous a donnée en cours mais je trouve pas la même solution
voilà on veut créer un arbre avec ces élèments
10 85 15 70 20 60 30 50 65 80 90 40 5 55

donc en appliquant l'alogo, je commence par l'insertion de 10 ce dernier il sera noir(car c'est la racine de l'arbre), après j'insère 85 il va se mettre à droite de 10 et sa couleur sera rouge , donc jusqu'à là tout vas bien, après j'insère 15 qui va se mettre à gauche de 85 et il sera en rouge donc d'après ce que j'ai compris là il y a une propriété violé (UN NOEUD ROUGE DOIT TOUJOURS AVOIR DES FILS NOIR), dans ce cas là on fait une rotation left au niveau du parent (85)
résultat 85 prend la place de 10(racine) donc on va la colorier en noir, 10 devient le fils gauche de 85 et 15 devient le fils droit de 85, donc résultat final est===> 85 est la nouvelle racine(noir) et ses deux fils deviennent rouge.
eh bah non quand je regarde mon cours c'est le 15 qui devient la racine et les trois sont noirs. voilà ce que je comprends pas, POURQUOI?

Merci