问平衡二叉树的定义
EN

Stack Overflow用户

提问于 2013-02-01 11:47:50

回答 1查看 1.4K关注 0票数 2

因此，我一直在研究平衡二叉树。

我用谷歌搜索了一下，我找到的是：

其中每个节点的两个子树的深度相差1或更小的二叉树(来自维基百科)

难道我们不能将平衡二叉树定义为高度不超过ceil( log (n+1) /log2)的树吗？

从这个答案看，Is Binary Search tree balanced?，提问者似乎已经问了很多相同的问题，但被接受的答案拒绝了这个想法，给出了斐波那契树的例子。斐波那契树不是平衡树，对吧？我认为答案可能会与AVL树中平衡树的定义混淆，据我所知，平衡树允许某些不平衡树

回答已采纳

发布于 2013-02-01 14:14:01

除非我的计算是错的，否则这个定义是行不通的。例如，以高度为6的完整二叉树为例，它有63个节点。如果移除底部的两个同级节点及其父节点，则有60个节点。这棵树是不平衡的，但它的高度仍然等于ceil( log (n+1) /log2)。

票数 1

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

原文链接：

https://stackoverflow.com/questions/14639411

复制

相似问题

问平衡二叉树的定义EN