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によるノードポインタの内容が変わっています。私がやりたかったのはこれだけでした: ノード (y が指す) のポインター (親) を変更し、x の親を指すようにします。

ノード構造は次のとおりです。

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

何か不足していますか？ポインターの基本的なプロパティ?

編集: 313 ページ コーメンのアルゴリズム入門

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

提示するコードの 2 つのバージョンは実際には同等です。ただし、このアルゴリズムの実装は、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 に答える