Problem mit Rot/Schwarz-Baum

[MTiN]

Hallo...
ich beiße mir hier gerade die Zähne an einer Implementierung eines Rot- Schwarz-Baumes die Zähne aus...
Wer weiß, vielleicht kennt sich ja hier jemand damit aus und kann mir helfen...

im moment habe ich das Problem, dass meine links/rechts-rotation gar nicht funktionieren KANN wenn um den Ursprung des Baumes rotiert werden soll...weil ich dann ja irgendwie den Ursprung austauschen müsste und das geht nicht innerhalb des Baumes...

so ungefähr hab ich mir das gedacht:

public void rotate_right(baum n){
        baum aktuell = n.li;
        n.li = aktuell.re;
        aktuell.re = n;
            //so?
            //n = aktuell;  --> Verweis auf n wird nicht geändert
            //this = aktuell; wär auch noch ne idee aber das geht natürlich gleich gar nicht^^
            //oder eher so o.o
            if (n.parent.re == n) n.parent.re = aktuell;
            if (n.parent.li == n) n.parent.li = aktuell;
    }

und das funktioniert auch mehr oder weniger...nur eben natürlich nicht wenn um das erste Element des Baumes rotiert werden soll, denn dies hat keinen "vater"...

ist vielleicht schon mein Grundansatz falsch? Also ein Baum ist bei mir praktisch ein Schlüssel und Ein Baum links un einer Rechts...ich kopier hier einfach mal die gesamte klasse rein, nicht wundern das alles noch nicht funktioniert, im moment geht es mir erstmal um die rotation!

import java.awt.Color;
import java.awt.Font;
import java.awt.Graphics;
/*
 * Baum.java
 *
 * Created on 15. November 2006, 21:32
 *
 * To change this template, choose Tools | Template Manager
 * and open the template in the editor.
 */



/**
 *
 * @author MK
 */
public class baum implements Cloneable{
  int schluessel, hoehe;
  baum li, re, parent;
  String color;
  
  public static final baum NIL = new baum();
  
  

   // Object System;
  /**
     * Gibt einen Baum in den Rückgabestring
     */
  public String ausgabe(){
    if (this == NIL) return ""; //leer
    String s = "";
    if (li != NIL) s = li.ausgabe();
    s += schluessel + " ";
    if (re != null) s += re.ausgabe();
    return s;

  }
     
      public void zeichnen(Graphics g,  int l, int r, int t) {
	  g.setFont(new Font("Serif", Font.PLAIN, 14));
	  if (this != NIL){
              String s = ""+ schluessel;
              try{
                 s = ""+ schluessel+"("+parent.schluessel+")"; }catch(Exception e){};
		int x = (int) ((l+r - s.length()*7) / 2);
                Color co = g.getColor();
                if(this.color=="rot") g.setColor(new Color(1.0f,0.0f,0.0f));
                else g.setColor(new Color(0.0f,0.0f,0.0f));
                g.fillOval(x, t*36,10,10);
                g.setColor(co);
		g.drawString(s, x, t*36);
		int x1 = (int) ( (l+r)/2);
		int y1 = t*36 + 7;
		int x2 = (int) ((l+x1)/2);
		int x3 = (int) ((x1+r)/2);
		int y2 = y1 + 36;
		if (li != NIL) g.drawLine(x1, y1, x2, y2);
//		 else g.fillOval(x1-3, y1-3, 6, 6);
		if (re != NIL) g.drawLine(x1, y1, x3, y2);
//		 else g.fillOval(x1-3, y1-3, 6, 6);
	  li.zeichnen(g, l, (int)(l+r)/2, t+1);
	  re.zeichnen(g, (int)(l+r)/2, r, t+1);
	 }
	}
   
      
      public void delete(int wert)
      {
          if (this != NIL){
              if (li.schluessel == wert) li = NIL;
              if (re.schluessel == wert) re = NIL;
	  li.delete(wert);
	  re.delete(wert);
	 }
      }
      
  
   
  /** gibt die Anzahl der Knoten als Ganzzahl zurück*/
  public int anzahl(){
     if (this == NIL) return 0;
     return 1+li.anzahl()+ re.anzahl();
  }
  /**
     * Fügt ein Datum mittels wachse() in den Suchbaum ein. Prüft über anzahl() den Erfolg.
     */
  public boolean einfügen(int key){
      int oldSize = anzahl();

      wachse(key,null);
      
      return anzahl()>oldSize;

  }
  

