为什么教科书上的八角树和我的不一样？
Why is splay tree in textbook different than mine?
在 C++ 中的数据结构和算法分析（第 4 版） 中，Mark Allen Weiss 在第 162 页的图 4.50 中描述了如何展开最左边的 child只剩下children的树最终看起来像。
我感到困惑的是本书如何从第 2 步进入第 3 步。以下是第 162 页图 4.50 中突出显示的步骤：
而我的第三步是这样的：
7
/
6
/
1
\
3
/ \
2 4
\
5
我的第四步也是最后一步是这样的：
1
\
4
/ \
3 6
/ / \
2 5 7
我对这本书如何平衡树感到困惑。对我来说，当 1 超过 4 时，树的底部看起来像这样：
...
/
1
\
2
\
3
\
4
我的逻辑是，发生平衡的根是 2。然后向左旋转，树的底部将如下所示：
...
/
1
\
3
/ \
2 4
我是在做错什么，还是只是以一种与书本不同但同样有效的方式来做？我也很困惑，因为这本书的最终树从 6 的根开始是不平衡的，而我的 4 的根没有不平衡。
这主要是 "Zig-zig" 的情况，直到向上，所以每次你在节点的 grandparent 上进行右旋转，然后在 parent 上进行右旋转。
举个例子：
5
/
4
/
3
/
2
/
1
如果你想张开 1，你先围绕 3 然后 2 旋转，结果是：
5
/
4
/
1
\
2
\
3
因为又是 Zig-Zig 的情况，我们先轮换 5，然后轮换 4，结果：
1
\
4
/ \
2 5
\
3
所以你一直这样做，直到你有 1 作为 root。有3种情况，Zig-Zig，Zig和Zig-Zag。 Here is a tool 将整个概念可视化，我相信它会有所帮助。
在 C++ 中的数据结构和算法分析（第 4 版） 中，Mark Allen Weiss 在第 162 页的图 4.50 中描述了如何展开最左边的 child只剩下children的树最终看起来像。
我感到困惑的是本书如何从第 2 步进入第 3 步。以下是第 162 页图 4.50 中突出显示的步骤：
而我的第三步是这样的：
7
/
6
/
1
\
3
/ \
2 4
\
5
我的第四步也是最后一步是这样的：
1
\
4
/ \
3 6
/ / \
2 5 7
我对这本书如何平衡树感到困惑。对我来说，当 1 超过 4 时，树的底部看起来像这样：
...
/
1
\
2
\
3
\
4
我的逻辑是，发生平衡的根是 2。然后向左旋转，树的底部将如下所示：
...
/
1
\
3
/ \
2 4
我是在做错什么，还是只是以一种与书本不同但同样有效的方式来做？我也很困惑，因为这本书的最终树从 6 的根开始是不平衡的，而我的 4 的根没有不平衡。
这主要是 "Zig-zig" 的情况，直到向上，所以每次你在节点的 grandparent 上进行右旋转，然后在 parent 上进行右旋转。
举个例子：
5
/
4
/
3
/
2
/
1
如果你想张开 1，你先围绕 3 然后 2 旋转，结果是：
5
/
4
/
1
\
2
\
3
因为又是 Zig-Zig 的情况，我们先轮换 5，然后轮换 4，结果：
1
\
4
/ \
2 5
\
3
所以你一直这样做，直到你有 1 作为 root。有3种情况，Zig-Zig，Zig和Zig-Zag。 Here is a tool 将整个概念可视化，我相信它会有所帮助。