Souci de programmation :arbre rouge et noir
chaf
-
amina_info27 Messages postés 1 Statut Membre -
amina_info27 Messages postés 1 Statut Membre -
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
A voir également:
- Souci de programmation :arbre rouge et noir
- Application de programmation - Guide
- Télécharger le programme de pmu - Télécharger - Médias et Actualité
- Fermer un programme de force - Guide
- Programmation envoi sms - Guide
- Langage de programmation visual basic - Télécharger - Langages
5 réponses
Salut.
En quoi consiste ton arbre rouge et noir?
Personnellement je connai les arbres binaires ou Naire.
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
-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 ?
@++
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 ?
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).
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).
chaf