Splay tree:对于splay树，有序遍历是否按递增顺序查看节点？

Question

我刚刚完成了一个关于这方面的测试，我使用了一个顺序遍历来检查我的splay树中的节点顺序是否正确。这是有效的吗？

Answer 1

是的，顺序遍历以递增的顺序访问splay树的元素。

根据展开树in the original article的定义

分叉树(

splay tree )是一种自调整的二叉树

因此，splay树只是一个按结构的常规二进制搜索树，这就是按顺序遍历以按递增顺序访问元素所需的全部内容。除此之外，沿着展开树的搜索路径的操作修改了结构，但它们以一种不违反binary search tree invariants的方式这样做。