c - 当我在 splay 树中遍历时，现在哪个是根？

Question

我有一个疑问，当我们使用 splay 树时，最后访问的元素会到达根节点。考虑我的树是

                     5
                    / \
                   3   7
                  / \ / \
                 2  4 6  8

当我执行中序遍历时，输出将是

     2 3 4 5 6 7 8 

所以这里最后访问的元素是8，我有疑问，所以8将是最后访问的节点，所以我们想移动8 是否作为根节点？

Answer 1

你的逻辑是正确的。但是展开的操作只在插入和查找时进行，而不会在遍历时进行。当您插入或搜索一个节点时，它会被移动到顶部(作为根节点)，以便此后可以快速访问它。