[C] Binär-Baum Wurzel festlegen

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