0

二分木が平衡しているかどうかを確認します。

CTCI 5th のソースコード:

public class QuestionBrute {

public static int getHeight(TreeNode root) {
    if (root == null) {
        return 0;
    }
    return Math.max(getHeight(root.left), getHeight(root.right)) + 1;
}

public static boolean isBalanced(TreeNode root) {
    if (root == null) {
        return true;
    }
    int heightDiff = getHeight(root.left) - getHeight(root.right);
    if (Math.abs(heightDiff) > 1) {
        return false;
    }
    else {
        return isBalanced(root.left) && isBalanced(root.right);
    }
}

public static void main(String[] args) {
    // Create balanced tree
    int[] array = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    TreeNode root = TreeNode.createMinimalBST(array);
    System.out.println("Root? " + root.data);
    System.out.println("Is balanced? " + isBalanced(root));

    // Could be balanced, actually, but it's very unlikely...
    TreeNode unbalanced = new TreeNode(10);
    for (int i = 0; i < 10; i++) {
        unbalanced.insertInOrder(AssortedMethods.randomIntInRange(0, 100));
    }
    System.out.println("Root? " + unbalanced.data);
    System.out.println("Is balanced? " + isBalanced(unbalanced));
}
}

アルゴリズムはすべてのノードの高さをチェックする必要があり、各再帰で高さを保存しないため、実行時間は O(N^2) になります。

4

1 に答える 1

4

まず、コードを少し修正しましょう。次の場合、バイナリツリーのバランスが取れているという理由だけで、ルートのバランスが取れているかどうかをチェックする関数は機能しません。

maxHeight(root) - minHeight(root) <= 1

ウィキペディアを引用します。「平衡二分木は一般に、すべてのノードの2つのサブツリーの深さが1以下異なる二分木として定義されます。」

あなたのアルゴリズムはこのツリーに対して間違った答えを与えるでしょう：

サイズ9、高さ3の単純な二分木で、ルートノードの値は2です。上記のツリーは不均衡であり、並べ替えられていません。

電話をかけるgetHeight(Node7)と3が返され、電話をかけるgetHeight(Node5)と3も返されます(0>1) == false。true

これを修正するにはint MinHeight(TreeNode node)、同じ方法で実装するgetHeight()だけです。Math.min()

今あなたの答えに。getHeight()ルートから関数を呼び出すときは常に実行時の複雑さの観点から、 DFSを実行しており、ツリーの高さを見つけるためにすべてのノードにアクセスする必要があるため、このアルゴリズムはO（N）になります。これで、このアルゴリズムを呼び出すときに2回実行するのは事実ですmaxHeight(root)がminHeight(root)、両方ともO（N）であるため（正確に実行する場合getHeight()）、全体的な複雑さは、一定のCおよびすべての上限としてC*Nになります。いくつかのNノットよりも大きいN、つまりO（N）ここで、Nはツリーのノードの数です;）

乾杯！

于 2013-01-30T05:08:48.853 に答える