二叉搜索树是平衡的吗？

这已经讨论过了here https://stackoverflow.com/questions/742844/how-to-determine-if-binary-tree-is-balanced，但我在下面有一个实现（线程中从未讨论过），

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 是树中元素的数量。这是正确的解决方案吗？

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

请注意，只有一个完整的树 http://en.wikipedia.org/wiki/Binary_tree#Types_of_binary_trees是有身高的lg(n)确切地。

寻找例如斐波那契树 http://lcm.csa.iisc.ernet.in/dsa/node112.html, which is平衡树（实际上是最坏的情况AVL tree http://en.wikipedia.org/wiki/AVL_tree）。然而 - 它的高度更大lgn (~1.44*lg(n)），并且建议的算法将返回不平衡的斐波那契树。