data-structures - 二叉搜索树的运行时间复杂度

Question

我已经知道如果您尝试查找具有特定键的项目，最坏情况的运行时间是O(n)，n是节点数。如果您尝试按键的顺序打印所有数据项，那么最坏情况的运行时间是O(n). 如果您尝试搜索特定数据项（您不知道密钥），那么最坏情况的运行时间是 O(n)。但是，如果键和数据都是整数，并且输入项在插入之前被随机打乱怎么办。运行时间的最坏情况是否仍然相同？

Answer 1

在最坏的情况下，是的。具有 n 个节点的随机构建的 BST 有 2 ^n-1 / n! 退化构建的机会，这是极其罕见的，因为 n 可以达到任何合理的大小，但仍有可能。在这种情况下，查找可能需要 Θ(n) 时间，因为搜索可能需要一直下降到最深的叶子。

但是，在预期中，树的高度将是 Θ(log n)，因此查找将花费预期的 O(log n) 时间。

顺便说一句，打印一棵树的时间与树的形状无关。它总是 Θ(n)。

希望这可以帮助！

Answer 2

您可能无法更改正常 BST 的最坏情况运行时间，但是，如果您随机化输入（在小于 O(log n) 的时间内，如果您的总体目标是 O(log n)），那么机会发生的最坏情况非常罕见。请参阅此处的数学分析。

如果您对保证的 O(log n) 时间感兴趣，您可以使用平衡 BST，例如红黑树等。但是，打印时间仍然是 O(n)，因为您仍然需要先访问每个节点才可以打印它。