1

「Cracking the Coding Interview」から次の問題を解決しています: 二分木のバランスが取れているかどうかをチェックする関数を実装します。バランスの取れたツリーとは、ノードの 2 つのサブツリーの高さの差が 1 を超えないようなツリーです。

本のサンプル ソリューション (以下にコピー) では、(a) ノードの左と右のサブツリーのバランスが取れている場合、ノードから発するツリーのバランスが取れていると想定しています。(b) ノード自体のバランスがとれている。なぜこれが事実なのか理解しようとしていますか？上記の 2 つの条件が満たされていることは、ノードから発するツリー全体のバランスが取れていることをどのように証明しますか?

ありがとう

public static boolean isBalanced(TreeNode root)
{
    if (checkHeight(root)==-1)
        return false;
    return true;
}


public static int checkHeight(TreeNode root)
{
    //base case
    if (root == null)
        return 0;

    //is left subtree balanced
    int leftHeight = checkHeight(root.leftChild);

    if (leftHeight == -1)
        return -1;

    //is right subtree balanced
    int rightHeight = checkHeight(root.rightChild);

    if (rightHeight == -1)
        return -1;

    //is current node balanced
    int heightDiff = leftHeight - rightHeight;

    if (Math.abs(heightDiff) > 1)
        return -1;

    return (Math.max(leftHeight, rightHeight) + 1);
}
4

3 に答える 3

0

バランスの取れた二分木とは、左右のサブツリーの深さの合計の差が 1 を超えないものです[1]。ここで提示されたソリューションは再帰的であり、最初に子自体がバランスが取れているかどうかを確認し、次に親がバランスが取れているかどうかを確認します。これは、子の左と右のサブツリーの深さをチェックすることによって行われ、それらの間の深さが最大 ​​1 だけ異なる場合は、 を返しますmax(left_depth,right_depth)+1。そうでない場合は、 を返します-1。次に、アルゴリズムはツリー全体でこれを続けます。任意の時点で深さが -1 の場合 (子のバランスが取れていないことを示します)、サブツリー全体の深さは -1 として返されます。最後に、ツリーの深さの合計が -1 であるかどうかを確認します。そうであれば、ツリーはバランスが取れていません。

誘導の形式のアルゴリズムは次のとおりです。

  • 規範事例

    葉ノード - 自明にバランスが取れており、子はありません。深さには子の数 (0) とノード自体の両方が含まれるため、1 が返されます。

  • 誘導性の場合

    中間ノード。子のバランスが取れている場合にバランスが取れ、左の子の深さが右の子の深さと最大で 1 異なります。バランスが取れている場合max(left_depth,right_depth) + 1、ノード自体を含むツリーの合計の深さを表す を返します。 . バランスが取れていない場合は、単純に を返し-1ます。

  • ついに

    帰納的な場合と同様にチェックされるルート ノードですが、バランスがとれている場合は、ツリー全体がバランスが取れており、深さの合計はmax(left_depth,right_depth) + 1であり、とはルート ノードに対する左/右サブツリーの深さを表しますleft_depth。right_depth

BST のコーディングのいくつかの非常に興味深い側面をカバーする以前に尋ねられた SO の質問は、ここにあります。

于 2015-05-25T09:09:59.553 に答える
0

これは再帰の適用です。ルーチンは、チェック対象のノードの左右のサブツリーの高さを計算し、同時にサブツリーを再帰的に検証します。-1ノードのバランスが取れていない場合、またはサブツリーの高さが問題ない場合は戻ります。サブツリーの高さの比較により、現在のノードがバランスが取れているかどうかが決まります。

ところで、関数全体を に置き換えrootて、ルートだけでなく、ツリー内のすべてのノードにルーチンが再帰的に適用される方法を明確にします。currnodecheckHeight()

于 2015-05-25T09:15:16.937 に答える
0

あなたがそれを求めたので、ここで誘導についてもう少し:

https://en.wikipedia.org/wiki/Well-founded_relation

誘導について知っていることはすべて忘れてください。ここに本物があります。何らかの関係 R がある場合、x1 R x2、x2 R x3 などの無限に下降するチェーン x1、x2、x3、... がない場合にのみ、R は十分に根拠があると言われます。(「降順」は、人々が数字で < を考えているためです )

たとえば、< は自然数では十分に根拠がありますが、実数では根拠がありません。

十分に根拠のある関係で、あなたはそれを持っています

(すべての x の場合: (すべての y の場合: x R y -> P(y)) -> P(x)) <-> すべての x の場合: P(x)

つまり、すべての最小要素が wrt であることを示せば十分です。R はいくつかのプロパティを持ち、ある x よりも小さいすべての要素が P を満たす場合、x も P を満たすことを示します。

特殊なケースは、おそらくご存知の帰納法です。

(P(0) & for all n: P(n) -> P(n+1)) -> for all n: P(n) (ここでの根拠のある関係は後継関数です)

有限ツリーの場合、サブツリーの関係は (明らかに) 十分な根拠があるため、次のことができます (実際には推移閉包を使用して、証明を短くします。それでも十分な根拠があります)。

基本ケース: (葉、これらはサブツリー関係に関する最小限のものです) 0 の子を持つ葉は、自明にバランスが取れています。

帰納法: すべてのサブツリー (およびそのサブツリーなど) のバランスが取れており、ルート ノードのバランスが取れていると仮定すると、すべてのノードのバランスが取れており、バランスが崩れている可能性のあるノードは残っていません (ここで何をしたかを参照してください)。

バランスがとれているということはサブツリーがバランスが取れていることを意味することにも注意すれば、推移閉包を使わずにこれを行うことができたでしょう。次に、直接のサブツリーのバランスが取れていることは、それらのすべてのサブツリーも同様にバランスが取れていることを意味すると言え、私の証明に戻ります。

于 2015-06-24T19:52:22.453 に答える