1

二分探索ツリーにない最小の正の ([0, INT_MAX)) (最大の整数) 値を見つける方法を見つけようとしています。ツリーにはすべて正の整数があります。私は木の左側を横断しようと考えていました。次に、構造体の値を作成します。最小値の場合struct { int data; bool found; };は戻ります。t/f

左側をトラバースすることでこれを行いました。ルート -> データ + 1 > 左 -> データの場合は、

左 -> データ + 1

、それ以外の場合は右に進みます。もし

ルート -> データ + 1 < 右 -> データ

、その後return root->data + 1。それ以外の場合、right が null でない場合は戻りroot->data or right->data、見つかった値は false になります。また、ツリーの最小値が 0 でない場合は、0 を返す必要があります。ただし、これが最善の方法であるかどうかはわかりません。

助けてくれてありがとう。

編集: 申し訳ありませんが、これを書いたのは昨夜、本当に疲れていたときでした。これをループ内で使用しているため、毎回配列に入れると時間がかかりすぎます。私は二分探索木を使用しているので、ループのたびに挿入と削除を 1 回だけ行うだけで済み、ツリーにない最小値を見つけるのに最小限の時間を費やすことができます。

4

2 に答える 2

4

実行できる手順は次のとおりです。

  • max_int型のサイズの配列を宣言し、boolすべての要素を で初期化しますfalse。

    bool found[max_int] = {}; //it initializes the array with false!
//assumming `max_int` is a constant expression.
//else you can use `std::vector<bool>` or `std::vector<char>`.

  • BFSやDFSなど、自分に合ったものを使用して、ツリーをトラバースします。ツリー内の値ごとvに、インデックスの配列を次のように更新しますv。

    found[v] = true; //it means value `v` is found in the tree!

終わったら。最も低いインデックスは、探している値iですfound[i]。falseつまりi、ツリーにない最小値です。

二分木と二分探索木には違いがあることに注意してください。私の解決策はバイナリ ツリーに適用されますが、バイナリ サーチ ツリーでも機能します。バイナリ検索ツリーの場合、より最適なソリューションを見つけることができます。たとえば、トラバース中に、より大きな値を持つブランチを無視できます。あなたがそれを自分でできることを願っています。

于 2013-01-28T07:07:54.153 に答える
3

ツリーに重複する値が含まれていないと仮定すると、ツリーの順序どおりの走査を実行できます。最初に訪問したノードの期待値は0です。後続の各訪問済みノードの期待値は、最後に訪問したノードより1つ大きくなります。期待値とは異なるノードに遭遇した場合、期待値はクエリに対する答えです。

あなたがトラバーサルを説明した方法のために、あなたのツリーが順序付けられていると思います。ツリーが順序付けられていない場合は、各ノードにアクセスして回答を決定する必要がありますが、ツリー内のノードの数よりも大きい値は無視してかまいません。

上記はBSTの線形ソリューションを提供しますが、構造をさらに活用して、平均して対数ソリューションを取得できます。左ノードと右ノードが真のサブツリーであると仮定すると、アルゴリズムは次のようになります。

MinMissingValue(BST t, integer b = 0):
    if (t is empty) return b;
    if (t.root.value - b) > t.root.left.count
        return MinMissingValue(t.root.left, b)
    else
        return MinMissingValue(t.root.right, t.root.value + 1)

アルゴリズムは、各サブツリーが含まれるノードの数を知っているという概念に依存しています。

于 2013-01-28T07:10:50.983 に答える