是二叉搜索树平衡？ [英] Is Binary Search tree balanced?

问题描述

这已经讨论过了<一href="http://stackoverflow.com/questions/742844/how-to-determine-if-binary-tree-is-balanced">here,但我有以下的实现（这是从来没有在线程讨论），

This has already been discussed here, but I have an implementation below (which was never discussed in the thread),

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

where maxHeight() returns the maximum height of the tree. Basically I am checking if maxHeight > log(n), where n is the number of elements in the tree. Is this a correct solution?

推荐答案

这个解决方案是不正确的。平衡树是平衡的，如果它的高度是 O（LG（N）），从而（高度）需要更小的话 C * LG （N） - 对于某一常数 C 。您的解决方案假定该常数为1。

This solution is not correct. A balanced tree is balanced if its height is O(lg(n)), thus it (the height) needs to be smaller then c*lg(n) - for some CONSTANT c. Your solution assumes this constant is 1.

请注意，只有完整的树是高度 LG（N）完全

Note that only a complete tree is of height lg(n) exactly.

查找例如在斐波那契树，其中的是的平衡树（和实际上是最坏的情况下对一个 AVL树的）。但是 - 它的高度是再大 LGN （〜1.44 * LG（N）），和建议的算法将返回斐波那契树的不均衡。

Look for example on a Fibonacci tree, which is a balanced tree (and is actually the worst case for an AVL tree). However - its height is larger then lgn (~1.44*lg(n)), and the suggested algorithm will return a fibonacci tree is not balanced.

这篇关于是二叉搜索树平衡？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！