Discussion :

[bakero]

salut!
je voudrais implementer un graphe en C avec des listes chainées pour representer les noeuds et un arbre red/black pour les arcs(chaque arc contient deux noeuds). Mais je bloque au niveau de la suppression d'un noeud qui devrait engendré egualement la supression des arcs dans l'arbre. J'ai deja essaié avec une visite ricorsive en eliminant a chaque fois l'arc qui contient le noeud, mais la procedure d'elimination dans un red/black comporte les operations d'equilibrages qui permettent a certains arcs de pas se faire controller.
Quelqu'un a t'il une autre solution please!

[Franck Dernoncourt]

http://en.wikipedia.org/wiki/Red-black_tree#Removal ?

[bakero]

http://en.wikipedia.org/wiki/Red-black_tree#Removal ?

Merci frank, mais ce sont là les classiques operations de suppression, j'aimerais supprimer un noeud della liste et supprimer egalement les arcs qui y sont connectés. Mes arcs sont representés par un arbre red/black.

[Franck Dernoncourt]

j'aimerais supprimer un noeud della liste et supprimer egalement les arcs qui y sont connectés

Lorsque tu supprimes un noeud, les arcs qui y sont connectés sont également supprimés, non ?

[bakero]

Lorsque tu supprimes un noeud, les arcs qui y sont connectés sont également supprimés, non ?

Non! vu que un arc est composé de deux noeuds, je fais une recherche inorder dans l'arbre R/B des arcs je trouve l'arc qui contient le noeud et je le supprime. Mais le réequilibrage de l'arbre fait en sorte que certains noeud de l'arbre echappe au controlle.Je sais pas si je me fais comprendre.

[Franck Dernoncourt]

Je ne comprends pas :

le réequilibrage de l'arbre fait en sorte que certains noeud de l'arbre echappe au controlle

Cela fait quelques années que je n'ai pas regarder l'algo de suppression d'un noeud dans un red-black tree, mais j'ai l'impression que http://en.wikipedia.org/wiki/Red-black_tree#Removal donne bien tous les cas.