3

ご迷惑をおかけして申し訳ありませんが、質問があり、数日間自分で理解できていません。これは、たとえば、treapをposで右回転させるためのtreapの回転に関するものです。問題は、の元の親にどのようにリンク（または接続）pos->leftするかです。pos私はこのコードをオンラインで見つけましたが、それは機能しますが、それが私の質問をどのように解決するのかわかりませんでした、それはの使用のため*&ですか？もしそうなら、私がそれを少し説明するのを手伝ってもらえますか？そして、pos=bこのコードの機能は何ですか？

void Treap::right_rotate(Node *&pos) {
    Node *b   = pos->left; 
    pos->left = b->right;
    b->right  = pos;
    pos       = b;
}

前もって感謝します！！

4

1 に答える 1

8

トリッキーな部分は確かにその*&部分です。それはそれをポインタへの参照として宣言します（ここにいくつかの同様のサンプルコードへのリンクがありますが、それらが役立つよりも混乱するかもしれないと私は恐れています）。

ポインタが指すノードを変更することでpos = b、親を知らなくても内容を別のノードに入れ替えることができます。元の参照が更新され、新しい回転ノードになります。

これは、回転がどのように見えるかを少しやり過ぎた場合に備えて、図を示しています（ただし、その部分を理解しているように聞こえます）。

最初の状態：

Node *&pos; 

         |
        [P]
      /     \
     L       R
    / \     / \ 
   w   x   y   z

次に、Pに関する限り、左の子を上書きしようとしているので、左の子を保存します。

Node *b = pos->left;
pos->left = b->right;

           |
    L     [P]
  /  \   /   \
 w     x      R
             / \ 
            y   z

Lは空間に浮かんでいるので、適切なツリー構造を壊して、回転を終了します。

b->right = pos;

        L     
      /  \ |
     w    [P]
         /   \
        x     R
             / \ 
            y   z

次に、ノードポインタへの参照を更新して、メモリ内のその場所の内容を置き換える新しいノードになるように維持を終了します。

pos = b;

       |
      [L]     
     /   \
    w      P
         /   \
        x     R
             / \ 
            y   z

以前にpos（posの元の親）を指していた人は、メモリ内の同じ場所を指すようになりましたが、その値は、回転された子に置き換えられました。

于 2012-06-28T04:27:15.310 に答える