Posez votre question Signaler

Suppression dans un arbre rouge et noir

Epsilon - Dernière réponse le 8 juil. 2010 à 05:21
Bonjour,
j'ai besoin d'un code de suppression d'un élément dans un arbre bicolore (rouge et noir): c'est un arbre binaire de recherche qui satisfait les propriétés suivantes:
1- chaque noeud est soit rouge soit noir.
2-chaque feuille est noire.
3-si un noeud est rouge alors ses deux fils sont noirs.
4- Tous les chemins descendants reliant un noeud donné à une feuille contiennent le meme nombre de noeuds noirs
Lire la suite 
Réponse
+0
moins plus
j aurai besoin d une methode pour supprimer une racine d'un arbre .et merci d'avance
Ajouter un commentaire
Réponse
+0
moins plus
Salut,

Je te conseil de recherche dans google des pages fait par des professeurs, ce n'est pas évident d'écrire le code sur un forum car tu as plusieurs méthodes à écrire. De plus, p-t meme si tu en voyais un, juste le langage utilisé te rendrait gaga.

Mais pour supprimer un noeud, on se base sur le même principe que les arbres binaire de recherche, On suprrime pas le noeud directement, on le remplace par une des feuille de l'arbre et ensuite on supprime la feuille. La différence pour les arbres un peu plus complexe, on doit les rééquilibrer de nouveau ensuite la supression.

Pour choisir la feuille, si tu prends l'enfant gauche de ton noeud à suprimé, tu recherches la feuille (ou le noeud) la plus à droite de cet enfant. Ensuite, tu echanges ce qu'il contient le noeud. Finallement, si tu as trouver une feuille, tu la supprimes directement ou si tu tombes sur un noeud qui à un enfant à gauche( car on cherchait le plus a droit), tu refais la methode de cherche d'une feuille....... Ca sens la recursion!

Ensuite pour équilibrer un arbre rouge noir, tu as besoin l'algo de rotation.....
oublie moi pour t'expliquer sans dessin............

Bref, difficile d'écrire ca sans image, mais cherche sur le net pour des notes de professeur.
Ajouter un commentaire
Ce document intitulé «  suppression dans un arbre rouge et noir  » issu de CommentCaMarche (www.commentcamarche.net) est mis à disposition sous les termes de la licence Creative Commons. Vous pouvez copier, modifier des copies de cette page, dans les conditions fixées par la licence, tant que cette note apparaît clairement.

Vous n'êtes pas encore membre ?

inscrivez-vous, c'est gratuit et ça prend moins d'une minute !

Les membres obtiennent plus de réponses que les utilisateurs anonymes.

Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes.

Le fait d'être membre vous permet d'avoir des options supplémentaires.