data-structures - 平衡二叉搜索树的定义

Question

所以，我一直在研究平衡二叉搜索树。

我用谷歌搜索了它，这就是我发现的：

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

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

从这个答案看来，二叉搜索树是否平衡？，提问者似乎已经问了很多同样的事情，但接受的答案通过给出斐波那契树的例子来拒绝这个想法。斐波那契树不是平衡树吗？我认为回答者可能对 AVL 树中平衡树的定义感到困惑，据我了解，其中允许某些不平衡树

Answer 1

除非我的计算是错误的，否则这个定义是行不通的。例如，如果你取一棵高度为 6 的完整二叉树，它有 63 个节点。如果删除底部的两个兄弟姐妹及其父节点，则有 60 个节点。这棵树不平衡，但它的高度仍然等于 ceil(log(n+1) / log 2)。