KEVINシュミット：時々、ビルドするとき このプログラムは、あなたが利用することをお勧めします 辞書として知られているデータ構造。 ある辞書のマップキー、 通常の値に、文字列、整数、 文字、いくつかのオブジェクトへのポインタ、 我々は好き。 それは、普通の辞書のようなものだ 定義を通じてそのマップは言葉。 

辞書はを提供してくれる 情報を記憶する能力 何かに関連付けられている 後でそれを検索します。 では、どのように実際に実装するのですか Cコード、たとえば、辞書たちができる 私たちのプログラムのいずれかで使うのか？ まあ、それの方法はたくさんあり​​ます 私たちは辞書を実装することができます。 

1のために、我々は我々の配列を使用することができます 動的に再サイズや、我々は使用することができます リンクリスト、ハッシュテーブル またはバイナリツリー。 しかし、我々は選択したものは何でも、私たちはすべき 効率に留意し、 実装のパフォーマンス。 我々は、使用されるアルゴリズムを考える必要があります に項目を挿入して、ルックアップする 私たちのデータ構造。 

ここでは、のは、その私たちを想定してみましょう キーとして文字列を使用したいと思います。 それでは一つの可能​​性についてお話しましょう​​、 データ構造は、トライと呼ばれる。 だからここに視覚的な表現です トライの。 

写真は、トライを示唆しているように とツリーデータ構造である 互いにリンクされたノード。 我々はルートが明確があることを参照してください。 に至るいくつかのリンクを持つノード 他のノード。 しかし、各ノードは、で構成されていますか？ 私たちは鍵を格納していると仮定した場合 英字のみとし、 私たちは、大文字と小文字を気にしない、 ここに、そのノードの定義を示します 十分です。 

型が構造体であるオブジェクト ノードには2つの部分があります データや子供たちを呼んだ。 私たちは、コメントとしてデータ部分を残してきた 成分によって置換される 構造ノードである宣言 Cプログラムに組み込ま。 ノードのデータ部分は次のようになります。 かどうかを示すブール値 いないノードが完了したことを表している 辞書のキーのまたはそれはあるかもしれない 定義を表す文字列 辞書内の単語の。 

我々は示すためにスマイリーフェイスを使用します データは、ノード内に存在する場合。 私たちの中の26の要素があります。 子配列、1インデックス 英字あたり。 私たちは、意義が表示されます すぐにこのの。 

のルートノードを詳しく見ていきましょう データがない私たちの図に で示されるように、それに関連付けられた 中スマイリーフェイスの欠如 データ部。 の部分から延びる矢印 子配列は、非ノードを表す 他のノードへのポインタ。 例えば、矢印は、から延びる 子供の二番目の要素 手紙Bを表し、 辞書のキーにある。 より大きな図中の 我々はBでラベルを付け 

より大きな図では、ときに我々に注意してください 別のノードへのポインタを描き、それ どこ矢じりは関係ありません そのほかのノードを満たしています。 このサンプル辞書トライは含まれています 二つの言葉は、そのズーム。 それではの例を見てみましょう キーのデータを検索する。 

我々が見ていたとします キー風呂の値を対応する。 私たちは、ルックアップを始めましょう ルートノードた。 その後、我々は我々の最初の文字を取るよ 、鍵B、および対応を見つける 私たちの子供たち配列内のスポット。 正確に26のスポットがあることに注意してください 配列の各文字のための1中 アルファベット。 そして、我々は斑点が表す必要があります 順にアルファベットの文字。 

私たちは、2番目のインデックスを見てみましょう 一般的にはBのインデックス1、我々の場合 いくつかのアルファベット文字C、我々が持っている 対応するスポットを決定することができる 使用して子配列内の このような計算。 私たちは、より大きな子を使用することもできます 我々は、ルックアップを提供したい場合は、アレイ 文字の広い範囲でキー、 このような全体としての ASCII文字セット。 

この場合、ポインタ で私達の子供·アレイ内の インデックス1はNULLではありません。 だから我々は見続けます キー風呂上り。 我々はこれまでに、nullポインタが発生した場合 子供の適切な箇所に 配列我々はノードを横断しながら、 その後、我々はその我々が言うことがあるでしょう そのキーの何かを見つけることができませんでした。 

今、私たちは第二の手紙を取るよ 当社の主要A、および以下継続 私たちまで、このように、ポインタ 当社の主要の最後に到達する。 私たちはせずに、キーの最後に到達した場合 任意の行き止まり、ヌルポインタを打つ、 我々だけにして、ここではそうであるように もう一つのことをチェックする必要があります。 このキーは、実際には 辞書内の？ 

もしそうなら、我々はAだけでなく、値を見つける必要があります 私たちの図中のスマイリーフェイスアイコンを場所 言葉は終了します。 何か他のものがあった場合に格納されている データは、その後、我々はそれを返すことができます。 例えば、キー動物園ではありません 我々が持っている可能性にもかかわらず、辞書、 これまでにすることなく、このキーの終わりに達し 我ながら、NULLポインタを打つ トライを反復。 

我々は主要なお風呂を検索しようとすると、 第二の最後のノードの配列インデックスに、 、文字Hになり、対応する NULLポインタを開催しています。 だから、お風呂は辞書にありません。 だからトライは、キーという点で独特である 明示的に保存されることはありません データ構造。 では、どのように何かを挿入しない トライへ？ 

