[Powered by Google Translate] どのようにコンピュータ内のすべてのあなたの家族のメンバーを表すでしょう？ 我々は、単に、リストを使用することができます しかし、明確な階層がここにあります。 

Let 'sは、我々はあなたの曾祖母、アリスから始めていると言う。 彼女はボブ、2人の息子がいます そしてあなたの祖父、チャーリー。 チャーリーは、3人の子供を持っている あなたの叔父、デイブ、あなたの叔母、イブ、とあなたの父、フレッド。 あなたは、フレッドの唯一の子である。 

なぜ、このようにあなたの家族のメンバーの編成であろう 単純なリスト表現よりも良くなる？ 一つの理由は、この階層構造、 いわゆる "木を、"単純なリストよりも多くの情報が含まれています。 我々は皆の間に家族関係を知る ただ木を調べることによって。 また、スピードアップすることができます ツリーデータがソートされている場合、途方もなく時間のルックアップ。 

私たちはここでそれを活用することはできませんが、我々はすぐにこのような例を見ることができます。 各人は、ツリー上のノードで表されます。 ノードが子ノードを持つことができます 同様に親ノードとして。 これらは、技術的な用語である 家族以外のもののために木を用いた場合であっても。 アリスのノードは、2人の子供と親のないを持っている チャーリーのノードは3人の子供と1親を持ちながら。 

リーフノードは子を持たないものである 木の外側の端に。 ツリーの最上位ノード、ルートノード、 親を持たない。 

バイナリツリーでは、ツリーの特定のタイプです その内の各ノードは、最大で2人の子供を持っています。 ここではC言語でバイナリツリーのノードの構造体は、 すべてのノードは、それに関連付けられているいくつかのデータを持って 他のノードへのポインタと2。 

私たちの家族のツリーで、 関連付けられているデータは、それぞれの人の名前だった。 それは何でもかまいませんけれども、ここでは、int型です。 それは結局のところ、 バイナリツリーは、家族のために良い表現ではない 人々は頻繁に2つ以上の子供を持っているので。 

二分探索木 バイナリツリーの特別な、秩序タイプです それは私達がすぐに値を見ることができます。 あなたは気づいているかもしれません そのツリーのルートの下のすべてのノード 別のツリーのルートは、 "サブツリー"と呼ばれます。 ここでは、ツリーのルートは、6です とその子、2は、サブツリーのルートです。 

二分探索木で ノードの右の部分木のすべての値 ノードの値よりも大きくなります。ここに：6。 さて、ノードの左の部分木の値 ノードの値未満です。 我々は、重複値を処理する必要がある場合は、 我々は、緩い不平等のいずれかにそれらの変更ができます 同一の値は、左または右のいずれかに落ちることができることを意味し、 限り、我々は全体で約一貫性があるように。 このツリーは、二分探索木である それは次のルールに従いますので。 

これは、我々はC言語の構造体にすべてのノードをオンにした場合、それがどのように見えるかです。 ていることに注意して子供が欠落している場合、 ポインタはnullになります。 どのように我々は7が木になっているかどうかをチェックしますか？ 私たちは、ルートから始まる。 セブンが6より大きいので、それがツリーになら、それは右にでなければなりません。 そして、それが8未満であるので、それは残さなければなりません。 ここでは、7を発見した。 今、我々は5のために確認してみます。 ファイブは、6未満であるので、左側にあることが必要です。 ファイブは、2より大きい ので、権利でなければなりません そしてそれはまた、4よりも大きいので、それは再び右にする必要があります。 しかし、ここには子がありません。 ポインタはnullになります。 これは5が私たちのツリーに含まれていないことを意味します。 

我々は、次のコードを使用してバイナリツリーを検索することができます： すべてのノードで、我々が発見したかどうかを確認してください 私たちが探している値。 我々はそれが見つからない場合は、それがあるべきならば、我々は判断 左または右に、そのサブツリーを確認してください。 このループは、木を切り倒していきます 左または右のどちらかには子ノードが存在しなくなるまで。 

5は木ではありませんでしたことを覚えておいてください。 どのように我々はそれを挿入しますか？ プロセスは、検索に似ています。 我々は、6から始まるツリーを下に反復する 2に残され、 4への権利、 そして再び右が、4は、この側には子がありません。 これは、5用の新しい位置となります そして、それは子供がいないと開始されます。 

どのくらいの速さ二分探索木の操作はありますか？ Bigohnotationが上限を提供しようとすることを覚えておいてください。 最悪の場合には、 私達の木は、単にリンクされたリストであってもかまいません その挿入、削除、および検索を意味 ツリー内のノード数に比例して時間がかかることがあります。 これはO（n）である。 

たとえば、以下は有効な二分探索木である。 しかし、我々は9の検索を試みると、 我々は、すべてのノードを横断しなければならない。 これは、リンクされたリストと大差ありません。 理想的には、我々は、すべてのノードが欲しい 2人の子供を持っている私たちの二分探索木の。 このように、挿入、削除、検索 、最悪の場合、O（log n）の時間がかかるだろう。 前からツリーは、よりバランスの取れたかもしれない このように。 さて、任意の値を検索することは、最大でも3つのステップをとります。 このツリーは、バランスが取れている 最小限の深さを持っている意味 ノード数に対して相対的。 

平衡二分探索木に値を探して ソートされた配列でバイナリ検索に似ています。 実際、私達が項目を挿入したり削除したりする必要がない場合は、 彼らはまったく同じように動作します。 しかし、ツリー構造が優れている 挿入と削除を処理するための 

私の名前はBannusファンデKlootです。 これはCS50です。