Splay樹：索引遍歷是否按照遞增的順序查看樹狀結構？

Question

我剛剛完成了一個考試，在這裏我使用了一次遍歷來檢查我的一個splay樹中正確的節點順序。這有效嗎？

Answer 1

是的，按順序遍歷按遞增順序訪問splay樹的元素。

通過一個伸展樹in the original article的定義：

的伸展樹，（是）二叉搜索樹的自我調節形式

所以，一個伸展樹只是一個普通的二叉搜索樹的結構，這是按順序遍歷以升序訪問元素所需的全部內容。除此之外，沿着splay樹的搜索路徑進行的操作會修改結構，但它們的操作方式不會違反binary search tree invariants。