如何旋转treap或AVL树？

Question

很抱歉再次打扰你们,但我有一个问题,我几天都没想出来.它是关于一个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;
}

提前致谢!!

Answer 1

棘手的部分确实是其中的*&一部分.这声明它是对指针的引用(这里是一些链接或两个类似的示例代码,但我担心它们可能比有用的更令人困惑).

通过更改指针指向的节点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原始父级)的人现在指向内存中的相同位置,但该值现在已被已旋转的子项替换.