很抱歉再次打扰你们，但我有一个问题，我已经好几天没有自己弄清楚了。它是关于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;
}
提前致谢！！
棘手的部分确实是*&部分。这将其声明为对指针的引用（这里有一个或两个链接到一些类似的示例代码，但我担心它们可能比有用更令人困惑）。
通过更改指针指向的节点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的原始父级) 的人现在指向内存中的同一位置，但该值现在已替换为已旋转的子级。