   /**das eigentliche Einfügen in den Baum mittels Konstruktor*/
    public baum wachse(int key, baum vater) {
        if (this == NIL)  
        { 
            baum neubaum =  new baum(key); 
            neubaum.parent = vater;
            if (key < vater.schluessel) vater.li = neubaum;
            else vater.re = neubaum;
            return neubaum;
        }

        if (key == this.schluessel) return this;
        
        baum eingefügt = new baum();
        if (key <  this.schluessel)  eingefügt = li.wachse(key,this);
        else                         eingefügt = re.wachse(key,this);
        hoehe = 1 + Math.max(li.hoehe,re.hoehe);
        return eingefügt;
    }

    
    
   //den Großvater eines Knotens herausfinden
   public baum grandparent(baum n){
       return n.parent.parent;
   }
    
    //den Onkel eines Knotens herausfinden
    public baum uncle(baum n){
        if (n.parent == grandparent(n).li)
        return grandparent(n).re;
    else
        return grandparent(n).li;
    }
    
    public void einfügen_case1(baum n) {
    if (n.parent == NIL)
        n.color = "schw";
    else
        einfügen_case2(n);
}
    public void einfügen_case2(baum n) {
    if (n.parent.color == "schw")
        return; /* Alle Eigenschaften des Baumes sind immer noch gewahrt */
    else
        einfügen_case3(n);
}
    public void einfügen_case3(baum n) {
    if (uncle(n) != NIL && uncle(n).color == "rot") {
        n.parent.color = "schw";
        uncle(n).color = "schw";
        grandparent(n).color = "rot";
        einfügen_case1(grandparent(n));
    }
    else
        einfügen_case4(n);
}
    
    public void einfügen_case4(baum n) {
    //knoten ist rechts am vater und vater links am großvater
    if (n == n.parent.re && n.parent == grandparent(n).li) {
        rotate_left(n.parent);
        n = n.li;
    //knoten ist links am vater und vater rechts am großvater
    } else if (n == n.parent.li && n.parent == grandparent(n).re) {
        rotate_right(n.parent);
        n = n.re;
    }
    einfügen_case5(n);
}
    
    public void einfügen_case5(baum n) {
    n.parent.color = "schw";
    grandparent(n).color = "rot";
    //knoten ist links am vater und vater links am großvater
    if (n == n.parent.li && n.parent == grandparent(n).li) {
        rotate_right(grandparent(n));
    //knoten ist rechts am vater und vater rechts am großvater
    } else {
        /* Ab hier gilt, n == n->parent->right und n->parent == grandparent(n)->right */
        rotate_left(grandparent(n));
    }
}
     public void rotate_right(baum n){
        baum aktuell = n.li;
        n.li = aktuell.re;
        aktuell.re = n;
            //so?
            //n = aktuell;  --> Verweis auf n wird nicht geändert
            //this = aktuell; wär auch noch ne idee aber das geht natürlich gleich gar nicht^^
            //oder eher so o.o
            if (n.parent.re == n) n.parent.re = aktuell;
            if (n.parent.li == n) n.parent.li = aktuell;
    }
    
    public void rotate_left(baum n){
        baum aktuell = n.re;
        n.re = aktuell.li;
        aktuell.li = n;
        if (n.parent.re == n) n.parent.re = aktuell;
        if (n.parent.li == n) n.parent.li = aktuell;
        //n = aktuell;
    }
    
    /**
     * einen Baum konstruieren
     */
    public baum(int key) {
        schluessel = key;
        li = re  =parent=NIL;
        color = "rot";
    }
    /** leeren Baum konstruieren*/
    private baum(){
        li = re  =parent= this;
        hoehe = -1;
        color = "schw";
    } 

}

Wäre echt für jegliche Hilfe dankbar!

 

[mr.goalie]

Hallo, ich hab mal den guten alten Sedgewick "Algorithmen" bemüht. Da ist eine Rotationsfunktion implementiert, allerdings für delphi. Ich hab es mal in java und passend zu MTiNs baum-programm umgeschrieben, vielleicht hilft das ja jemanden.

public baum rotate(int key,baum vorgänger){
        baum child;
        baum gchild;
        if(key<vorgänger.schluessel) child = vorgänger.li;
        else child = vorgänger.re;
        if(key<child.schluessel){
            gchild = child.li;
            child.li = gchild.re;
            gchild.re = child;
        }
        else{
            gchild = child.re;
            child.re = gchild.li;
            gchild.li = child;   
        }
        if(key<vorgänger.schluessel) vorgänger.li = gchild;
        else vorgänger.re = gchild;
        return gchild;  
    }

Vorgänger ist der Vater des zu rotierenden Knotens, child ein Kind und gchild dessen Kind.
Grüße, mr.goalie