Signaler

Suppression dans un arbre rouge et noir

Posez votre question 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
Afficher la suite 
Utile
+0
moins plus
j aurai besoin d une methode pour supprimer une racine d'un arbre .et merci d'avance
Ajouter un commentaire
Utile
+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

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.

Vous n'êtes pas encore membre ?

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