>> [音楽再生]
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です。