二分查找树的运行时间复杂度
二分查找树的运行时间复杂度
提问于 2013-10-31 14:09:54
我已经知道，如果你试图找到具有特定关键字的项，最坏情况下的运行时间是O(n)，n是节点的数量。如果您尝试按键的顺序打印所有数据项，那么最坏情况下的运行时间是O(n)。如果您试图搜索特定的数据项(您不知道关键字)，那么最坏情况下的运行时间为O(n)。但是，如果键和数据都是整数，并且输入项在插入之前是随机加扰的，该怎么办？运行时间的最坏情况还会是一样的吗？
回答 1
Stack Overflow用户
发布于 2013-10-31 14:22:16
您可能无法更改正常BST的最坏情况运行时间，但是，如果您随机化输入(在少于O(log )时间内，如果您的总体目标是O(log ))，那么发生这种最坏情况的机会非常少。请参见数学分析here。
如果你对保证的O(log )时间感兴趣，你可以使用Balanced BSTs，如红黑树等。然而，打印时间仍然是O(n)，因为你仍然需要访问每个节点才能打印它。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/19699529
复制相关文章
相似问题
腾讯云开发者
