与AVL,Redblack trees相比,我认为splay tree没有存储任何额外的信息位,但是为什么wiki提到空间复杂性是O(n) https://en.wikipedia.org/wiki/Splay_tree 还有 https://www.bigocheatsheet.com/ 提到O(n)。是因为元素遍历/展开期间的堆栈递归空间还是我遗漏了什么?非常感谢您的帮助。
