[音楽再生] DOUG LLOYD：だから我々は近いインチングされてきました そして、近いそのデータの聖杯 構造、我々は挿入することができます1 から、削除、およびルックアップ 一定の時間です。 右。 それが目標のようなものです。 我々は行うことができるようにしたいです 物事は非常に、非常に迅速に。 私たちはときにここでそれを発見しました 我々はしようと話をしていますか？ さて、見てみましょう。 だから我々はいくつか見てきました 異なるデータ構造 それは、マッピングを処理 いわゆるキーと値のペア、 データのいくつかの作品をマッピング データのいくつかの他の作品に 私たちはどこに見つけることを知っています 構造体の情報。 そのようにアレイの、例えば、 キーは要素のインデックスまたは配列 位置0またはアレイ1のように。 そして、値はデータであり、 それは、その場所に存在します。 だから、配列0に何を保存されていますか？ ただ対アレイ1には何が保存されています 0と1の鍵されるであろう。 ハッシュテーブルで、それはです 同じ考えのようなもの。 ハッシュテーブルでは、我々はこのハッシュを持っています ハッシュコードを生成する関数。 そうキーは、データのハッシュコードがあります。 特に値が 私たちは、連鎖について話しました ハッシュテーブル上のビデオでは、 データのリンクリストです それは、そのハッシュコードにハッシュします。 右。 別のアプローチはどう この方法は、しかし？ 方法はどう キーは一意であることが保証され、 ハッシュテーブル、我々はできるとは異なり、 データの二枚で終わります 同じハッシュコードを持ちます。 そして、我々が対処しなければなりません そのいずれかのプロービング以上 好ましくは、その問題を解決するために連鎖。 だから今、私たちは保証することができます 我々のキーはユニークです。 そして、私たちの価値は何だった場合 簡単としてだけで何か かどうかを教えてくれるものと真と偽 情報のかその部分 構造内に存在しますか？ ブールビットと同じくらい簡単である可能性があります。 現実的にそれはおそらくです ビット以上の可能性が高いバイト。 しかし、それはより多くの小さいです 多分、50文字の文字列を格納し、 例えば。 試行だから、テーブルのハッシュと同様に、 これは配列やリンクリストを結合し、 試行は、配列を組み合わせて、 構造体、ポインタ 一緒にデータを格納します だ興味深い方法 とかなり異なります 我々はこれまでに見てきたもの。 今、私たちはロードマ​​ップとしてデータを使用します このデータ構造をナビゲートします。 そして、我々は従うことができた場合 ロードマップ、我々はできる場合 からのデータに従ってください 終始、我々はよ そのデータかどうかを知ります トライ中に存在します。 そして、我々は、マップに従うことができない場合 すべてで終了するという意味から、 データが存在することはできません。 ここでも、鍵はここにあります 一意であることが保証されています。 だからハッシュテーブルとは異なり、私たちは決して ここで衝突に対処する必要があります。 そして、データの無い2枚 まったく同じロードマップを持っています そのデータが同じである場合を除きます。 我々はジョンを挿入した場合、 我々はジョンを検索します。 それは2つの同一の部分です データは、右、我々はを通じて探しています。 しかし、そうでない場合は、任意の データの2つの部分があります ユニークなロードマップを持つことが保証 このデータ構造を通ります。 そして、私たちは見てみるつもりです 一瞬でこれを視覚的に。 我々はしようとすることでこれをやります 新しいデータ構造を作成し、 次のキーと値のペアをマッピングします。 ここでは、使用するつもりはありません ブールのような単純なもの。 私たちは、実際には文字列を格納します。 そして、その文字列をしようとしています 大学の名前です。 そして、キーは年になるだろう その大学が設立されたとき。 大学のためのすべての年 4桁の数字であることを行っています。 そして、私たちはそれらに4桁を使用します このデータ構造をナビゲート。 そして、私たちはどのように、再び、表示されます 私達はちょうど第二にそれを行います。 パスの最後に、 我々は名前が表示されます 対応大学の そのキーに、それらの4桁の数字。 トライの背後にある基本的な考え方 我々は中央ルートがあります。 だから、木のようにそれについて考えます。 そして、これはスペルが似ています ツリーの概念です。 一般的に私たちが考えると 現実の世界では木、 彼らは中のルートを持っています 地面と彼らが上方に成長 そして、彼らは枝を持っています 彼らは葉を持っています。 との基本的考え方 トライは、まったく同じです そのルートが固定されている以外 空のどこか。 そして葉は下部にあります。 だから、種類の木を取るようなものです そしてちょうどそれを逆さまにひっくり返します。 しかし、枝が残っています。 そして、それらは私たちの経路となり、 それらは私達の接続になります ルートからリーフへ。 この場合、これらの パス、それらの枝 教えて数字が付されています これは我々がどこにあるかから移動するための方法。 私たちは0が表示された場合、我々はこのブランチを下ります、 我々は1が表示された場合、我々はこのブランチを下ります、 などのように。 さて、これは何を意味するのでしょうか？ まあ、それはあることを意味 すべての接続点の と内のすべてのノード 途中、すべての枝、 10可能性があります 私たちが行くことができる場所。 だから10のポインタがあります すべての場所から。 試行を得ることができる場所、これはあります 誰かのために威圧少し 誰がするの多くを持っていません 前コンピュータサイエンスの経験。 しかし、試行は本当にすごいです。 そして、あなたが持っている場合 彼らと仕事をする機会 あなたは掘るインために喜んでいます それらを試して、 彼らは本当に非常に興味深いです で動作するデータ構造。 我々は、要素を挿入する場合 トライに、私たちが行う必要があるすべて 正しいパスを構築しています ルートからリーフまで。 ここではどのようなすべてのステップに沿ってです 方法は、次のようになります。 私たちは、新しいデータを定義しようとしています トライと呼ばれる新しいノードの構造。 そして、そのデータの内部 構造2個があります。 私たちは、保存しようとしています 大学の名前。 そして、我々は店に行っています ポインタの配列 同じタイプの他のノードに。 そのように、再び、これは、その一種であります どこでも概念の 我々は、我々は可能な10で、あります 私たちが行くことができる場所。 私たちは0が表示された場合、我々はこのブランチを下ります。 私たちは1表示された場合、このブランチ、 などなどのように。 私たちは9を言うなら、私たちはこのブランチを下ります。 だから、すべての接続点の、 我々は10の可能な場所に行くことができます。 だから、すべてのノードには、10のポインタが含まれている必要があり 他のノードに、10の他のノードに。 そして、私たちが保存しているデータがあります 大学の名前だけ。 それでは、トライを作成してみましょう。 カップルを挿入してみましょう 私たちのトライへのアイテムの。 、非常に上部にあるそう これは私たちのルートノードです。 これはおそらく、何かになるだろう あなたが宣言をグローバルになるだろう。 そして、あなたは維持グローバルになるだろう 常に、このノードへのポインタ。 あなたが言おうとしています、 ルートは等しく、あなたがしています 自分でトライノードををmallocに行きます。 そして、あなたが行くことはありませんしています 再び根に触れ。 あなたがするたび ナビゲートを開始、 あなたは別のポインタを設定 このようTRAVとして、根に等しく、 例Iであります 自分の動画の多くで使用 ここでスタックとキューの リンクリストのように。 もし、別のポインタを設定します トラバーサルのためTRAVと呼ばれます。 そして、あなたがナビゲートするTRAVを使用 データ構造を通ります。 それでは、これはどのように見えるかを見てみましょう。 だから、今、何を ノードは次のように見えますか？ まあ、ちょうど私たちのデータとして 構造体の宣言は、示されました 我々は、文字列を持っています この場合には空です。 ここには何もありません。 そして、10ポインタの配列。 そして今、我々だけ このトライで1ノードを持っています。 その中に他には何もありません。 だから、それらのすべての10 ポインタがヌルを指します。 それは赤が示すものです。 のは、文字列ハーバードを挿入してみましょう。 大学を挿入してみましょう このトライにハーバード大学、どの 今年1636年に設立されました。 我々は、キーを使用する場合、 1636年、私たちはしている場所を教えします トライでハーバード大学を保存するために行きます。 今、私たちはそれをどのように行うのでしょうか？ それは次のようになります。 私たちは、ルートから始まります。 そして、私たちは私たちが行くことができ、これらの10の場所を持っています。 ルートはただのようなものです トライの他のノード。 我々はここから行くことができる10の場所があります。 我々は、おそらくどこにしたいです キーが1636である場合に行くには？ 実際には2つのオプションがあります。 右。 私たちは、からキーを構築することができます 右、左と6を開始します。 それともからキーを構築することができ 左から右へと1から開始します。 それはおそらくより多くのです 人間としての直感的な 私たちを理解するためによ ちょうど左から右に移動します。 だから、私は挿入する場合 このトライにハーバード大学、 私はおそらく開始します ルートから開始することにより、 私の10のオプションを見て 私の前に、と言って 私は1道を行きたいです。 OK。 さて、1パスは、現在nullです。 だから私は、その道を進んでしたい場合 トライにこの要素を挿入するには、 私は1を持って、新しいノードををmallocする必要があります そこにポイントして、[私が行ってもいいよ。 だから私は基本的に午前 私が立っている点 ツリーのルートにありますか トライと10の支店があります。 しかし、各ブランチが持っています その前にゲート。 右。 他に何もないのであります。 いいえ安全な通行ません。 それは何もないことを意味し これらの枝のいずれかのダウン。 私は建物を開始する場合 何かが、私はゲートを削除したいです。 私はゲートを削除したいです 数1の正面インチ そして、私はそれを歩いしたいです。 そして、私が構築したいです 私のための別の場所に移動します。 そして、それは私がここでやったものです。 だから、1 nullにもはやポイント。 私はそれが今ここにダウンしても安全だと述べてきました。 私は別のノードを構築しました。 そして、私はそのノードに到達したとき、私は 作るために別の決定を持っています。 どこにここから行くつもりですか？ まあ、私はすでに1を下に行ってきました。 だから今私はおそらく6を下に行きたいです。 右。 繰り返しますが、私は私が選択することができます10の場所を持っています。 それでは、今数6を下に行ってみましょう。 だから私はゲートをクリア 数6の正面インチ そして、私はそこに歩きます。 そして、私は別のノードを構築します。 そして、私は別の接合点に達しました。 繰り返しますが、私は10の選択肢を持っています 私は行くことができる場所のため。 私は1から6まで移動しました。 だから今私はおそらく3に行きたいです。 図3は、私は行くことができますどこにもありません。 だから私は道をクリアする必要があります そして、自分自身に新しい領域を作成します。 そして、私が行きたいん3、から？ 私がダウンして6行きたいです。 そして、再び、私がしなければなりませんでした それを行うための方法をオフにします。 だから今私が作成し挿入するために、私のキーを使用しました ノードと、このトライを構築するために開始します。 私はルートに開始しました。 私は、1636ダウンしてきました。 そして今、私は底によ そこにそのノード上。 そして、あなたがすることができるかもしれません 画面にそれを参照してください。 これは、黄色でハイライト表示さ​​れます。 私は現在、午前ところです。 私のキーが行われます。 私は私のキーのすべての位置を使い果たしました。 だから私は先に進むことはできません。 この時点で、すべてのIだから 本当にOK、と言っている実行する必要があります。 それは一種の見てのようなものです 地面にダウンし、 あなたが想定している場合 自分のパスのこの種として 異なる接続で。 見下ろしのソート、ソートの 地面にハーバード大学の塗装スプレー。 つまり、この名前です。 それはこの場所に何があるか知っています。 我々はルートから開始し、我々はダウンした場合 1、次いで6、次に3、次いで6 ここはどこ？ さて、私たちがダウンして見れば 私たちはその後、ハーバード大学を参照してください 私たちは、ハーバード大学であったことを知っています 途中に基づいて1636年に設立されました 我々は、このデータ構造を実装しています。 だから、うまくいけば簡単でした。 我々は2つ​​以上の挿入をやろう​​としています。 そして、うまくいけばそれはするのに役立ちます これが二回以上行って参照してください。 それでは、他大学を挿入してみましょう。 それでは、このトライにエールを挿入してみましょう。 エールは、1701年に設立されました。 だから我々は、から始まります 根、私たちは常にそうであるように。 そして、我々はトラバーサルのポインタを設定します。 私たちはを移動することを使用するつもりです。 私たちがしたい最初のこと 行う1パスを下るです。 それが私たちのキーの最初の数字です。 幸いなことに、しかし、我々にはありません すべての作業にこの時間を行う必要があります。 1パスがすでにクリアされています。 私は以前にときに私にそれをクリア 1636年にハーバード大学を挿入しました。 だから私は、安全に移動することができます 1ダウン、ちょうどそこに行きます。 1を下に移動することができます。 さて、しかし、私は7に行きたいです。 私は6で道をクリアしました。 私は私が安全にすることができます知っています 6道を進みます。 しかし、私は7パスで続行する必要があります。 だから何をする必要がありますか？ まあ、ちょうど前のように、私はちょうど必要 ゲートをクリアするには、道から抜け出します、 7パスから新しいノードを作成します。 ちょうどこのような。 だから今、私は1、次に7を移動しました。 そして今、私はソートよ、気づきます この新しいサブブランチ上の。 右。 16から他のすべて で、私は気にしないでください。 私は16何もしていませんよ。 私が17のものをやっています。 だから今の17から、私がする必要はあり ソートのここで新しいトレイル火災。 次の桁は、私のキーは0です。 私は明らかにどこに行くことはできません。 私は、このノードを構築しました。 だから私は何もありません知っています ここから前方へのパス。 だから、私は1つを自分で行う必要があります。 だから私は、新しいノードををmalloc そしてそこに0点を持っています。 そして、もう一回、私のmalloc A 新しいノードとそこに一点を持っています。 繰り返しますが、私は私のキー、1701を使い果たしました。 だから私はダウンして見て、私はエールをペイントスプレー。 つまり、このノードの名前です。 そして今、私は今までにエールかどうかを確認する必要がある場合 このトライであり、私はルートから始まります、 私は、1701ダウンして、下を見ます。 そして、私はエールスプレーを見れば その後、地面に描かれ 私はエールは、このトライで存在することがわかっています。 それでは、もう一つのをやってみましょう。 この中ダートマスを挿入してみましょう 1769年に設立されたトライ。 再びルートで起動します。 私のキーの私の最初の桁が1です。 私は安全にそのパスを下に移動することができます。 それが既に存在します。 私のキーの次の桁は7です。 私は安全にそのパスを下に移動することができます。 それだけでなく、存在しています。 私の次は6です。 ここから、私は現在、午前どこから その中のノードであり、黄色で、 図6は、現在オフにロックされています。 私はその道を行きたい場合は、 私はそれを自分自身を構築する必要があります。 だから私は、新しいノードををmallocます そしてそこに6点を持っています。 そして、再び、私はよ ここに新しい道燃えます。 だから私は、新しいノードををmallocからなるように 今そのnode--パス番号9--と 私は1769年に移動し、私がダウンして見れば。 何はありません スプレーが描きました。 私は、ダートマスを書くことができます。 そして、私は挿入しました トライにダートマス。 だから、挿入です トライに物事。 今、私たちは物事を検索します。 どのように我々はトライで物事を探していますか？ まあ、それはほとんど同じ考えです。 今、私たちはただキーの数字を使用します 我々はルートからナビゲートすることができるかどうかを確認します 我々はトライに行きたい場所へ。 我々は、その後、任意の時点で行き止まりにヒットした場合 私たちは、その要素が存在することができないことを知っています あるいはそのパスがあろう 既にクリアされました。 我々はそれがすべての方法に加えた場合 最後に、我々がする必要があるすべて 見下ろすとそれがないかどうかを確認で 我々が探している要素。 それは、成功している場合。 そうでない場合は、失敗します。 それでは、を探してみましょう このトライでハーバード大学。 私たちは、ルートから始まります。 そして、再び、我々はするつもりです トラバーサルのポインタを作成します 私たちのために私たちの動きをすることができません。 ルートから、我々はことを知っています 私たちが行く必要がある最初の場所は1であり、 我々はそれを行うことができますか？ はい、我々はできます。 場合は、安全に存在します。 我々はそこに行くことができます。 今、私たちが行く必要がある次の場所は6です。 6パスは、ここから存在していますか？ ええ、それはありません。 私たちは、6道を行くことができます。 そして、私たちはここで終わります。 私たちはここから3の道を行くことはできますか？ まあ、それは結局のところ、 はい、それはあまりにも存在します。 そして、私たちはここから6パスで入手できますか？ はい、我々はできます。 我々は非常に答えていません まだ質問。 もう一つは、まだあります 今あるステップ、 私たちがダウンして見る必要があると それがactually--だかどうかを確認 我々はハーバード大学を探しているなら、ということです 我々は、キーを排気した後に何を見つけますか？ 例では、ここで使用しています、 年は常に4桁の数字です。 しかし、あなたはどこに例を使用している場合があります あなたは単語の辞書を格納しています。 だから代わりに10のポインタを持っていることの 私の場所のために、あなたは26を持っている可能性があります。 アルファベットの各文字の一つ。 そして、バットのようないくつかの単語がありますが、 これは例えば、バッチのサブセットです。 だからあなたが取得する場合でも、 キーの最後、あなたがダウンして見て、 あなたは何を参照しない可能性があり あなたが探しています。 だから、常に横断する必要があります 全体のパスと あなたが正常にできた場合 パス全体を横断します、 下を見ると1最終確認を行います。 それは私が探しているものはありますか？ まあ、私は開始後見下ろします 上部にと1636に行きます。 私がダウンして見てください。 私はハーバード大学を参照してください。 だから、はい、私は成功しました。 私は何を探していたらどう しかし、トライではありません。 私はプリンストンを探していますどのような場合には、 これは1746年に設立されました。 それで1746年、私のキーになります トライをナビゲートします。 まあ、私はルートから始まります。 そして、私がしたい最初の場所 1パスをダウンします。 私はそれを行うことができますか？ はい、私はすることができます。 私はそこから7道を行くことはできますか？ ええ、私はすることができます。 それはあまりにも存在します。 しかし、私は、ここから4道を行くことができますか？ それは、質問をするようにすることができます 私はその小さな広場を下に進みます 私は黄色で強調表示されていることを？ そこには何もありません。 右。 4パスダウン前方に方法はありません。 プリンストンは、このトライにあった場合は、その4 すでに私たちのためにクリアされていたであろう。 だからこの時点で 我々は袋小路に達しました。 我々は先に進むことはできません。 そして、私たちはありません、決定的に、言うことができます。 プリンストンは、このトライに存在しません。 これはすべて何を意味するのでしょうか？ 右。 ここで起こっがたくさんあり​​ます。 すべての場所の上にポインタがあります。 そして、あなたが見ることができるように ただ、ダイアグラムから そのノードがたくさんあり​​ます 種の周りに飛んでいます。 しかし、私たちがしたかったたびに気付きます 何かがトライしていたかどうかを確認し、 我々は唯一の4の移動をしなければなりませんでした。 我々が望んでいたたびに トライで何かを挿入し、 我々は、おそらく、4移動をしなければなりません 道に沿っていくつかのものをmallocing。 しかし、我々は挿入したとき、我々が見たように トライにダートマス、 時々、パスの一部 すでに私たちのためにクリアされることがあります。 だから私たちのトライはにつれて大きく、 大きな、私たちは以下の作業を毎回行う必要があり 新しいものを挿入します 我々はすでにきたので、 中間の多くを建て 途中で分岐します。 私たちは今まで見ている場合 4物事は、4だけで一定です。 私たちは本当に種類の近づいています 一定時間の挿入 そして一定時間のルックアップ。 当然のトレードオフは、そのされ あなたはおそらく言うことができるように、このトライ、 巨大です。 これらのノードの各々 多くのスペースを占有します。 しかし、それはトレードオフです。 私たちは本当に迅速にしたい場合 挿入、本当に迅速な削除、 本当に迅速な検索は、我々がする必要はあり 飛んデータがたくさんあり​​ます。 私たちは多くのスペースを別に設定する必要があります そのデータ構造のためのメモリ 存在します。 そしてそうそれはトレードオフです。 しかし、それは、私たちのように見えます それを発見した可能性があります。 我々はことを発見したかもしれません データ構造の聖杯 迅速な挿入と、 削除、および検索。 そして多分これは次のようになります 適切なデータ構造 どんな情報に使用します 我々は店にしようとしています。 私はダグロイドだけど、これはCS50です。