文章/答案/技术大牛

发布

社区首页 >问答首页 >是否存在平衡的二叉树，而不是平衡的二叉树？时间的复杂性是什么？

问是否存在平衡的二叉树，而不是平衡的二叉树？时间的复杂性是什么？
EN

Stack Overflow用户

提问于 2015-07-28 17:24:47

回答 1查看 523关注 0票数 1

是否存在平衡的二叉树，而不是平衡的二叉树？如果是这样的话，在这样的树中搜索节点的时间复杂度是多少？

我的理解是：

二叉树:任何节点都有两个最大的叶节点。在二叉树中搜索，使用DFS或BFS是O|V+E|。
二进制搜索树: BST是由有序节点组成的树。使用DFS在二进制搜索树中进行搜索
平衡树(假设高度平衡)：在根以下的最高层数保持在最小。平衡对搜索的时间复杂度有影响吗？

所以，从本质上说，我可以创建一个高度平衡但没有排序的二叉树。这棵树的搜索时间是O|V+E|还是更好？

big-o

algorithm

data-structures

tree

回答 1

Stack Overflow用户

回答已采纳

发布于 2015-07-28 17:31:42

搜索无序二叉树需要访问每个节点，所以无论它是否平衡，都是O(N)

          50
       __/  \__
      /        \
    25          26
   /  \        /  \
 49    46    48    47

或者不是

          50
       __/  \__
      /        \
    25          26
   /  \
 49    46
      /  \
     5    6

平衡一棵无序的树是没有意义的。

票数 5

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

原文链接：

https://stackoverflow.com/questions/31683215

复制

相似问题

问是否存在平衡的二叉树，而不是平衡的二叉树？时间的复杂性是什么？
EN

回答 1

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问是否存在平衡的二叉树，而不是平衡的二叉树？时间的复杂性是什么？EN

回答 1

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问是否存在平衡的二叉树，而不是平衡的二叉树？时间的复杂性是什么？
EN