问平衡二叉搜索树和二叉搜索树有什么不同？
EN

Stack Overflow用户

提问于 2015-06-24 21:06:05

回答 2查看 2.1K关注 0票数 0

如果这是一个非常基本的问题，我很抱歉，但我对树相当陌生，因此，这个疑问最近困扰着我。

不是每个BST (二叉树)都已经是BBST (平衡BST)了吗？

发布于 2015-06-25 00:26:53

“平衡”是二叉树可能具有的属性。这通常意味着树中的每个节点在其下面的每个子树上具有大致相同数量的后代节点。更具体地说，它意味着树的“高度”已经最小化。

对于不是“平衡”的树，有可能有一个二叉树，其中所有的“左”子节点都是空的，另外它仍然具有“二叉树”的属性。这被称为退化树，因为它在结构上更像链表，因此搜索时间为O(N)，而不是O(log(N))。

票数 3

发布于 2015-06-24 21:27:29

不同之处在于，平衡二叉树具有可能的最小高度

票数 0

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

原文链接：

https://stackoverflow.com/questions/31027422

复制

相似问题

问平衡二叉搜索树和二叉搜索树有什么不同？EN