Souci de programmation :arbre rouge et noir
chaf
-
amina_info27 -
amina_info27 -
j aurai besoin d une methode pour supprimer un noeud (feuille,noeud interne ou racine) d un arbre rouge et noir et le reequilibrer en sachant que j ai les methodes qui:
-renvoient et modifie l objet racine, le fils droit et le fils gauche
-renvoient l arbre vide et le pere du noeud
-donnent un nouveau pere
-permettent des rotations( gauche, droite,gauchedroite)
en vous remerciant par avance
-renvoient et modifie l objet racine, le fils droit et le fils gauche
-renvoient l arbre vide et le pere du noeud
-donnent un nouveau pere
-permettent des rotations( gauche, droite,gauchedroite)
en vous remerciant par avance
5 réponses
-
salut
en quel langage ???
Chouba
Casque Bleu forumique -
Salut.
En quoi consiste ton arbre rouge et noir?
Personnellement je connai les arbres binaires ou Naire.-
un arbre rouge et noir est un arbre dont:
-tout noeud possede zero ou deux fils
-la racine est noire
-les feuilles sont noires
-les fils d un noeud rouge sont noirs
-tous les chemins terminaux issus d un meme noeud ont le meme nombre de noeuds noirs
c est aussi connu sous le nom arbre bicolore
chafi
-
-
Un Red/Black Tree (je préfère la version anglaise du nom ;-) C'est un arbre qui est toujours équilibré => C'est un peu plus long en traitement en insertion ou en suppression pour le rééquilibrage, mais en recherche c'est génial : c'est toujours de la complexité en log(n) au pire cas.
@++
Vous hésitez entre Linux et Windows?
Vous voulez dépenser du temps ou de l'argent ? -
dsl, c'est de l'algo récursive pure... Je ne crois pas qu'un livre soit une meilleure aide que le web et ton cerveau ;-)
Il va falloir réfléchir intensément ;p
Un ptit conseil qui s'est avéré très utile pour moi par le passé : en récursif, ne cherche pas à réfléchir à un ordre élevé...
Je vais essayer de m'expliquer : réflechis et trouve un algo qui fonctionne très bien récursivement avec un noeud et ses deux fils, et normalement ça devrait marcher avec plus de noeuds... Je suis toujours parti de ce principe et ça a souvent marché sans que j'en sois sur (exemple : en partiel sur feuille où tu n'as pas de moyen de vérifier quoi que ce soit en pratique ;-)
=> Tu as le luxe de pouvoir tester ton algo, donc applique le principe ci-dessus et reviens nous voir si tu n'y arrives pas.
Rappelle aussi d'une chose importante : plus ta question sera courte et précise (c'est à dire que tu auras cherché avant de demander quelque chose), plus tu auras de réponses et plus tu comprendras les solutions proposées...
Voilà
@++
PS : tape Red black tree sur google, tu vas trouver pleins d'exemples et de codes .... (en espérant que tu parles anglais, mais tu devrais aussi trouver en français ;)
Vous hésitez entre Linux et Windows?
Vous voulez dépenser du temps ou de l'argent ? -
Vous n’avez pas trouvé la réponse que vous recherchez ?
Posez votre question -
bonjour,voila une methode de supression d'un noeud dans un arbre bicolore
La suppression dans un arbre bicolore etant delicate, on envisage de faire de la suppression paresseuse : plutot
que de supprimer "physiquement" chaque sommet au fur et a mesure, on se contente de le marquer comme etant
supprime, et lorsque la moitie des sommets d'un arbre sont marques, on reconstruit totalement l'arbre (avec les
"bons" sommets, i.e. les sommets non supprimes).
