3

これはすでにここで議論されていますが、私は以下の実装を持っています (これはスレッドでは決して議論されませんでした),

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 はツリー内の要素の数です。これは正しい解決策ですか？

4

1 に答える 1

6

この解決策は正しくありません。バランスのとれたツリーは、その高さが の場合にバランスが取れているO(lg(n))ため、それ (高さ) をそれよりも小さくする必要がありますc*lg(n)- 一部の CONSTANT の場合c。ソリューションでは、この定数が 1 であると想定しています。

完全なツリーlg(n)のみが正確な高さであることに注意してください。

たとえば、バランスのとれたツリーであるフィボナッチ ツリーを見てください (実際には、 AVL ツリーの最悪のケースです)。ただし、その高さは( ) よりも大きく、提案されたアルゴリズムはフィボナッチ ツリーがバランスされていないことを返します。lgn~1.44*lg(n)

于 2012-08-23T08:52:00.830 に答える