Splay Tree 中的 Zig-zig 旋转是否不同于两次向右或两次向左旋转？
Is a Zig-zig rotation in a Splay Tree different than two right or two left rotations?
我明白 Zig-Zag 旋转基本上是一个 AVL 双旋转。 Zig-zig 旋转与两次向左或两次向右旋转有什么不同吗？我以为他们不是，但如果我只是对下图这样的东西做 2 次右旋转，我会得到错误的答案。
如果确实不是一回事，那么假设Zig-zig旋转是一种特殊类型的旋转是否正确？
区别在于您使用哪些节点进行旋转以及执行这些旋转的特定顺序。让我们调用我们用作参考旋转的节点作为基本节点，所以在 zig zig 情况下我们有 2 个基本节点，第一个是示例中 x 的父节点，即 p，我们首先沿着这个节点右旋转，然后我们沿着节点 x 右旋转。在您提到的情况下，将在相同节点上执行 2 个右旋转。因此，总而言之，它们在我们使用哪些节点旋转以及我们使用它们的顺序方面有所不同，zig zig 首先对父节点进行右旋转或左旋转，然后再对节点进行右旋转或左旋转。
我明白 Zig-Zag 旋转基本上是一个 AVL 双旋转。 Zig-zig 旋转与两次向左或两次向右旋转有什么不同吗？我以为他们不是，但如果我只是对下图这样的东西做 2 次右旋转，我会得到错误的答案。
如果确实不是一回事，那么假设Zig-zig旋转是一种特殊类型的旋转是否正确？
区别在于您使用哪些节点进行旋转以及执行这些旋转的特定顺序。让我们调用我们用作参考旋转的节点作为基本节点，所以在 zig zig 情况下我们有 2 个基本节点，第一个是示例中 x 的父节点，即 p，我们首先沿着这个节点右旋转，然后我们沿着节点 x 右旋转。在您提到的情况下，将在相同节点上执行 2 个右旋转。因此，总而言之，它们在我们使用哪些节点旋转以及我们使用它们的顺序方面有所不同，zig zig 首先对父节点进行右旋转或左旋转，然后再对节点进行右旋转或左旋转。