二叉搜索树是否平衡？

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

- vikky.rk

---

你似乎没有使用node，也不需要一个if()语句，你可以直接返回布尔值。否则，对于自平衡二叉搜索树而言，它看起来是正确的。http://en.wikipedia.org/wiki/Self-balancing_binary_search_tree - Peter Lawrey

是的，这段代码是从另一个函数复制过来的，然后添加了一个名为isBalanced的函数。这就是为什么我没有使用node的原因。 - vikky.rk

正如Amit所说，这将确定树是否具有最小平衡高度。它可能比这个高，但仍然是平衡的。 - Peter Lawrey

哦，我明白了，我对平衡树的定义是具有“最小高度”。因此，实际定义是“树中任何节点都应具有高度相同或相差1的子树”。 - vikky.rk

公平地说，对于一棵平衡树，最大高度始终大于log(n)。如果你有三个元素，那么你有两个元素，log(3) = 1.6，log(7) = 2.8（深度为3级）。你计算中加1的原因是什么？ - Maderas

Answer 1

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

请注意，只有一个完全二叉树的高度恰好为lg(n)。

例如，看看Fibonacci树，它是一棵平衡树（实际上是AVL树的最坏情况）。然而 - 它的高度大于lgn（~1.44*lg(n)），建议的算法将返回Fibonacci树不平衡。

- amit

---

该公式计算的是最小高度，而不是符号“>”所暗示的最大高度。保持高度始终为其最小值floor(log_2(n))并不总是可行的。可以证明，任何这样做的插入算法都会有过多的开销。因此，大多数自平衡BST算法将高度保持在这个下界的常数因子内。-- 来自维基页面。 - Peter Lawrey

@PeterLawrey: 仍然，最小高度比 log_2(n) 大。floor(log_2(n)) 不总是可行的 - 必须保持一个常数因子，但这个常数绝对不是1。我仍然无法理解你想要表达的意思。即使平衡二叉树大于 lg_2(n)，它也可以保持平衡 - 这就是我想要展示的。由于斐波那契树是 AVL 树的一种特定类型，它是一个高度大于 lg_2(n) 的平衡二叉树的可行示例，并且仍然保持平衡。 - amit

是的，我在谈论二叉搜索树。 - vikky.rk

@amit：我对平衡树的定义是具有“最小高度”。因此，实际定义是“树中任何节点都应具有具有相同高度或高度差为1的子树”。 - vikky.rk

那么要检查一棵二叉搜索树是否平衡，您是否使用与检查二叉树是否平衡相同的方法？还是有针对BST的优化？ - bytefire