algorithm - 我们可以将链表视为倾斜的树吗

Question

考虑到一棵 Skewed 树，它的所有节点都只有一个特定的方向(左或右)。我们可以说一个有 n 个节点的链表也是一棵高度为 n 的 Skewed 树吗？

Answer 1

是的。列表是退化树。如果需要，您可以将其称为“最大不平衡树”。

事实上，这正是有人说您需要平衡二叉搜索树以获得 O(log n) 查找性能时的意思，因为如果您的树变得不平衡，它就会退化为列表和查找性能变为 O(n)。

有时从另一个方向思考也很有用:大多数人完全可以理解持久列表的工作原理，但很多人很难理解持久树的工作原理。但问题是:它实际上完全像持久列表一样工作，并且通常很容易理解持久树的工作原理，如果您从持久列表开始，然后将该列表重新解释为退化树。