algorithm - Splay 树最坏情况搜索时间

Question

由于 splay tree 是一种不平衡二叉搜索树 ( brilliant.org/wiki/splay-tree )，它不能保证最大为 O(log(n)) 的高度。因此，我认为它不能保证 O(log(n)) 的最坏情况搜索时间。

但根据bigocheatsheet.com :

Splay Tree 的最坏情况搜索时间为 O(log(n))???

Answer 1

你是对的；对于不平衡的树，在伸展树(Splay Tree)中查找的成本可以达到 Θ(n)。

像 big-O 备忘单这样的许多资源要么做出简化的假设，要么只是包含与事实不符的数据。目前还不清楚他们是在这里错了，还是他们在谈论分摊的最坏情况等等。

最好了解您正在使用的数据结构的内部结构，这样您才能了解运行时的来源。