algorithm - 展开树：中序遍历是否以展开树的升序查看节点？

Question

我刚刚完成了一项考试，在那里我使用了中序遍历来检查我的一个展开树中的正确节点顺序。这是有效的吗？

Answer 1

是的，按顺序遍历以升序访问展开树的元素。

根据原始文章中splay树的定义：

splay树，（是）一种自调整形式的二叉搜索树

因此，展开树只是按结构划分的常规二叉搜索树，这是按顺序遍历以升序访问元素所需的全部内容。除此之外，沿展开树的搜索路径的操作会修改结构，但它们这样做的方式不会违反二叉搜索树的不变量。