java - 再帰的二分探索木トリミング.. x=change(x)

Question

これは私のコードがすべきことです:

問題は、メソッドを作成することを要求し、パラメーターとして最小および最大の整数を受け入れ、その範囲内にない要素をツリーから削除します。

最初に書いたコードは

public void trim (int min, int max) {
    overallRoot = trim (overallRoot, min, max);
}

private IntTreeNode trim (IntTreeNode root, int min, int max) {
    if (root != null) {
        if(root.data < min && root.data > max) {
            root = null;
        }else {
            root.left = trim(root.left, min, max);
            root.right = trim (root.right, min, max);
        }
    } 
    return root;
}

私のコードはツリーを再構築しないため、少し検索しましたが、次のコードが見つかりました。

private IntTreeNode trim (IntTreeNode root, int min, int max) {
    if (root == null) {
        return root;
    }
    root.left = trim(root.left, min, max);
    root.right = trim (root.right, min, max);
    if(root.data < max && root.data> min) {
        return root;
    }else if (root.data < min) {
        return root.right;
    }else if (node.data > max) {
        return root.left;
    }
}

returnステートメントがないため、コードはコンパイルされません。そのため、elseに変更すると、場合によってのみ機能します。上記のコードはある程度理解できますが、あまり直感的に書かれていませんが、繰り返しになりますが...再帰はあまり直感的ではありません。私の教授が言うように、「信仰を飛躍させてください」。どんな助けでも大歓迎です:)私の最終的にうまくやろうとしています

Answer 1

コードの問題は、ルート ノードが間隔の外側にある場合でも、その子がそうである必要はないにもかかわらず、サブツリー全体を削除することです。

見つかったコードは、最初にサブツリーをトリミングしてからルート ノードを調べることで、これに対処しています。の左側にある場合はmin、ルート ノードとその左側のサブツリーの両方を削除する必要があり、右側のサブツリー (既にトリミングされている) が残ります。同様に、ルートが の右にある場合maxは、右のサブツリーも同様であり、(既にトリミングされた) 左のサブツリーを残す必要があります。これはツリー全体を訪問するため、あまり効率的ではありません。

簡単な改善は、使用する予定のサブツリーのみを訪問します。

private IntTreeNode trim (IntTreeNode root, int min, int max) {
    if (root == null) {
        return root;
    }
    if(root.data < max && root.data> min) {
        root.left = trim(root.left, min, max);
        root.right = trim (root.right, min, max);
        return root;
    }else if (root.data < min) {
        return trim (root.right, min, max);
    }else if (node.data > max) {
        return trim(root.left, min, max);
    }
}

ただし、[min, max] 内のすべてのノードに再アクセスするため、これはまだ最適ではありません。

おそらく最良の方法は、トリミングを 2 つのステップで行うことです。最初にすべてのノード < min をトリミングし、次にすべてのノード > max をトリミングします。

