问在平衡二叉树中搜索项
EN

Stack Overflow用户

提问于 2017-03-30 02:29:38

回答 1查看 1.5K关注 0票数 0

如果我有一个平衡的二叉树，并且我想在其中搜索一个项，那么大的--哦，时间复杂度会是O(n)吗？在二叉树中搜索某一项，无论它是否平衡，都会从O(n)中改变大的我知道，如果我们有一个平衡的BST，那么搜索一个项就等于BST的高度，所以O(log )，但是普通的二叉树呢？

回答已采纳

发布于 2017-03-31 23:47:03

平衡BST中的O(log n)搜索时间由以下两个属性提供了便利：

如果您失去了这些属性中的任何一个，那么您将不再获得O(log )搜索时间。

如果您正在搜索未排序的平衡二叉树(也称为BST)，则必须检查树中的每个节点以确保找到所要查找的值，因此需要O(n)时间。

对于一棵不平衡的树，如果你想象出最坏的情况--失去平衡，每个节点都只有一个子节点，除了叶子--本质上是一个链表，这可能会有所帮助。如果您有一个完全(或大部分)不平衡的BST，搜索将花费O(n)时间，就像链表一样。

如果没有排序的二叉树是不平衡的，它仍然有n个节点，它们仍然是未排序的，所以它仍然需要O(n)时间。

票数 2

页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持

原文链接：

https://stackoverflow.com/questions/43107461

复制

相似问题

问在平衡二叉树中搜索项EN