c++ - 親を知らずにサブツリーを回転させる方法

Question

N親を操作せずに、ノード (左の図を参照) をルートとするサブツリーを左に回転させたいと思いますP。

P             P              P   
 \            |               \
  N           | R              R
 / \          |/              /
L   R         N              N
             /              /
            L              L

関数でそれを行う場合、それはN引数として取ります:

void rotate_left(Node *node);

真ん中の図に提示された木で終わります。問題は、回転にもかかわらず、(左図)ではなく をP指していることです。関数に へのポインターがない場合、回転の最後にを指すようにする方法は?NRPRrotate_left()P

これを行うには、次の 3 つの方法を考えます。

1. Letrotate_left()はノードへのポインタへの参照を取りますN

   void rotate_left(Node * &node);
   

   次に を呼び出し、 (つまり )rotate left()の右の子を渡します。PN

   rotate_left(P->right_child);
   

2. 回転終了時のRメモリアドレスの下にオブジェクトを配置しますN

3. 親 P を に渡すrotate_left():

   void rotate_left(Node *parent, Node *child);
   

P解決策 (2) と (3) は良く聞こえません。解決策 (1) では、 を呼び出す関数で親を知る必要がありますrotate_left()。