指针交换奇怪

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; 
}