IntTreeNode trimLeft(IntTreeNode root, int min) {
    if (root == null {
        return null;
    } else if (root.data < min) {
        return trimLeft(root.right, min);
    } else {
        root.left = trimLeft(root.left, min);
        return root;
    }
}

このアプローチには、 および へのパス上のノードのみを訪問するという利点がminありmaxます。探索木のバランスがとれている場合、これは O(log n) になります。

選択したアプローチに関係なく、エッジケースで何が起こるかを正しく定義する必要がありroot.data == minますroot.data == max(元のコードと見つけたコードの両方がこれを間違っています)。

Answer 2

これは、この問題をグーグルで検索することになる将来の人々のために、すべてのケースで機能するコードです。

public void trim (int min, int max) {
    overallRoot = trim (overallRoot, min, max);
}

private IntTreeNode trim (IntTreeNode root, int min, int max) {
    if (root == null) {
        return root;
    }
    if(root.data <= max && root.data>= min) {
        root.left = trim(root.left, min, max);
        root.right = trim (root.right, min, max);
        return root;
    }else if (root.data < min) {
        return trim (root.right, min, max);
    }else if (root.data > max) {
        return trim(root.left, min, max);
    }else{
        return root;
    }
}

Answer 3

コードが再帰のすべてのケースをカバーしていることを確認する必要があります。

private IntTreeNode trim (IntTreeNode root, int min, int max) {
    if (root == null) {
        return root;
    }
    root.left = trim(root.left, min, max);
    root.right = trim (root.right, min, max);
    if(root.data < max && root.data> min) {
        return root;
    }else if (root.data < min) {
        return root.right;
    }else if (node.data > max) {
        return root.left;
    }
}

それでは、チェックしているものをリストしましょう。

• ルートはヌルです
• 最小値 < 現在値 < 最大値
• 現在の値 < 最小
• 最大 < 現在の値

current value == minとcurrent value == maxケースをカバーしていません！包括的な範囲をチェックする必要があると言いました。つまり、 でmin < current value < maxあるべきmin ≤ current value ≤ maxですよね？それで直ると思います。

しかし、あなたが言ったように、コードはあまり読みにくいです。私はそれを少し変更します：

private IntTreeNode trim (IntTreeNode root, int min, int max) {
    // Base case: leaves' children are null
    if (root == null)
        return root;
    // Case: current value too small - use trimmed right subtree
    if (root.data < min)
        return trim(root.right, min, max);
    // Case: current value too large - use trimmed left subtree
    else if (node.data > max)
        return trim(root.left, min, max);
    // Case: current value in range - trim both subtrees
    else if (min <= root.data && root.data <= max) {
        root.left = trim(root.left, min, max);
        root.right = trim (root.right, min, max);
        return root;
    }
    // Make sure we've covered all the cases
    // (this should be unreachable if our cases are complete)
    throw new RuntimeException("Unhandled case in trim!");
}

trimトリミングしてしまうサブツリーを呼び出さないため、これは少し効率的です。最後のケースでの呼び出しを繰り返すことで、ほんの少しのコードを複製しtrimましたが、これに問題を感じる人もいるかもしれませんが、個人的には問題ないと思います。

(注: 私はこのコードを実際にテストしていないので、構文エラーがあり、コンパイルさえされていない可能性がありますが、これがどのように機能するかについてのアイデアが得られるはずです。)

---

あなたのコメントに応えて：

throwメソッドの最後に句を追加したので、コードはすぐに実行されるはずです。

あなたのコードの句は、基本的に 2 番目のバージョンif (root != null)の場合と同じです。if (root == null) return root;

if (root.data < max && root.data > min)値がmin から max exclusiveの範囲内にあるかどうかをチェックしています。

したがって、現在のノードの値が最小値と最大値の間にない場合、サブツリー全体を破棄しています。正しいサブツリーのみを破棄し、包括的なチェックを行うようにコードを修正する必要があります。

---

余談if (min <= root.data && root.data <= max)ですが、より伝統的な数学の定義で書き出すものに似ているため、あなたが持っているものよりもはるかに読みやすいと思います: min ≤ root.data ≤ max. 私の意見では、不等号を同じ方向に向けておくのはいいことです。

Answer 4

public void trim(int min, int max) {
    overallRoot = trim(overallRoot, min, max);
}

private IntTreeNode trim(IntTreeNode root, int min, int max) {
    if (root != null) {
        root.left = trim(root.left, min, max);
        root.right = trim (root.right, min, max);
        if (root.data < min) {
            return root.right;
        } else if (root.data > max) {
            return root.left;
        }
    }
    return root;
}

かなり直感的です。バイナリ ツリーは、左側の値が常にルートの値以下であり、右側の値が常に大きくなるように構築されているため、root.data が最小値より小さい場合は、右側を返します。枝 (これは常に root.data よりも大きくなります) であり、root.data が指定された最大値よりも大きい場合は、左の枝 (常に小さいか等しい) を返します。再帰を使用してツリー全体をトリミングします (バイナリ ツリーは左右の 2 つの側面で構成されます): trim(root.left, min, max) trim(root.right, min max)。そして、ルートを返して、指定された最小値と最大値 (両端を含む) 内の値のみを持つツリーを与えるoverallRoot を置き換えます。

より包括的な構造:

public void trim(int min, int max) {
    overallRoot = trim(overallRoot, min, max);
}

private IntTreeNode trim(IntTreeNode root, int min, int max) {
    if (root != null) {
        if (root.data < min) {
            root = trim(root.right, min, max);
        } else if (root.data > max) {
            root = trim(root.left, min, max);
        } else {
            root.left  = trim(root.left,  min, max);
            root.right = trim(root.right, min, max);
        }
    }
    return root;
}