如何旋转子树而不知道其父 [英] How to rotate a subtree without knowing its parent

问题描述

我想向左旋转子树根节点 N （见左图），而不操作其父 P 。

  PPP 
 \ | \ 
 N | RR 
 / \ | / / 
 LRNN 
 / / 
 LL 
  

b $ b

如果我在函数中使用 N 作为参数：

  void rotate_left（Node * node）; 
  

我最终会在中间的一个树上出现一个树。问题是，尽管旋转 P 仍然指向 N ，而不是 code>（左图）。如果函数 rotate_left（）在循环结束时如何使 P 指向 R 没有指向 P ？

的指针我认为有三种方法this：

1. 让 rotate_left（）节点 N

     void rotate_left（Node *& node）; 
     

   然后调用 rotate left（）它是 P （即
   N ）的正确的孩子：

     rotate_left（P-> right_child）; 
     




2. 将对象 R
   结束时 N 的内存地址




3. 将父P传递到 rotate_left（）：

     ; 
     

解决方案（1）在调用 rotate_left（） P >。

解决方案

解决方案1是您建议的三个方案中最好的。它或多或少等同于解决方案3.我会使用。在我看来，在任何地方你调用 rotate_left 你已经知道这个指针存储的变量（父节点或 root ），因此传递它的引用不会是一个问题。

解决方案2（交换内容）将使已经存在于树外的任何指针无效。你必须非常小心;如果有这样的指针，不要使用它。但是，这是你的问题如何旋转而不知道父节点的唯一真正的答案。

我想你不想保留指向父节点的指针在树上。如果你准备这样做，一切都会容易得多。

I'd like to rotate left the subtree rooted at node N (see left figure) without manipulating its parent P.

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

If I will to it in a function, that takes N as an argument:

void rotate_left(Node *node);

I will end up with a tree presented on the middle figure. The problem is that despite the rotation P still points to N, not to R (left figure). How to make P pointing to R at the end of rotation if the function rotate_left() does not have a pointer to P?

I think of three ways of doing this:

1. Let rotate_left() takes a reference to pointer to node N

   void rotate_left(Node * &node);
   

   Then call rotate left(), passing it a right child of P (that is N):

   rotate_left(P->right_child);
   

2. Place object R under the memory address of N at the end of rotation

3. Pass parent P to rotate_left():

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

Solutions (2) and (3) don't sound good, and in the solution (1) you need to know parent P in function that calls rotate_left().

解决方案

Solution 1 is the best of the three you're suggesting. It is more or less equivalent to Solution 3. I'd use that. It seems to me that everywhere you call rotate_left you already know the variable where this pointer is stored (either the parent node, or root), so it wouldn't be a problem passing its reference.

Solution 2 (swapping the contents) will invalidate any pointers that already exist outside your tree. You'll have to be very careful; if there are such pointers, don't use it. However, this is the only true answer to your question "how to rotate without knowing the parent?".

I suppose you wouldn't want to keep pointers to parent nodes in the tree. If you're prepared to do that, everything will be much easier.

这篇关于如何旋转子树而不知道其父的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！