指針交換奇怪

Question

我有以下工作代碼，紅黑樹旋轉。

void BalancedTree::rotateLeft(Node* & x){ 
37 Node* y = x->right; 
38 
39 x->right = y->left;//slice y's left child 
40 x->right->parent = x; 
41 
42 y->left = x;//switch x and y's parentship 
43 Node* xp = x->parent;//for some reason, y->parent = x->parent causes logic 
    errors. 
44 x->parent = y; 
45 y->parent = xp; 
46 
47 if (y->parent == nil) root = y;//fix grandparent 
48 else if (y->parent->parent->left == x) y->parent->parent->left = y; 
49 else y->parent->parent->right = y; 
50 } 

當線43和45是由替換（保持44）

y->parent = x->parent 

或者，只是交換線44和45，節點指針的用x含量改變。我想要做的就是：改變Node中的指針（父）（由y指向），並讓它指向x的父節點。

節點結構爲：

struct Node{ 
    Node* parent; 
    Node* left; 
    Node* right; 
    int value; 
}; 

我這麼想嗎？指針的基本屬性？

編輯：頁313 Cormen的算法導論

LEFT-ROTATE(T, x) 
1 y = x.right 
2 x.right = y.left 
3 if y.left != T.nil 
4 y.left.p = x 
5 y.p = x.p 
6 if x.p == T.nil 
7 T.root = y 
8 elseif x == x.p.left 
9 x.p.left = y 
10 else x.p.right = y 
11 y.left = x 
12 x.p = y 

EDIT2：這裏是不工作的代碼：

36 void BalancedTree::rotateLeft(Node* & x){ 
37 Node* y = x->right; 
38 
39 x->right = y->left;//slice y's left child 
40 x->right->parent = x; 
41 
42 y->left = x;//switch x and y's parentship 
43 y->parent = x->parent; 
44 x->parent = y; 
45 
46 
47 if (y->parent == nil) root = y;//fix grandparent 
48 else if (y->parent->parent->left == x) y->parent->parent->left = y; 
49 else y->parent->parent->right = y; 
50 } 

Answer 1

你的代碼的兩個版本，你現在確實是等價的。然而，你的這個算法的實現與你的Cormen參考文獻中所寫的算法沒什麼關係。您的代碼應爲：

void BalancedTree::rotateLeft(Node* & x){ 
    Node* y = x->right; 
    x->right = y->left; 
    if (y->left != nil) 
     y->left->parent = x; 
    y->parent = x->parent; 
    if (x->parent == nil) 
     root = y; 
    else if (x == x->parent->left) 
     x->parent->left = y; 
    else 
     x->parent->right = y; 
    y->left = x; 
    x->parent = y; 
}