[Powered by Google Translate] [バイナリサーチ] [パトリック·シュミット - ハーバード大学] [これはCS50です。 -  CS50.TV] 

私はあなたにアルファベット順にディズニーキャラクターの名前のリストを与えた場合 そして、ミッキーマウスを見つけておくようにお願いし どうやってこれをやって行くか？ 自明な方法の1つは、リストを先頭からスキャンすることであろう それはミッキーもよいかどうかを確認し、すべての名前を確認します。 しかし、あなたがアラジン、アリス、アリエルを読み取るなどのように、 あなたはすぐにリストの先頭から開始するのは良いアイデアではなかったことに気づくでしょう。 さて、多分あなたは、リストの最後から順番に作業を開始する必要があります。 今、あなたは、ターザン、スティッチ、白雪姫などをお読みください。 それでも、これはそれについて移動する最良の方法のように見えません。 

さて、あなたはこれをやって行くことができる別の方法は絞り込むしようとすることです あなたが見なければならないことが名前のリスト。 あなたは彼らがアルファベット順になっていることを知っているので、 あなただけのリストの中に名前が見てでした とミッキーマウスがこの名前の前か後かを確認してください。 2番目の列に姓を見てみる あなたは、ミッキーのためにMはジャスミンのJの後に来ることを認識したい ので、単にリストの最初の半分を無視すると思います。 あなたはおそらく最後の列の一番上を見てね それはラプンツェルで始まっていることを参照してください。 ミッキーはラプンツェルの前に来る、我々は同様に最後の列を無視することができますように見えます。 検索戦略を継続すると、すぐにわかるでしょうミッキー 名前の残りのリストの最初の半分になっている そして最後にミッキーはマーリンとミニーの間に隠れて見つける。 

あなただけの何をしたかは、基本的には二分探索であった。 この名前が示すように、それはバイナリの問題で、その探索戦略を実行します。 これはどういう意味ですか？ まあ、ソート項目のリストを指定して、バイナリ·サーチ·アルゴリズムは、バイナリ決定を行います -  左または右に、より大きいか、小さい、アルファベットの前か後か - 各ポイントで。 今、私たちは、この探索アルゴリズムと一緒に行く名前を持っていること、 別の例を見てみましょうが、ソート番号のリストとこの時間。 我々はソート番号の一覧の中では番号144を探していると言う。 前と同じように、私たちは途中での番号を見つける -  これは、この場合には13  - と144以上13以下であるかどうかを確認します。 それが13よりも明らかに大きいですので、我々は13以下であるすべてのものを無視することができます そして残りの半分だけに集中しています。 我々は今、左の項目の偶数を持っているので、 我々は単に真ん中に近い番号を選択します。 この場合、我々は55を選択します。 我々は同じように簡単に89を選択した可能性があります。 オーケー。繰り返しになりますが、144は55よりも大きいので、私たちは右に行く。 幸いにも私たちのために、次の中間数は、144です 私たちが探している1。 だからバイナリ検索を使って144を見つけるために、我々は唯一の3つのステップでそれを見つけることができるしている。 我々がここで線形検索を使用したならば、それは私たちに12の措置を講じていただろう。 実際のところ、以来、この検索方法は、項目の数を半分に それは、各ステップで見ており、それが探しているアイテムを見つける リスト内の項目数の約ログインチ 今、私たちは2つの例を見てきましたので、次に見てみましょう 二分探索を実装再帰関数のためのいくつかの擬似コード。 上から順番に、我々は4つの引数を取る関数を見つけなければならないことがわかります。 キー配列、最小値、および最大値。 キーは、前の例でそう144、我々が探しているものです。 配列は、我々が検索している番号のリストです。 minとmaxは最小位置と最大位置のインデックスです 我々は、現在見ている。 だから我々が開始すると、minがゼロになるとmaxは、配列の最大インデックスになります。 我々は、検索を絞り込むように、我々は最小値と最大値を更新します 我々はまだインチ探しているだけ範囲になるように 

の最初の興味深い部分にスキップしてみましょう。 まず最初にすることは、中間点を見つけることです 我々はまだ検討している配列のminとmaxの中間にあるインデックス。 その後、我々はその中間位置に配列の値を見てみ 我々が探している番号は、そのキーよりも小さい場合とを参照してください。 その位置の数が少ない場合は、 それはキーがその位置の左側にすべての数値よりも大きいことを意味します。 だから我々は、再びバイナリ検索機能を呼び出すことができます。 しかし、今回は半分だけを読むためにminとmaxパラメータを更新 それがより大きいか、または私達はただ見て値に等しくなります。 一方、キーが配列の現在の中点で数よりも少ない場合 我々は左に行くと大きいすべての数字を無視したい。 再び、我々はminとmaxの範囲で更新されたバイナリ·サーチが、今回を呼び出す ちょうど下半分を含めることができます。 配列内の現在の中点での値がどちらである場合 キーよりも小さいよりも大きい場合は、キーと等しくなければなりません。 したがって、私たちは、単に現在の中点インデックスを返すことができ、我々は完了です。 最後に、ここでは、このチェックは、その数は場合の例です。 我々が検索している数値の配列で、実際にはありません。 もし我々が探している範囲の最大インデックス 我々は行き過ぎだということ最低限、これまでより少なくなります。 番号は入力配列ではありませんでしたので、私たちは-1を返す それは何も見つからなかったことを示すため。 

