[C] Binär-Baum Wurzel festlegen

[Oestinator]

Ok, folgendes Problem:

Ich habe in C die Datenstruktur eines binären Baumes wie folgt gegeben:

Code:

typedef struct _tree {
        int v;
        struct _tree *left , *right, *parent;
        }TreeRec, *Tree;

*left und *right zeigen dabei stets auf den linken/rechten Knoten des aktuellen Knotens und *parent auf den Vorgänger des Knotens (sofern er existiert).

Zudem eine Funktion, die einen Baum initialisiert/konstruiert:

Code:

Tree cons(int v, Tree tl , Tree tr) {
    Tree tmp;
    tmp =(Tree) malloc(sizeof(TreeRec));
    if(tmp == NULL) {printf("{cons} Memory full\n");} 
    else {
        tmp ->v = v;
        tmp ->left = tl;
        tmp ->right = tr;
        tmp ->parent = NULL;
        if(tl) {tl->parent = tmp;} //ist der linke Teilbaum!=NULL, so wird tmp als sein Parent gesetzt
        if(tr) {tr->parent = tmp;}// analog
        }
    return tmp;
    }

Mein Problem dabei ist, dass ich gerne eine Struktur *root definieren möchte, die stets auf den Wurzelknoten des Baums zeigt. Allerdings habe ich absolut keine Ahnung, wie ich root in diesem Fall definieren müsste, damit das klappt.
Ich hoffe, jemand kann mir bei meinem Problem helfen.

EDIT: Ich möchte darauf aufbauend einen Algorithmus schreiben, der einen Baum rotiert, um die Eigenschaften eines AVL-Baumes wiederherzustellen. Dabei muss in einigen Fällen auch der Wurzelknoten ausgetauscht werden.

[Whiz-zarD]

Jeder Knoten stellt doch ein Wurzelknoten, für einen Teilbaum, dar. Der Rootknoten hat dann als Parent den NULL-Zeiger.
Demnach könntest du über die Parent Information nach oben iterieren, bis du den Root-Knoten erreicht hast, also bis ein Knoten den NULL-Zeiger als Parent hat.
Dann bräuchtest du nicht einmal diese Information speichern.

[Oestinator]

Jeder Knoten stellt doch ein Wurzelknoten, für einen Teilbaum, dar. Der Rootknoten hat dann als Parent den NULL-Zeiger.
Demnach könntest du über die Parent Information nach oben iterieren, bis du den Root-Knoten erreicht hast, also bis ein Knoten den NULL-Zeiger als Parent hat.
Dann bräuchtest du nicht einmal diese Information speichern.

...

Ja, das ist mir bewusst.
Allerdings wird der Knoten, dessen Parent auf NULL zeigt, nicht unbedingt auch als Wurzelknoten des gesamten Baumes behandelt.
Wenn ich z.B. folgenden Baum vorliegen habe:

Code:

      5 --> Wurzelknoten
     /
   4
  /
3

Durch eine Rechtsrotation möchte ich den Baum wieder korrigieren, also dass er wie folgt aussieht:

Code:

    4 --> 4 ist dabei der neue Wurzelknoten
   / \
  3   5

Allerdings wird Knoten der '5' als Eintrag weiterhin als Wurzelknoten behandelt, obwohl der Parent von '5' auf die '4' zeigt und die '4' richtigerweise keinen Parent besitzt.
Wenn ich jetzt einen neuen Knoten mit den Wert '2' einfüge, sieht mein Baum so aus:

Code:

    4 
   / \
  3   5
     /
    2

Die '2' müsste eigentlich links unter die '3'. Allerdings ist '5' weiterhin als root definiert, von daher würde dieser Knoten nie dort ankommen, wo er eigentlich hin sollte.

Hier ist auch mal der Rotationsalgorithmus:

Code:

void rotateR(Tree y, Tree *root) {
    Tree x, z;
    x = y->left; z = y->parent;
    if(z==NULL) {(*root) = z;} //wenn y keinen parent hat, wird z als neue Wurzel definiert
    else if(z->left == y) {z->left = x;}
         else {z->right = x;}
    y->left = x->right; x->right = y; //Rechtsrotation
    x->parent = y->parent; y->parent = x;
    if(y->left != NULL) {y->left ->parent = y;}
}

Hierbei wird eine Rechtsrotation durchgeführt, wie in meinem Beispiel oben. Als Eingabe-Parameter Tree *root muss dabei auf die Wurzel des Gesamtbaums zeigen.

[Whiz-zarD]

Du musst ja aber auch bei der Rotation den Parent-Zeiger ändern. Ansonsten besitzt der Zeiger nach einer Rotation falsche Informationen.
Also müsste der Parent-Zeiger von 4 den Parent-Zeiger von 5 besitzen und 5 hat als Parent 4 und somit wäre wieder alles korrekt.

[Oestinator]

Du musst ja aber auch bei der Rotation den Parent-Zeiger ändern. Ansonsten besitzt der Zeiger nach einer Rotation falsche Informationen.
Also müsste der Parent-Zeiger von 4 den Parent-Zeiger von 5 besitzen und 5 hat als Parent 4 und somit wäre wieder alles korrekt.

...

Das wird doch mit diesem Befehl

Code:

x->parent = y->parent; y->parent = x

gewährleistet, oder nicht? oO

[Whiz-zarD]

gewährleistet, oder nicht? oO

...

Naja, hab deinen Code nicht wirklich angeschaut, weil ich den Stil sehr gruselig finde.
x, y, z ist für mich so nichtssagend.

[Oestinator]

Also y und x sind die Knoten, die vertauscht werden.
z ist der Parent von y, der nach der Rotation der Parent von x wird.

[Whiz-zarD]

Und wofür brauchst du *root?

[Oestinator]

Das soll der Zeiger auf die Wurzel des Gesamtbaumes sein. Und genau da liegt mein Problem.

[Whiz-zarD]

Naja, wenn du aber die Parents nach der Rotation richtig setzt, wo liegt denn da noch das Problem den Rootknoten zu ermitteln, wenn du doch in der Lage bist, den Baum komplett nach oben zu wandern?
Dann kann man doch den Rootknoten von jedem x-beliebigen Knoten im Baum ermitteln.

[Drakes]

Ich glaube, dass was du willst, ist etwa das Folgende:

Code:

typedef struct foo{
        TreeRec *root;
} root_buffer ;
typedef struct _tree {
        int v;
        struct _tree *left , *right, *parent;
        root_buffer *root;
        }TreeRec, *Tree;

Dann kannst du jedem Knoten das gleiche "root_buffer" Element als root zuweisen und must den Wurzelknoten nur in diesem Buffer neu setzen.
(Keine Ahnung ob das einen bestimmten Namen hätte, statt Buffer)
Ein beinahe gleicher Weg, wäre, was einigigermassen Sinn machen Würde, dass du zwei Strukturen hast für Tree und TreeNode, dann könnte jeder TreeNode auf den Tree verweisen und der Tree kennt den Root TreeNode, aber z.T. wird das recht mühsam, man muss immer überprüfen, ob dieses oder jenes die RootNode geändert hat.