0

我有以下工作代码，用于红黑树旋转。

 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 行被替换为 (keep 44)

y->parent = x->parent

或者，只是交换第 44 行和第 45 行，x 的 Node 指针的内容被改变了。我想做的就是：更改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 }
4

1 回答 1

0

您提供的两个版本的代码确实是等效的。但是，您对该算法的实现与 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;
}
于 2012-05-18T15:19:20.887 回答