二进制搜索树是否平衡？

Question

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

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.

请注意,只有完整的树具有高度lg(n).

在Fibonacci树上查找示例,这是一棵平衡树(实际上是AVL树的最坏情况).但是 - 它的高度大于lgn(~1.44*lg(n)),并且建议的算法将返回不平衡的斐波纳契树.