3

ここに画像の説明を入力してください

ツリーには、上記の画像のように、親ノードが常に子よりも小さくなければならないという不変条件があります。ここで、ノードのキーの一部が変更されて不変性が破られ、不変性を維持したいとします。基本的には、親ノードのすべての子をコンペア・アンド・スワップすると思いますが、ツリーをトラバースするための再帰を作成する方法がわかりません。以前に学んだ二分木とは違うようです...

ところで、各ノードにはインデックスはありませんが、親、leftChild、rightSiblingの3つのポインターしかありません。ノードがルートの場合、その親はNULLを指します。ノードが右端のノードである場合、そのrightSiblingはNULLを指します...誰かがこれに光を当てることができますか？事前にThx！

4

1 に答える 1

1

手始めに、この多分木を二分木として表現することは、左子/右兄弟表現と呼ばれ、通常の多分木表現といくつかのトレードオフがあります。この古い質問/回答は、これらの木を再帰的にトラバースする方法についての背景を与える可能性があります。

あなたの質問に関して：ノードの値が変化することには2つの可能な結果があります：

  • ノードの値が下がった場合は、その値が親より小さくなくなるまで、ノードを上にスワップする必要がある場合があります。
  • ノードの値が上がった場合、値がその子のいずれよりも大きくなくなるまで、ノードを最小の子と交換する必要がある場合があります。

この再帰を記述する1つの方法は、ツリーを2つのパスで処理し、各パスでこれら2つのケースのいずれかをチェックすることです。これらのパスを組み合わせることができないという根本的な理由はありませんが、説明を簡単にするために、それぞれを個別に扱います。

最初のケースでは、値が減少したため、ノードをその親ノードと交換する必要がある場合があります。その場合、最初にすべての子ノードを処理し、次にノード自体を処理する、ある種のツリートラバーサルをシミュレートする必要があります。そうすれば、値を多くのレベルでルートにスワップアップする必要がある場合、ルートを越えずに可能な限り最高のレベルに再帰的に上げてから、もう1つのレベルに昇格させることができます。標準のマルチウェイツリーがある場合、再帰は次のようになります。

void FixTreeUpward(TreeNode curr) {
    /* If the current node is null, we're done. */
    if (curr == null) return;

    /* Process each child. */
    for (TreeNode child that is a child of curr) {
        FixTreeUpwardRec(child);
    }

    /* If we need to swap values with our parent, do so here. */
    if (curr.parent != null && curr.value < curr.parent.value) {
        swap(curr.value, parent.value);
    }
}

多元ツリーの左子、右兄弟の表現を使用しているため、中央のforループは少し奇妙に見えます。最初に左の子に降りてから、ノードがなくなるまで右に進みます。擬似コードの場合：

void FixTreeUpward(TreeNode curr) {
    /* If the current node is null, we're done. */
    if (curr == null) return;

    /* Process each child. */
    for (TreeNode child = curr.left; child != null; child = child.right) {
        FixTreeUpwardRec(child);
    }

    /* If we need to swap values with our parent, do so here. */
    if (curr.parent != null && curr.value < curr.parent.value) {
        swap(curr.value, parent.value);
    }
}

これですべてです。概念的には、再帰はそれほど難しくはありません。それについての唯一の奇妙な部分は、私たちがどのように子供たちを訪問するかです。

アルゴリズムの2番目の部分について考えてみましょう。ここでは、必要に応じてバブルダウンする必要があります。これを行うには、次のようにします。ノードごとに、そのすべての子を調べて、値が最小の子を見つけます。その値がルートノードの値よりも小さい場合は、ツリーのルートをその子と交換してから、繰り返します。疑似っぽいコードの場合：

void FixTreeDownward(TreeNode root) {
    /* If the root is null, we have nothing to do. */
    if (root == null) return;

    /* Find the smallest child. */
    TreeNode smallChild = (root's first child, or null if none exists);

    for (TreeNode child in the children of the root) {
        if (child.value < smallChild.value) {
            smallChild = child.value;
        }
    }

    /* If we have a smallest child and it's smaller than our value,
     * swap values and recursively repeat this.
     */
    if (smallChild != null && smallChild.value < root.value) {
        swap(smallChild.value, root.value);
        FixTreeDownward(smallChild);
    }
}

したがって、ここでの唯一の質問は、すべての子を反復処理することです。幸い、それはそれほど難しいことではありません。前と同じように、左側のサブツリーに降りて、ノードがなくなるまで右に進みます。これはここに示されています：

void FixTreeDownward(TreeNode root) {
    /* If the root is null, we have nothing to do. */
    if (root == null) return;

    /* Find the smallest child. */
    TreeNode smallChild = root.left;

    for (TreeNode child = root.left; child != null; child = child.right) {
        if (child.value < smallChild.value) {
            smallChild = child;
        }
    }

    /* If we have a smallest child and it's smaller than our value,
     * swap values and recursively repeat this.
     */
    if (smallChild != null && smallChild.value < root.value) {
        swap(smallChild.value, root.value);
        FixTreeDownward(smallChild);
    }
}

そして、私たちはすべて設定されている必要があります！

お役に立てれば！

于 2013-02-24T18:45:14.053 に答える