このアルゴリズムのために働くことに気づいたかもしれません、 番号のリストがソートされています。 言い換えれば、我々は唯一の144はバイナリ検索を使って見つけることができます すべての数字は、最低から最高に順序付けられている場合。 これが事実でなかったら、我々は、各ステップでの数字の半分を除外することができないだろう。 だから我々は2つ​​のオプションがあります。 どちらか我々は、バイナリ検索を使用する前にソートされていないリストを取得し、それを並べ替えることができます あるいは、我々は我々はそれに数字を追加すると番号のリストがソートされていることを確認することができます。 そこで、代わりに私たちが検索する必要があり、ちょうどその時のソート、 なぜすべての回でソートされたリストを保持しない？ 

同時に可能にしながら、ソート番号のリストを維持するための一つの方法 このリストから数字を追加したり移動したりするための1 二分探索木と呼ばれるものを使用することです。 二分探索木では、3つのプロパティを持つデータ構造体です。 まず、任意のノードの左のサブツリーには、より少ない値のみを含む またはノードの値に等しい。 第二に、ノードの右の部分木のみよりも大きい値が含まれています またはノードの値に等しい。 そして最後に、両方のすべてのノードの左と右のサブツリー また、二分探索木である。 我々が以前使用したのと同じ数字で例を見てみましょう。 コンピュータサイエンスの木の前に見たことがない人のために、 私はコンピュータサイエンスの木が下向きに生えていることを伝えることから始めましょう。 はい、あなたが慣れている木とは異なり、 コンピュータサイエンスのツリーのルートは、一番上にある 葉は下部にあります。 それぞれの小さなボックスはノードと呼ばれ、ノードはエッジで互いに接続されている。 だから、このツリーのルートは、13という値を持つノードの値です これは、値5と34と2子ノードを持っています。 サブツリーは、ツリー全体の項を見ただけで形成されている木です。 

たとえば、ノード3の左側のサブツリーは、ノード0、1、2で作成されたツリーです。 だから、我々は二分探索木の性質に戻ってしまったら、 私たちは、ツリー内の各ノードは、すなわち、すべての3つの特性に適合していることがわかり 左の部分木のみ以下のノードの値に等しい値が含まれます。 すべてのノードの右側のサブツリー 唯一のより大きいか、またはノードの値に等しい値が含まれ、そして すべてのノードの左と右のサブツリー双方はまた、二分探索木である。 このツリーは異なって見えるが、これは有効な二分探索木である 数字の同じセットのため。 実際のところ、あなたが作成することができる多くの方法はいくつもあります これらの数値から有効な二分探索木。 さて、のは、我々が作成した最初のものに戻りましょう。 だから我々は、これらの木々に何ができるのでしょうか？ まあ、我々は非常に単純に、最小値と最大値を見つけることができます。 最小値は常に左に行くことによって見つけることができる 訪問することはありません以上のノードが存在するようになるまで。 逆に、最大のものを見つけるためには、単にちょうどたびに右にダウンした。 

最小値または最大値はありません他の番号を見つける 同様に簡単です。 私たちは番号89を探していると言う。 我々は、単に、各ノードの値を確認し、左または右に移動します ノードの値がより小さいか大きいかどうかに応じて、 私たちが探している1。 だから、13のルートから始まる、私たちは、89の方が大きいことがわかり それで我々は右に行く。 その後、我々は34のノードを見て、再び我々は右に行く。 89はまだ55を超えているので、我々は右に行く続ける。 次に、144の値を持つノードを思い付くと左に移動します。 驚くなかれ、89はすぐそこです。 

