java - 二叉搜索树是平衡的吗？

Question

这个已经讨论过了here ，但我在下面有一个实现(在线程中从未讨论过)，

public boolean isBalanced(BSTNode node) {
    if(maxHeight() > (int)(Math.log(size())/Math.log(2)) + 1) 
        return false;
    else
        return true;
}

其中 maxHeight() 返回树的最大高度。基本上我是在检查 maxHeight > log(n)，其中 n 是树中元素的数量。这是正确的解决方案吗？

Answer 1

这个解决方案是不正确的。如果平衡树的高度为 O(lg(n))，那么它(高度)需要小于 c*lg(n) - 因为一些常数 c。您的解决方案假定此常数为 1。

请注意，只有一个 complete tree高度 lg(n) 正好。

以 Fibonacci tree 为例，是一棵平衡树(实际上是 AVL tree 的最坏情况)。但是 - 它的高度大于 lgn (~1.44*lg(n))，并且建议的算法将返回不平衡的斐波那契树。