java - 二叉搜索树是否平衡？

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)- 对于一些 CONSTANT c。您的解决方案假定此常数为 1。

请注意，只有一棵完整的树lg(n)具有精确的高度。

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