我々が行うことができますもう一つは、間順走査を行うことで、すべての番号をプリントアウトしています。 間順走査は、左のサブツリー内のすべてをプリントアウトすることを意味します ノード自体の印刷が続く をクリックし、右側のサブツリー内のすべてをプリントアウトが続く。 例えば、使用している私たちのお気に入りの二分探索木を取らせ とソート順に番号をプリントアウト。 我々は13のルートで開始しますが、13を出力する前に、我々は、プリントアウトする必要があります 左のサブツリー内のすべての。 だから我々は5に進みます。我々はまだ、私たちは一番左のノードが見つかるまでツリーに深くダウンに行かなければならない これはゼロです。 印刷のゼロの後、我々は最大1に戻って、アウトを印刷してください。 その後、我々は2である、右の部分木に移動し、そのアウトを印刷してください。 今、私たちがそのサブツリーで行われていること、 我々は、3に戻って上がると、それをプリントアウトすることができます。 バックアップし続け、我々は5を印刷し、次に8。 今、我々は全体の左側のサブツリーを完了していること、 我々は13をプリントアウトし、右の部分木の上で作業を開始することができます。 我々は34にダウンホップが、印刷前に34我々は、その左の部分木をプリントアウトする必要があります。 だから我々は21をプリントアウトしてから、我々は34をプリントアウトし、その右の部分木を訪問することを得る。 55に左のサブツリーを持っていないので、我々はそれをプリントアウトし、その右の部分木に進みます。 144は左の部分木が付いているので、我々は、144に続いて、89をプリントアウト 233そして最後に一番右のノード。 そこにそれを持って、すべての数字は、最下位から最上位へ順番にプリントアウトされます。 

木に何かを追加することなく、比較的簡単です。 我々がしなければならないすべては、我々は3二分探索木の性質に従っていることを確認している スペースがある場合、その値を挿入します。 Let 'sは、我々は7の値を挿入したいと言う。 7が13未満であるため、我々は左に行く。 しかし、それは5より大きいですので、我々は右へトラバース。 それは8,8がリーフノードであるよりも少ないですので、我々は8の左の子に7を追加します。 出来上がり！私たちは、二分探索木に番号を追加しました。 

我々は物事を追加することができます場合、我々はより良​​いだけでなく、物事を削除することができる。 残念なことに私たちのために、削除は、もう少し複雑です -  はるかが、ほんの少しだけではない。 我々が考慮しなければならない3つのシナリオがあります 二分探索木から要素を削除するとき。 まず、最も簡単な場合は、要素が葉ノードであるということです。 この場合において、我々は単にそれを削除すると、当社の事業に進んでください。 我々は、追加した7を削除したいと言う。 まあ、我々は単にそれを見つけ、それを取り外してから、それはそれだ。 ノードが1つだけの子供を持っている場合は、次の場合です。 ここでは、ノードを削除できますが、我々は最初のことを確認する必要があります 現在、親の残っているサブツリーを接続する 我々だけで削除されたノードの親に。 私たちは木から3を削除してみたいと思います。 私たちは、そのノードの子要素を取得し、ノードの親にそれを添付してください。 このケースでは、我々は今、5から1を装着している。 私たちが知っているので、これは、二分探索木の性質に応じて、問題なく動作 3の左のサブツリー内のすべてのものは、5未満であった。 今3のサブツリーが世話をされていることを、我々はそれを削除することができます。 3番目と最後のケースは、最も複雑です。 我々は、削除するノードが2人の子供を持っている場合、これはそうです。 これを行うためには、まず、次の最大値を持つノードを見つけなければならない 2を交換してから、問題のノードを削除します。 次の最大値を持つノードが2人の子供自体を持つことはできません注意してください その左の子は、次の最大のための良い候補になるでしょうから。 したがって、2人の子供を持つノードを削除すると、2つのノードのスワッピングにのぼる その後削除は2前述のルールの1によって処理されます。 たとえば、みましょう我々はルートノード、13を削除したいと言う。 まず最初にすることは私たちがツリー内で2番目に大きい値を見つけることです これは、この場合には、21です。 次に、13葉と21の中央のグループノードを作って、2つのノードを入れ替える。 今、私たちは単純に13を削除することができます。 

以前に触れたように、有効な二分探索木を作る方法はいくつもあります。 残念なことに私たちのために、いくつかは他よりも悪化している。 我々は二分探索木を構築するとき、例えば、何が起こるでしょう 数字のソートされたリストから？ すべての数字は、ちょうど各ステップで右に追加されます。 私たちは番号を検索したいときは、 我々は選択の余地はないが、各ステップで右を見て。 これがすべてでは線形探索よりも優れているわけではない。 我々はここでそれらをカバーしていませんが、より複雑な、他があります このようなことが起こらないことを確認してデータ構造。 しかし、これを避けるために行うことができます一つのシンプルなものです ただランダムにシャッフル入力値に。 それは偶然で、数値のシャッフルリストがソートされている可能性は非常に低いです。 この設定が行われた場合、カジノは長くのためのビジネスにとどまらないだろう。 

そこにそれがある。 これでバイナリ検索とバイナリ検索ツリーを知っている。 私はパトリック·シュミットだが、これはCS50です。 [CS50.TV] 自明な方法の1つからリストをスキャンすることであろう... [ビープ音] 項目の数...うん... [笑] 234の...ポストノード...キャーッ。 >>イェーイ！それがあった -