二叉搜索树时间复杂度

Question

我现在正在使用二叉搜索树。我想知道二叉搜索树的 Tim 复杂度是多少。更具体什么是二叉搜索树的操作高度、叶子和 toString 的最坏情况的时间复杂度，为什么？

Answer 1

所有三个操作的时间复杂度均为 O(n) worst-case。

对于height：当树退化时将访问所有节点，并且除一个节点外的所有节点只有一个子节点。

对于leaves：必须访问每个节点以检查它们是否离开。

对于toString：显然需要访问所有节点。