[C] Binär-Baum Wurzel festlegen

[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.