キーを挿入してみましょう 私たちのトライに動物園があります。 覚えておいて、そのノードのスマイリーフェイス 簡単な、コードに対応することができる その動物園を示すブール値 辞書にあるか、それができた 我々より多くの情報に対応 キー動物園に関連付ける、 の定義のような 単語または何か他のもの。 ある意味では、プロセスは、挿入する トライへ何かに似ている トライで何かを調べる。 

我々は再びルートノードから始めましょう、 に対応する次のポインタ 当社の主要の手紙。 幸いなことに、我々はポインタをたどることができました 私たちに達するまで、すべての道 キーの最後。 動物園は、単語の接頭語であるため、 のメンバーである、ズーム、 辞書には、我々はする必要はありません 任意の新しいノードを割り当てます。 

我々はそれを示すためにノードを変更することができます につながる文字のパス それが私たちの辞書内のキーを表します。 それでは、挿入してみましょう トライにキーBATH。 私たちは、ルート·ノードから開始します そして、再びポインタに従ってください。 しかし、このような状況では、我々は死者を打つ 我々が得ることができるしている前に終了 キーの最後。 今、我々はいくつかの新しいを割り当てる必要があります ノードは、新しいものを割り当てる必要があります 残りの各ノードのための 当社の主要の手紙。 

この場合、我々だけが必要 1新しいノードを割り当てます。 その後、我々は、H·インデックスを作成する必要があります この新しいノードを参照。 もう一度、我々は、ノードを変更することができます 文字のパスを示している それにつながることを表す 私たちのディクショナリのキー。 漸近約レッツ理由 これらのための私たちの手続きの複雑さ 2事業。 

我々は両方のケースで数いることがわかり 我々のアルゴリズムがかかった手順 の数に比例 キーワードの文字。 そう。 あなたが単語を検索したいとき あなただけを反復処理する必要がトライ 文字1つずつ必要になるまでのどちらか 単語の最後に到達するか、 トライで行き止まりにヒット。 

そして、あなたはキーを挿入したいとき 使用してトライへと値のペア 我々は議論の手順、最悪の場合 新しいノードを割り当てる必要があります 各文字。 そして、我々はその割り当てを仮定します 一定時間操作があ​​る。 我々は、キーの長さであると仮定しそうである場合 固定された定数の両方で囲まれた 挿入と見上げる一定である トライの時間操作。 

私たちは、この仮定をしない場合は、その キーの長さは固定で囲まれ 定数は、挿入と見上げる、 最悪の場合には、線形である キーの長さ。 項目の数が格納されていることに注意してください トライでルックアップには影響しません または挿入時間。 それが唯一の影響を受けているの キーの長さ。 

これとは対照的に、たとえば、にエントリを追加する ハッシュテーブルは作成する傾向がある 未来が遅く調べる。 これは、最初は魅力的に聞こえるかもしれないが、 我々は心に留めておくべきこと 有利な漸近的複雑さはない 実際には、データをその意味 構造は必然である 非難を超えた。 我々はまた、保存するためにそれを考慮する必要があります 我々が必要とトライ中の単語、最悪の中 ケース、ノード数に比例 単語自体の長さに。 

試みは、多くのスペースを使用する傾向がある。 すなわち、ハッシュテーブルとは対照的だ 私たちは、1つの新しいノードを必要な場所 いくつかのキーと値のペアを格納します。 今、再び理論的には、大きなスペース 消費量が大きいように見えるしていません 特に現代のことを考えると契約、 コンピュータはギガバイトを持っており、 メモリのギガバイト。 しかし、それは、我々はまだ持っていることが判明 メモリ使用量を気にすると のための組織 現代のコンピュータからパフォーマンス、 下の場所でのメカニズムを持っている メモリアクセスを高速化するフード。 

しかし、これらのメカニズムは、最高のときに動作 メモリアクセスはコンパクトに作られてい 領域または地域。 とトライのノードが存在する可能性が そのヒープ内の任意の場所。 しかし、これらはトレードオフである 我々は考慮しなければならないこと。 

データを選択する際に、以下のことを覚えている 特定のタスクのための構造、私たち どのような考えなければならない 操作は、データ構造は、必要に サポートとどのくらいの性能 それらの各々の 操作は、私たちにとって重要。 これらの操作でもよい ちょうど超えて拡張 基本的なルックアップおよび挿入。 我々は親切を実装したいとし オートコンプリート機能は、多くの Googleのように検索エンジンがありません。 つまり、すべてのキーを返し、 潜在的にどの値 指定された接頭辞が付いています。 

トライは一意に便利です この動作を行います。 これは、反復処理するために簡単です 各文字のためのトライ 接頭辞。 ただ見上げる動作と同様に、 私たちは、ポインタをたどることができ 文字単位。 その後、我々は最後に到着したとき 接頭辞は、反復処理ができ データ構造の残りの部分 キーのいずれかを超えて以来、 この点は、接頭辞を持っている。 

それは、このリストを得ることも簡単です 以来、アルファベット順に 子配列の要素 アルファベット順に並べられます。 だから、うまくいけば、検討します 寄付は、トライをしようとします。 私はケビン·シュミットだし、これはCS50である。 

ああ、これが始まりです 衰退。 ごめんなさい。 申し訳ありません。 申し訳ありません。 申し訳ありません。 

ストライク4。 私は思います。 申し訳ありません。 申し訳ありません。 申し訳ありません。 誰が人を作るために残念 これは夢中に編集することがあります。 

申し訳ありません。 申し訳ありません。 申し訳ありません。 申し訳ありません。 

スピーカ1：よくやった。 それは本当によく行われていた。