Arbre rouge noire

public class noeuds
{
	 String couleur;
	   int info;
	   noeuds noeudsAjoute;
	   noeuds gauche, droit, parent;
	   static noeuds racine;
	  
	   
	   static noeuds sentinelle;
	   public noeuds(int o,String co){info=o;couleur=co;}
	   public noeuds ajout( int o, noeuds r, noeuds p){
		   // p est le parent de r 
		   if (r.isSentinelle())  r = noeudsAjoute = new noeuds(o, "rouge", r, r, p);
		   else
		      if(o<r.info) r.gauche = ajout(o, r.gauche, r);
		      else r.droit = ajout(o, r.droit, r);
		   return r;
		}
	   public noeuds (int o, String c, noeuds g, noeuds d, noeuds p){
		      couleur = c;
		      info = o;
		      gauche = g;
		      droit = d;
		      parent = p;
		   }
	   public noeuds(int p, String c, noeuds g, noeuds d) {
		// TODO Auto-generated constructor stub
		   couleur = c;
		     gauche = g;
		      droit = d;
		      info = p;
	}
	   boolean isSentinelle(){
		      return this == ArbreRougeNoir.sentinelle;
		   }
	   private void rotationDroite( noeuds n){
		   noeuds y = n.gauche;
		   n.gauche = y.droit;
		   if(!y.droit.isSentinelle())y.droit.parent = n; // on ne change pas le parent de la sentinelle
		   y.parent = n.parent;
		   if (n.parent==null) racine = y;
		   else
		      if( n.parent.droit == n) n.parent.droit = y;
		      else n.parent.gauche = y;
		   y.droit = n;
		   n.parent = y;
		}
	   private void rotationGauche( noeuds n){
			noeuds y = n.droit;
			   n.droit = y.gauche;
			   if(!y.gauche.isSentinelle())y.gauche.parent = n;// on ne change pas le parent de la sentinelle
			   y.parent = n.parent;
			   if (n.parent==null) racine = y;
			   else
			      if( n.parent.gauche == n ) n.parent.gauche = y;
			      else n.parent.droit = y;
			   y.gauche = n;
			   n.parent = y;
			}
	
	public  void reOrganiser( noeuds n){
		   // re organisation de l'arbre, en remontant vers la racine
		   while(n != racine && n.parent.couleur == "rouge" ){
		      if(n.parent == n.parent.parent.gauche){
			    noeuds y = n.parent.parent.droit;
			    if( y.couleur == "rouge" ){
				   n.parent.couleur ="noir";
				   y.couleur = "noir";
				   n.parent.parent.couleur = "rouge";
				   n = n.parent.parent;
			    }else{
				   if(n == n.parent.droit){
				      n = n.parent;
				      rotationGauche(n);
				   }
				   n.parent.couleur ="noir";
				   n.parent.parent.couleur = "noir";
				   rotationDroite(n.parent.parent);
			    }
			  }else{
			    noeuds y = n.parent.parent.gauche;
			    if( y.couleur == "roug" ){
				   n.parent.couleur = "noir";
				   y.couleur = "noir";
				   n.parent.parent.couleur = "noir";
				   n = n.parent.parent;
			    }else{
				   if(noeudsAjoute == n.parent.gauche){
				      n = n.parent;
				      rotationDroite(n);
				   }
				   n.parent.couleur = "noir";
				   n.parent.parent.couleur = "rouge";
				   rotationGauche(n.parent.parent);
			    }
			  }
		   }
		   racine.couleur = "noir"; // la racine est toujours noire
		}
	public static void imprimer(noeuds A,int tab)
	   {
		   if(A!=null)
			   {
			   for( int i = 0; i< tab-3; ++i) System.out.print(" ");	
			   System.out.println(A.couleur);
			   for( int i = 0; i< tab; ++i) System.out.print(" ");	
			   System.out.println(A.info); 
		   if(A.gauche!=null)
			   imprimer(A.gauche,tab);
		   if(A.droit!=null)
			   imprimer(A.droit,tab);
			   }
		   if(A.parent!=null)
			   imprimer(A.parent,tab);
			   
		   
		   
	   }