[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です。