rechtsrotation in einen avl baum

Fedaykin

Hallo, ich habe folgende funktion zu einer rechtsrotation in einen binärbaum geschrieben. Jedoch scheinen irgendwo zeiger nicht richtig "umgebogen" zu werden. Aber ich seh den Fehler nicht.

Zu Rechtsrotation.

es muss um den knoten 15 und 12 rotiert werden:
12 kommt an den platz der 15, 15 wird rechts an 12 angehangen, das was rechts an der 12 hängt muss links an die 15 ran alles andere bleibt so.

also nach der rotation sieht der baum dann so aus

Zumindest sollte er so aussehen. Das problem was bei mir auftritt ist das ich wenn ich den baum ausgebe 10,12,11 an dem richtigen platz habe aber rechts von der 12 kommt immer wieder 11,12,11,12 als würde es dort referenzen im kreis geben und ich weiss nicht wieso. Ggf übergebe ich den startknoten falsch?

hier der eigentliche Code:

/**
* rotiert um den übergebenen startknoten einfach rechts so das hinterher 
* wieder ein gültiger AVL Baum entsteht
* @param tree der Baum innerhalb dessen rotiert wird um bei einer rotation um die Wurzel diese neu zu setzen
* @param startnode der Knoten welcher der Ausgangspunkt der Rotation ist (am weitesten oben liegender Knoten der Rotation)

* dabei ist noch auf Root zu prüfen und ggf neu zu setzen
*/
void rightRotate( avlnode * startnode, avlTree * tree )
{
    printf("rR\n");
    //Zeiger auf die zwei "Tauschknoten" Speichern
    //der zweite ist startnode, um einfacheren zugriff drauf zu ermöglichen
    avlnode * node1 = startnode->leftChild;
    if ( startnode->parent == NULL )
    {
        //behandlung für wurzel
        //Knoten 1 wird nach oben "gezogen" Vater für den knoten neu setzen
        //node 1 wird nun wurzel
        tree->root = node1;
        node1->parent = NULL;        
    }
    else
    {
        //Knoten 1 wird nach oben "gezogen" Vater für den knoten neu setzen
        node1->parent = startnode->parent;        
        //rechten knoten nach oben "ziehen"
        if (startnode->parent->leftChild == startnode) startnode->parent->leftChild = node1 ;
        else if ( startnode->parent->rightChild == startnode) startnode->parent->rightChild = node1;
    }
    //ACHTUNG zur Zeit hat starnode nicht den richtigen Vater dies muss später gesetzt werden
    //sofern linkes Kind von knoten 1 existiert dieses rechts an den startknoten anhängen
    if ( node1->rightChild != NULL )
    {
        startnode->leftChild = node1->rightChild;
        node1->rightChild->parent = startnode;
    }
    //startknoten rechts an knoten 1 anhängen
    node1->rightChild = startnode;
    startnode->parent = node1;
    //gewichtungen neu setzen
    node1->weight = '-';
    startnode->weight = '-';  
}

c.rackwitz

kannst du bitte auch testdaten dazuliefern, sodass man den code auch mal laufen lassen kann?

edit: benutz bitte [cpp] tags. gibt weihnachtsbeleuchtung fuer den code.

Fedaykin

hab den fehler mittlerweile gefunden aber trotzdem danke.
das problem lag hier.

if ( node1->rightChild != NULL )
    {
        startnode->leftChild = node1->rightChild;
        node1->rightChild->parent = startnode;
    }

denn startnode->leftChild muss im fall node1->rightChild auf jedenfall auch auf NULL gesetzt werden ansonsten zeigt es noch auf einen eintrag der wiederum auf node1 zeigt welcher wiederum auf den eintrag zeigt.... naja man kennt das ja notfalls mit einer Kreisreferenz.

und zu den cpp tags naja irgendwie trenne ich c und c++ ziemlich und daher hab ich nicht daran gedacht das die grundsyntax die gleiche ist