1
00:00:00,000 --> 00:00:02,994
>> [音楽再生]

2
00:00:02,994 --> 00:00:05,426

3
00:00:05,426 --> 00:00:08,550
DOUG LLOYD：だから我々は近いインチングされてきました
そして、近いそのデータの聖杯

4
00:00:08,550 --> 00:00:13,050
構造、我々は挿入することができます1
から、削除、およびルックアップ

5
00:00:13,050 --> 00:00:15,440
一定の時間です。

6
00:00:15,440 --> 00:00:16,270
右。

7
00:00:16,270 --> 00:00:17,280
それが目標のようなものです。

8
00:00:17,280 --> 00:00:19,720
我々は行うことができるようにしたいです
物事は非常に、非常に迅速に。

9
00:00:19,720 --> 00:00:22,580
>> 私たちはときにここでそれを発見しました
我々はしようと話をしていますか？

10
00:00:22,580 --> 00:00:23,670
さて、見てみましょう。

11
00:00:23,670 --> 00:00:25,628
だから我々はいくつか見てきました
異なるデータ構造

12
00:00:25,628 --> 00:00:28,680
それは、マッピングを処理
いわゆるキーと値のペア、

13
00:00:28,680 --> 00:00:32,080
データのいくつかの作品をマッピング
データのいくつかの他の作品に

14
00:00:32,080 --> 00:00:36,020
私たちはどこに見つけることを知っています
構造体の情報。

15
00:00:36,020 --> 00:00:40,060
>> そのようにアレイの、例えば、
キーは要素のインデックスまたは配列

16
00:00:40,060 --> 00:00:42,600
位置0またはアレイ1のように。

17
00:00:42,600 --> 00:00:46,140
そして、値はデータであり、
それは、その場所に存在します。

18
00:00:46,140 --> 00:00:48,550
だから、配列0に何を保存されていますか？

19
00:00:48,550 --> 00:00:54,290
ただ対アレイ1には何が保存されています
0と1の鍵されるであろう。

20
00:00:54,290 --> 00:00:56,360
>> ハッシュテーブルで、それはです
同じ考えのようなもの。

21
00:00:56,360 --> 00:01:00,690
ハッシュテーブルでは、我々はこのハッシュを持っています
ハッシュコードを生成する関数。

22
00:01:00,690 --> 00:01:03,670
そうキーは、データのハッシュコードがあります。

23
00:01:03,670 --> 00:01:06,530
特に値が
私たちは、連鎖について話しました

24
00:01:06,530 --> 00:01:10,590
ハッシュテーブル上のビデオでは、
データのリンクリストです

25
00:01:10,590 --> 00:01:12,550
それは、そのハッシュコードにハッシュします。

26
00:01:12,550 --> 00:01:14,050
右。

27
00:01:14,050 --> 00:01:16,050
別のアプローチはどう
この方法は、しかし？

28
00:01:16,050 --> 00:01:21,000
方法はどう
キーは一意であることが保証され、

29
00:01:21,000 --> 00:01:25,410
ハッシュテーブル、我々はできるとは異なり、
データの二枚で終わります

30
00:01:25,410 --> 00:01:27,200
同じハッシュコードを持ちます。

31
00:01:27,200 --> 00:01:30,020
そして、我々が対処しなければなりません
そのいずれかのプロービング以上

32
00:01:30,020 --> 00:01:33,340
好ましくは、その問題を解決するために連鎖。

33
00:01:33,340 --> 00:01:37,520
>> だから今、私たちは保証することができます
我々のキーはユニークです。

34
00:01:37,520 --> 00:01:39,690
そして、私たちの価値は何だった場合
簡単としてだけで何か

35
00:01:39,690 --> 00:01:44,080
かどうかを教えてくれるものと真と偽
情報のかその部分

36
00:01:44,080 --> 00:01:45,610
構造内に存在しますか？

37
00:01:45,610 --> 00:01:48,180
ブールビットと同じくらい簡単である可能性があります。

38
00:01:48,180 --> 00:01:52,660
現実的にそれはおそらくです
ビット以上の可能性が高いバイト。

39
00:01:52,660 --> 00:01:55,410
しかし、それはより多くの小さいです
多分、50文字の文字列を格納し、

40
00:01:55,410 --> 00:01:57,360
例えば。

41
00:01:57,360 --> 00:02:02,210
>> 試行だから、テーブルのハッシュと同様に、
これは配列やリンクリストを結合し、

42
00:02:02,210 --> 00:02:05,790
試行は、配列を組み合わせて、
構造体、ポインタ

43
00:02:05,790 --> 00:02:08,509
一緒にデータを格納します
だ興味深い方法

44
00:02:08,509 --> 00:02:11,550
とかなり異なります
我々はこれまでに見てきたもの。

45
00:02:11,550 --> 00:02:16,750
今、私たちはロードマ​​ップとしてデータを使用します
このデータ構造をナビゲートします。

46
00:02:16,750 --> 00:02:18,710
そして、我々は従うことができた場合
ロードマップ、我々はできる場合

47
00:02:18,710 --> 00:02:22,390
からのデータに従ってください
終始、我々はよ

48
00:02:22,390 --> 00:02:24,945
そのデータかどうかを知ります
トライ中に存在します。

49
00:02:24,945 --> 00:02:28,310
>> そして、我々は、マップに従うことができない場合
すべてで終了するという意味から、

50
00:02:28,310 --> 00:02:30,600
データが存在することはできません。

51
00:02:30,600 --> 00:02:32,890
ここでも、鍵はここにあります
一意であることが保証されています。

52
00:02:32,890 --> 00:02:36,020
だからハッシュテーブルとは異なり、私たちは決して
ここで衝突に対処する必要があります。

53
00:02:36,020 --> 00:02:39,090
そして、データの無い2枚
まったく同じロードマップを持っています

54
00:02:39,090 --> 00:02:40,530
そのデータが同じである場合を除きます。

55
00:02:40,530 --> 00:02:44,580
>> 我々はジョンを挿入した場合、
我々はジョンを検索します。

56
00:02:44,580 --> 00:02:47,430
それは2つの同一の部分です
データは、右、我々はを通じて探しています。

57
00:02:47,430 --> 00:02:49,880
しかし、そうでない場合は、任意の
データの2つの部分があります

58
00:02:49,880 --> 00:02:52,750
ユニークなロードマップを持つことが保証
このデータ構造を通ります。

59
00:02:52,750 --> 00:02:56,210
そして、私たちは見てみるつもりです
一瞬でこれを視覚的に。

60
00:02:56,210 --> 00:02:58,810
>> 我々はしようとすることでこれをやります
新しいデータ構造を作成し、

61
00:02:58,810 --> 00:03:00,564
次のキーと値のペアをマッピングします。

62
00:03:00,564 --> 00:03:03,480
ここでは、使用するつもりはありません
ブールのような単純なもの。

63
00:03:03,480 --> 00:03:06,200
私たちは、実際には文字列を格納します。

64
00:03:06,200 --> 00:03:08,690
そして、その文字列をしようとしています
大学の名前です。

65
00:03:08,690 --> 00:03:12,140
>> そして、キーは年になるだろう
その大学が設立されたとき。

66
00:03:12,140 --> 00:03:15,380
大学のためのすべての年
4桁の数字であることを行っています。

67
00:03:15,380 --> 00:03:19,840
そして、私たちはそれらに4桁を使用します
このデータ構造をナビゲート。

68
00:03:19,840 --> 00:03:22,270
そして、私たちはどのように、再び、表示されます
私達はちょうど第二にそれを行います。

69
00:03:22,270 --> 00:03:25,110
>> パスの最後に、
我々は名前が表示されます

70
00:03:25,110 --> 00:03:30,250
対応大学の
そのキーに、それらの4桁の数字。

71
00:03:30,250 --> 00:03:34,390
トライの背後にある基本的な考え方
我々は中央ルートがあります。

72
00:03:34,390 --> 00:03:35,640
だから、木のようにそれについて考えます。

73
00:03:35,640 --> 00:03:39,211
そして、これはスペルが似ています
ツリーの概念です。

74
00:03:39,211 --> 00:03:41,460
一般的に私たちが考えると
現実の世界では木、

75
00:03:41,460 --> 00:03:44,090
彼らは中のルートを持っています
地面と彼らが上方に成長

76
00:03:44,090 --> 00:03:46,830
そして、彼らは枝を持っています
彼らは葉を持っています。

77
00:03:46,830 --> 00:03:49,450
との基本的考え方
トライは、まったく同じです

78
00:03:49,450 --> 00:03:51,755
そのルートが固定されている以外
空のどこか。

79
00:03:51,755 --> 00:03:53,130
そして葉は下部にあります。

80
00:03:53,130 --> 00:03:55,750
>> だから、種類の木を取るようなものです
そしてちょうどそれを逆さまにひっくり返します。

81
00:03:55,750 --> 00:03:56,880
しかし、枝が残っています。

82
00:03:56,880 --> 00:03:59,463
そして、それらは私たちの経路となり、
それらは私達の接続になります

83
00:03:59,463 --> 00:04:02,220
ルートからリーフへ。

84
00:04:02,220 --> 00:04:04,200
この場合、これらの
パス、それらの枝

85
00:04:04,200 --> 00:04:08,490
教えて数字が付されています
これは我々がどこにあるかから移動するための方法。

86
00:04:08,490 --> 00:04:11,800
>> 私たちは0が表示された場合、我々はこのブランチを下ります、
我々は1が表示された場合、我々はこのブランチを下ります、

87
00:04:11,800 --> 00:04:12,900
などのように。

88
00:04:12,900 --> 00:04:14,060
さて、これは何を意味するのでしょうか？

89
00:04:14,060 --> 00:04:16,519
まあ、それはあることを意味
すべての接続点の

90
00:04:16,519 --> 00:04:19,260
と内のすべてのノード
途中、すべての枝、

91
00:04:19,260 --> 00:04:23,020
10可能性があります
私たちが行くことができる場所。

92
00:04:23,020 --> 00:04:27,690
だから10のポインタがあります
すべての場所から。

93
00:04:27,690 --> 00:04:30,610
>> 試行を得ることができる場所、これはあります
誰かのために威圧少し

94
00:04:30,610 --> 00:04:34,460
誰がするの多くを持っていません
前コンピュータサイエンスの経験。

95
00:04:34,460 --> 00:04:35,960
しかし、試行は本当にすごいです。

96
00:04:35,960 --> 00:04:37,793
そして、あなたが持っている場合
彼らと仕事をする機会

97
00:04:37,793 --> 00:04:40,420
あなたは掘るインために喜んでいます
それらを試して、

98
00:04:40,420 --> 00:04:44,234
彼らは本当に非常に興味深いです
で動作するデータ構造。

99
00:04:44,234 --> 00:04:46,900
我々は、要素を挿入する場合
トライに、私たちが行う必要があるすべて

100
00:04:46,900 --> 00:04:51,360
正しいパスを構築しています
ルートからリーフまで。

101
00:04:51,360 --> 00:04:55,390
ここではどのようなすべてのステップに沿ってです
方法は、次のようになります。

102
00:04:55,390 --> 00:04:59,660
私たちは、新しいデータを定義しようとしています
トライと呼ばれる新しいノードの構造。

103
00:04:59,660 --> 00:05:02,560
>> そして、そのデータの内部
構造2個があります。

104
00:05:02,560 --> 00:05:05,460
私たちは、保存しようとしています
大学の名前。

105
00:05:05,460 --> 00:05:09,410
そして、我々は店に行っています
ポインタの配列

106
00:05:09,410 --> 00:05:12,190
同じタイプの他のノードに。

107
00:05:12,190 --> 00:05:14,780
そのように、再び、これは、その一種であります
どこでも概念の

108
00:05:14,780 --> 00:05:18,567
我々は、我々は可能な10で、あります
私たちが行くことができる場所。

109
00:05:18,567 --> 00:05:20,150
私たちは0が表示された場合、我々はこのブランチを下ります。

110
00:05:20,150 --> 00:05:22,690
私たちは1表示された場合、このブランチ、
などなどのように。

111
00:05:22,690 --> 00:05:25,160
私たちは9を言うなら、私たちはこのブランチを下ります。

112
00:05:25,160 --> 00:05:28,220
だから、すべての接続点の、
我々は10の可能な場所に行くことができます。

113
00:05:28,220 --> 00:05:35,740
だから、すべてのノードには、10のポインタが含まれている必要があり
他のノードに、10の他のノードに。

114
00:05:35,740 --> 00:05:39,810
>> そして、私たちが保存しているデータがあります
大学の名前だけ。

115
00:05:39,810 --> 00:05:41,060
それでは、トライを作成してみましょう。

116
00:05:41,060 --> 00:05:44,860
カップルを挿入してみましょう
私たちのトライへのアイテムの。

117
00:05:44,860 --> 00:05:46,740
、非常に上部にあるそう
これは私たちのルートノードです。

118
00:05:46,740 --> 00:05:49,740
これはおそらく、何かになるだろう
あなたが宣言をグローバルになるだろう。

119
00:05:49,740 --> 00:05:53,450
そして、あなたは維持グローバルになるだろう
常に、このノードへのポインタ。

120
00:05:53,450 --> 00:05:55,360
>> あなたが言おうとしています、
ルートは等しく、あなたがしています

121
00:05:55,360 --> 00:05:57,580
自分でトライノードををmallocに行きます。

122
00:05:57,580 --> 00:05:59,850
そして、あなたが行くことはありませんしています
再び根に触れ。

123
00:05:59,850 --> 00:06:02,300
あなたがするたび
ナビゲートを開始、

124
00:06:02,300 --> 00:06:05,802
あなたは別のポインタを設定
このようTRAVとして、根に等しく、

125
00:06:05,802 --> 00:06:07,760
例Iであります
自分の動画の多くで使用

126
00:06:07,760 --> 00:06:11,090
ここでスタックとキューの
リンクリストのように。

127
00:06:11,090 --> 00:06:13,320
>> もし、別のポインタを設定します
トラバーサルのためTRAVと呼ばれます。

128
00:06:13,320 --> 00:06:15,890
そして、あなたがナビゲートするTRAVを使用
データ構造を通ります。

129
00:06:15,890 --> 00:06:17,500
それでは、これはどのように見えるかを見てみましょう。

130
00:06:17,500 --> 00:06:19,880
だから、今、何を
ノードは次のように見えますか？

131
00:06:19,880 --> 00:06:22,920
まあ、ちょうど私たちのデータとして
構造体の宣言は、示されました

132
00:06:22,920 --> 00:06:26,906
我々は、文字列を持っています
この場合には空です。

133
00:06:26,906 --> 00:06:27,780
ここには何もありません。

134
00:06:27,780 --> 00:06:29,550
>> そして、10ポインタの配列。

135
00:06:29,550 --> 00:06:31,790
そして今、我々だけ
このトライで1ノードを持っています。

136
00:06:31,790 --> 00:06:33,110
その中に他には何もありません。

137
00:06:33,110 --> 00:06:36,020
だから、それらのすべての10
ポインタがヌルを指します。

138
00:06:36,020 --> 00:06:38,090
それは赤が示すものです。

139
00:06:38,090 --> 00:06:39,500
>> のは、文字列ハーバードを挿入してみましょう。

140
00:06:39,500 --> 00:06:41,999
大学を挿入してみましょう
このトライにハーバード大学、どの

141
00:06:41,999 --> 00:06:43,940
今年1636年に設立されました。

142
00:06:43,940 --> 00:06:48,220
我々は、キーを使用する場合、
1636年、私たちはしている場所を教えします

143
00:06:48,220 --> 00:06:50,140
トライでハーバード大学を保存するために行きます。

144
00:06:50,140 --> 00:06:51,470
今、私たちはそれをどのように行うのでしょうか？

145
00:06:51,470 --> 00:06:52,886
>> それは次のようになります。

146
00:06:52,886 --> 00:06:54,160
私たちは、ルートから始まります。

147
00:06:54,160 --> 00:06:56,920
そして、私たちは私たちが行くことができ、これらの10の場所を持っています。

148
00:06:56,920 --> 00:06:59,900
ルートはただのようなものです
トライの他のノード。

149
00:06:59,900 --> 00:07:02,850
我々はここから行くことができる10の場所があります。

150
00:07:02,850 --> 00:07:07,215
>> 我々は、おそらくどこにしたいです
キーが1636である場合に行くには？

151
00:07:07,215 --> 00:07:08,340
実際には2つのオプションがあります。

152
00:07:08,340 --> 00:07:08,450
右。

153
00:07:08,450 --> 00:07:10,825
私たちは、からキーを構築することができます
右、左と6を開始します。

154
00:07:10,825 --> 00:07:14,000
それともからキーを構築することができ
左から右へと1から開始します。

155
00:07:14,000 --> 00:07:16,140
>> それはおそらくより多くのです
人間としての直感的な

156
00:07:16,140 --> 00:07:18,110
私たちを理解するためによ
ちょうど左から右に移動します。

157
00:07:18,110 --> 00:07:21,140
だから、私は挿入する場合
このトライにハーバード大学、

158
00:07:21,140 --> 00:07:23,560
私はおそらく開始します
ルートから開始することにより、

159
00:07:23,560 --> 00:07:25,720
私の10のオプションを見て
私の前に、と言って

160
00:07:25,720 --> 00:07:28,700
私は1道を行きたいです。

161
00:07:28,700 --> 00:07:29,700
OK。

162
00:07:29,700 --> 00:07:31,810
>> さて、1パスは、現在nullです。

163
00:07:31,810 --> 00:07:35,920
だから私は、その道を進んでしたい場合
トライにこの要素を挿入するには、

164
00:07:35,920 --> 00:07:42,040
私は1を持って、新しいノードををmallocする必要があります
そこにポイントして、[私が行ってもいいよ。

165
00:07:42,040 --> 00:07:46,460
>> だから私は基本的に午前
私が立っている点

166
00:07:46,460 --> 00:07:50,270
ツリーのルートにありますか
トライと10の支店があります。

167
00:07:50,270 --> 00:07:52,260
しかし、各ブランチが持っています
その前にゲート。

168
00:07:52,260 --> 00:07:53,060
右。

169
00:07:53,060 --> 00:07:54,850
他に何もないのであります。

170
00:07:54,850 --> 00:07:56,522
いいえ安全な通行ません。

171
00:07:56,522 --> 00:07:58,980
それは何もないことを意味し
これらの枝のいずれかのダウン。

172
00:07:58,980 --> 00:08:02,532
私は建物を開始する場合
何かが、私はゲートを削除したいです。

173
00:08:02,532 --> 00:08:04,490
私はゲートを削除したいです
数1の正面インチ

174
00:08:04,490 --> 00:08:05,698
そして、私はそれを歩いしたいです。

175
00:08:05,698 --> 00:08:08,060
そして、私が構築したいです
私のための別の場所に移動します。

176
00:08:08,060 --> 00:08:09,470
>> そして、それは私がここでやったものです。

177
00:08:09,470 --> 00:08:11,430
だから、1 nullにもはやポイント。

178
00:08:11,430 --> 00:08:13,830
私はそれが今ここにダウンしても安全だと述べてきました。

179
00:08:13,830 --> 00:08:15,789
私は別のノードを構築しました。

180
00:08:15,789 --> 00:08:18,330
そして、私はそのノードに到達したとき、私は
作るために別の決定を持っています。

181
00:08:18,330 --> 00:08:20,890
どこにここから行くつもりですか？

182
00:08:20,890 --> 00:08:22,700
>> まあ、私はすでに1を下に行ってきました。

183
00:08:22,700 --> 00:08:24,470
だから今私はおそらく6を下に行きたいです。

184
00:08:24,470 --> 00:08:24,970
右。

185
00:08:24,970 --> 00:08:27,100
繰り返しますが、私は私が選択することができます10の場所を持っています。

186
00:08:27,100 --> 00:08:30,060
それでは、今数6を下に行ってみましょう。

187
00:08:30,060 --> 00:08:32,280
だから私はゲートをクリア
数6の正面インチ

188
00:08:32,280 --> 00:08:33,250
そして、私はそこに歩きます。

189
00:08:33,250 --> 00:08:34,580
そして、私は別のノードを構築します。

190
00:08:34,580 --> 00:08:37,630
そして、私は別の接合点に達しました。

191
00:08:37,630 --> 00:08:40,289
>> 繰り返しますが、私は10の選択肢を持っています
私は行くことができる場所のため。

192
00:08:40,289 --> 00:08:42,799
私は1から6まで移動しました。

193
00:08:42,799 --> 00:08:44,215
だから今私はおそらく3に行きたいです。

194
00:08:44,215 --> 00:08:45,381
図3は、私は行くことができますどこにもありません。

195
00:08:45,381 --> 00:08:48,980
だから私は道をクリアする必要があります
そして、自分自身に新しい領域を作成します。

196
00:08:48,980 --> 00:08:50,870
そして、私が行きたいん3、から？

197
00:08:50,870 --> 00:08:52,450
私がダウンして6行きたいです。

198
00:08:52,450 --> 00:08:54,770
>> そして、再び、私がしなければなりませんでした
それを行うための方法をオフにします。

199
00:08:54,770 --> 00:08:59,179
だから今私が作成し挿入するために、私のキーを使用しました
ノードと、このトライを構築するために開始します。

200
00:08:59,179 --> 00:09:00,220
私はルートに開始しました。

201
00:09:00,220 --> 00:09:03,666
私は、1636ダウンしてきました。

202
00:09:03,666 --> 00:09:05,540
そして今、私は底によ
そこにそのノード上。

203
00:09:05,540 --> 00:09:06,610
そして、あなたがすることができるかもしれません
画面にそれを参照してください。

204
00:09:06,610 --> 00:09:07,735
>> これは、黄色でハイライト表示さ​​れます。

205
00:09:07,735 --> 00:09:10,020
私は現在、午前ところです。

206
00:09:10,020 --> 00:09:11,300
私のキーが行われます。

207
00:09:11,300 --> 00:09:13,030
私は私のキーのすべての位置を使い果たしました。

208
00:09:13,030 --> 00:09:15,040
だから私は先に進むことはできません。

209
00:09:15,040 --> 00:09:17,720
この時点で、すべてのIだから
本当にOK、と言っている実行する必要があります。

210
00:09:17,720 --> 00:09:18,990
それは一種の見てのようなものです
地面にダウンし、

211
00:09:18,990 --> 00:09:21,115
あなたが想定している場合
自分のパスのこの種として

212
00:09:21,115 --> 00:09:22,350
異なる接続で。

213
00:09:22,350 --> 00:09:25,800
見下ろしのソート、ソートの
地面にハーバード大学の塗装スプレー。

214
00:09:25,800 --> 00:09:26,800
つまり、この名前です。

215
00:09:26,800 --> 00:09:28,300
それはこの場所に何があるか知っています。

216
00:09:28,300 --> 00:09:31,870
我々はルートから開始し、我々はダウンした場合
1、次いで6、次に3、次いで6

217
00:09:31,870 --> 00:09:32,780
ここはどこ？

218
00:09:32,780 --> 00:09:35,640
さて、私たちがダウンして見れば
私たちはその後、ハーバード大学を参照してください

219
00:09:35,640 --> 00:09:38,960
私たちは、ハーバード大学であったことを知っています
途中に基づいて1636年に設立されました

220
00:09:38,960 --> 00:09:41,400
我々は、このデータ構造を実装しています。

221
00:09:41,400 --> 00:09:43,177
だから、うまくいけば簡単でした。

222
00:09:43,177 --> 00:09:44,760
我々は2つ​​以上の挿入をやろう​​としています。

223
00:09:44,760 --> 00:09:50,060
そして、うまくいけばそれはするのに役立ちます
これが二回以上行って参照してください。

224
00:09:50,060 --> 00:09:52,210
>> それでは、他大学を挿入してみましょう。

225
00:09:52,210 --> 00:09:54,630
それでは、このトライにエールを挿入してみましょう。

226
00:09:54,630 --> 00:09:57,037
エールは、1701年に設立されました。

227
00:09:57,037 --> 00:09:58,870
だから我々は、から始まります
根、私たちは常にそうであるように。

228
00:09:58,870 --> 00:09:59,890
そして、我々はトラバーサルのポインタを設定します。

229
00:09:59,890 --> 00:10:01,624
私たちはを移動することを使用するつもりです。

230
00:10:01,624 --> 00:10:03,790
私たちがしたい最初のこと
行う1パスを下るです。

231
00:10:03,790 --> 00:10:05,830
それが私たちのキーの最初の数字です。

232
00:10:05,830 --> 00:10:08,420
幸いなことに、しかし、我々にはありません
すべての作業にこの時間を行う必要があります。

233
00:10:08,420 --> 00:10:09,919
1パスがすでにクリアされています。

234
00:10:09,919 --> 00:10:13,520
私は以前にときに私にそれをクリア
1636年にハーバード大学を挿入しました。

235
00:10:13,520 --> 00:10:18,090
だから私は、安全に移動することができます
1ダウン、ちょうどそこに行きます。

236
00:10:18,090 --> 00:10:20,150
1を下に移動することができます。

237
00:10:20,150 --> 00:10:22,930
>> さて、しかし、私は7に行きたいです。

238
00:10:22,930 --> 00:10:24,280
私は6で道をクリアしました。

239
00:10:24,280 --> 00:10:27,050
私は私が安全にすることができます知っています
6道を進みます。

240
00:10:27,050 --> 00:10:29,220
しかし、私は7パスで続行する必要があります。

241
00:10:29,220 --> 00:10:30,580
だから何をする必要がありますか？

242
00:10:30,580 --> 00:10:35,070
まあ、ちょうど前のように、私はちょうど必要
ゲートをクリアするには、道から抜け出します、

243
00:10:35,070 --> 00:10:38,740
7パスから新しいノードを作成します。

244
00:10:38,740 --> 00:10:40,250
ちょうどこのような。

245
00:10:40,250 --> 00:10:42,930
>> だから今、私は1、次に7を移動しました。

246
00:10:42,930 --> 00:10:45,550
そして今、私はソートよ、気づきます
この新しいサブブランチ上の。

247
00:10:45,550 --> 00:10:46,050
右。

248
00:10:46,050 --> 00:10:49,260
16から他のすべて
で、私は気にしないでください。

249
00:10:49,260 --> 00:10:50,720
私は16何もしていませんよ。

250
00:10:50,720 --> 00:10:51,750
私が17のものをやっています。

251
00:10:51,750 --> 00:10:58,380
>> だから今の17から、私がする必要はあり
ソートのここで新しいトレイル火災。

252
00:10:58,380 --> 00:11:00,462
次の桁は、私のキーは0です。

253
00:11:00,462 --> 00:11:01,670
私は明らかにどこに行くことはできません。

254
00:11:01,670 --> 00:11:02,628
私は、このノードを構築しました。

255
00:11:02,628 --> 00:11:04,550
だから私は何もありません知っています
ここから前方へのパス。

256
00:11:04,550 --> 00:11:06,370
だから、私は1つを自分で行う必要があります。

257
00:11:06,370 --> 00:11:09,360
>> だから私は、新しいノードををmalloc
そしてそこに0点を持っています。

258
00:11:09,360 --> 00:11:12,770
そして、もう一回、私のmalloc A
新しいノードとそこに一点を持っています。

259
00:11:12,770 --> 00:11:15,870
繰り返しますが、私は私のキー、1701を使い果たしました。

260
00:11:15,870 --> 00:11:18,472
だから私はダウンして見て、私はエールをペイントスプレー。

261
00:11:18,472 --> 00:11:19,680
つまり、このノードの名前です。

262
00:11:19,680 --> 00:11:24,660
>> そして今、私は今までにエールかどうかを確認する必要がある場合
このトライであり、私はルートから始まります、

263
00:11:24,660 --> 00:11:27,060
私は、1701ダウンして、下を見ます。

264
00:11:27,060 --> 00:11:30,030
そして、私はエールスプレーを見れば
その後、地面に描かれ

265
00:11:30,030 --> 00:11:32,200
私はエールは、このトライで存在することがわかっています。

266
00:11:32,200 --> 00:11:32,950
それでは、もう一つのをやってみましょう。

267
00:11:32,950 --> 00:11:36,430
この中ダートマスを挿入してみましょう
1769年に設立されたトライ。

268
00:11:36,430 --> 00:11:37,750
>> 再びルートで起動します。

269
00:11:37,750 --> 00:11:39,445
私のキーの私の最初の桁が1です。

270
00:11:39,445 --> 00:11:40,820
私は安全にそのパスを下に移動することができます。

271
00:11:40,820 --> 00:11:42,400
それが既に存在します。

272
00:11:42,400 --> 00:11:44,040
私のキーの次の桁は7です。

273
00:11:44,040 --> 00:11:45,890
私は安全にそのパスを下に移動することができます。

274
00:11:45,890 --> 00:11:47,540
それだけでなく、存在しています。

275
00:11:47,540 --> 00:11:49,000
>> 私の次は6です。

276
00:11:49,000 --> 00:11:52,860
ここから、私は現在、午前どこから
その中のノードであり、黄色で、

277
00:11:52,860 --> 00:11:56,060
図6は、現在オフにロックされています。

278
00:11:56,060 --> 00:11:58,830
私はその道を行きたい場合は、
私はそれを自分自身を構築する必要があります。

279
00:11:58,830 --> 00:12:02,250
だから私は、新しいノードををmallocます
そしてそこに6点を持っています。

280
00:12:02,250 --> 00:12:04,250
そして、再び、私はよ
ここに新しい道燃えます。

281
00:12:04,250 --> 00:12:10,750
>> だから私は、新しいノードををmallocからなるように
今そのnode--パス番号9--と

282
00:12:10,750 --> 00:12:13,584
私は1769年に移動し、私がダウンして見れば。

283
00:12:13,584 --> 00:12:15,500
何はありません
スプレーが描きました。

284
00:12:15,500 --> 00:12:16,930
私は、ダートマスを書くことができます。

285
00:12:16,930 --> 00:12:20,710
そして、私は挿入しました
トライにダートマス。

286
00:12:20,710 --> 00:12:23,450
>> だから、挿入です
トライに物事。

287
00:12:23,450 --> 00:12:25,384
今、私たちは物事を検索します。

288
00:12:25,384 --> 00:12:27,050
どのように我々はトライで物事を探していますか？

289
00:12:27,050 --> 00:12:29,170
まあ、それはほとんど同じ考えです。

290
00:12:29,170 --> 00:12:33,620
今、私たちはただキーの数字を使用します
我々はルートからナビゲートすることができるかどうかを確認します

291
00:12:33,620 --> 00:12:37,170
我々はトライに行きたい場所へ。

292
00:12:37,170 --> 00:12:41,620
>> 我々は、その後、任意の時点で行き止まりにヒットした場合
私たちは、その要素が存在することができないことを知っています

293
00:12:41,620 --> 00:12:44,500
あるいはそのパスがあろう
既にクリアされました。

294
00:12:44,500 --> 00:12:45,930
我々はそれがすべての方法に加えた場合
最後に、我々がする必要があるすべて

295
00:12:45,930 --> 00:12:48,471
見下ろすとそれがないかどうかを確認で
我々が探している要素。

296
00:12:48,471 --> 00:12:49,335
それは、成功している場合。

297
00:12:49,335 --> 00:12:52,610
そうでない場合は、失敗します。

298
00:12:52,610 --> 00:12:54,940
>> それでは、を探してみましょう
このトライでハーバード大学。

299
00:12:54,940 --> 00:12:56,020
私たちは、ルートから始まります。

300
00:12:56,020 --> 00:12:58,228
そして、再び、我々はするつもりです
トラバーサルのポインタを作成します

301
00:12:58,228 --> 00:12:59,390
私たちのために私たちの動きをすることができません。

302
00:12:59,390 --> 00:13:02,080
ルートから、我々はことを知っています
私たちが行く必要がある最初の場所は1であり、

303
00:13:02,080 --> 00:13:03,390
我々はそれを行うことができますか？

304
00:13:03,390 --> 00:13:03,982
はい、我々はできます。

305
00:13:03,982 --> 00:13:04,690
場合は、安全に存在します。

306
00:13:04,690 --> 00:13:06,660
我々はそこに行くことができます。

307
00:13:06,660 --> 00:13:08,440
>> 今、私たちが行く必要がある次の場所は6です。

308
00:13:08,440 --> 00:13:10,557
6パスは、ここから存在していますか？

309
00:13:10,557 --> 00:13:11,140
ええ、それはありません。

310
00:13:11,140 --> 00:13:12,690
私たちは、6道を行くことができます。

311
00:13:12,690 --> 00:13:13,905
そして、私たちはここで終わります。

312
00:13:13,905 --> 00:13:16,130
>> 私たちはここから3の道を行くことはできますか？

313
00:13:16,130 --> 00:13:18,450
まあ、それは結局のところ、
はい、それはあまりにも存在します。

314
00:13:18,450 --> 00:13:20,790
そして、私たちはここから6パスで入手できますか？

315
00:13:20,790 --> 00:13:21,982
はい、我々はできます。

316
00:13:21,982 --> 00:13:24,002
>> 我々は非常に答えていません
まだ質問。

317
00:13:24,002 --> 00:13:25,710
もう一つは、まだあります
今あるステップ、

318
00:13:25,710 --> 00:13:28,520
私たちがダウンして見る必要があると
それがactually--だかどうかを確認

319
00:13:28,520 --> 00:13:32,660
我々はハーバード大学を探しているなら、ということです
我々は、キーを排気した後に何を見つけますか？

320
00:13:32,660 --> 00:13:35,430
例では、ここで使用しています、
年は常に4桁の数字です。

321
00:13:35,430 --> 00:13:40,280
しかし、あなたはどこに例を使用している場合があります
あなたは単語の辞書を格納しています。

322
00:13:40,280 --> 00:13:44,060
>> だから代わりに10のポインタを持っていることの
私の場所のために、あなたは26を持っている可能性があります。

323
00:13:44,060 --> 00:13:46,040
アルファベットの各文字の一つ。

324
00:13:46,040 --> 00:13:50,350
そして、バットのようないくつかの単語がありますが、
これは例えば、バッチのサブセットです。

325
00:13:50,350 --> 00:13:53,511
だからあなたが取得する場合でも、
キーの最後、あなたがダウンして見て、

326
00:13:53,511 --> 00:13:55,260
あなたは何を参照しない可能性があり
あなたが探しています。

327
00:13:55,260 --> 00:13:58,500
>> だから、常に横断する必要があります
全体のパスと

328
00:13:58,500 --> 00:14:01,540
あなたが正常にできた場合
パス全体を横断します、

329
00:14:01,540 --> 00:14:03,440
下を見ると1最終確認を行います。

330
00:14:03,440 --> 00:14:05,120
それは私が探しているものはありますか？

331
00:14:05,120 --> 00:14:07,740
まあ、私は開始後見下ろします
上部にと1636に行きます。

332
00:14:07,740 --> 00:14:08,240
私がダウンして見てください。

333
00:14:08,240 --> 00:14:09,400
私はハーバード大学を参照してください。

334
00:14:09,400 --> 00:14:11,689
だから、はい、私は成功しました。

335
00:14:11,689 --> 00:14:13,980
私は何を探していたらどう
しかし、トライではありません。

336
00:14:13,980 --> 00:14:17,200
私はプリンストンを探していますどのような場合には、
これは1746年に設立されました。

337
00:14:17,200 --> 00:14:20,875
それで1746年、私のキーになります
トライをナビゲートします。

338
00:14:20,875 --> 00:14:22,040
まあ、私はルートから始まります。

339
00:14:22,040 --> 00:14:24,760
そして、私がしたい最初の場所
1パスをダウンします。

340
00:14:24,760 --> 00:14:25,590
私はそれを行うことができますか？

341
00:14:25,590 --> 00:14:26,490
はい、私はすることができます。

342
00:14:26,490 --> 00:14:28,730
>> 私はそこから7道を行くことはできますか？

343
00:14:28,730 --> 00:14:29,230
ええ、私はすることができます。

344
00:14:29,230 --> 00:14:30,750
それはあまりにも存在します。

345
00:14:30,750 --> 00:14:32,460
しかし、私は、ここから4道を行くことができますか？

346
00:14:32,460 --> 00:14:35,550
それは、質問をするようにすることができます
私はその小さな広場を下に進みます

347
00:14:35,550 --> 00:14:37,114
私は黄色で強調表示されていることを？

348
00:14:37,114 --> 00:14:38,030
そこには何もありません。

349
00:14:38,030 --> 00:14:38,610
右。

350
00:14:38,610 --> 00:14:41,310
>> 4パスダウン前方に方法はありません。

351
00:14:41,310 --> 00:14:46,480
プリンストンは、このトライにあった場合は、その4
すでに私たちのためにクリアされていたであろう。

352
00:14:46,480 --> 00:14:49,130
だからこの時点で
我々は袋小路に達しました。

353
00:14:49,130 --> 00:14:50,250
我々は先に進むことはできません。

354
00:14:50,250 --> 00:14:53,440
そして、私たちはありません、決定的に、言うことができます。

355
00:14:53,440 --> 00:14:56,760
プリンストンは、このトライに存在しません。

356
00:14:56,760 --> 00:14:58,860
>> これはすべて何を意味するのでしょうか？

357
00:14:58,860 --> 00:14:59,360
右。

358
00:14:59,360 --> 00:15:01,000
ここで起こっがたくさんあり​​ます。

359
00:15:01,000 --> 00:15:02,500
すべての場所の上にポインタがあります。

360
00:15:02,500 --> 00:15:04,249
そして、あなたが見ることができるように
ただ、ダイアグラムから

361
00:15:04,249 --> 00:15:07,010
そのノードがたくさんあり​​ます
種の周りに飛んでいます。

362
00:15:07,010 --> 00:15:13,480
しかし、私たちがしたかったたびに気付きます
何かがトライしていたかどうかを確認し、

363
00:15:13,480 --> 00:15:15,000
我々は唯一の4の移動をしなければなりませんでした。

364
00:15:15,000 --> 00:15:17,208
>> 我々が望んでいたたびに
トライで何かを挿入し、

365
00:15:17,208 --> 00:15:20,440
我々は、おそらく、4移動をしなければなりません
道に沿っていくつかのものをmallocing。

366
00:15:20,440 --> 00:15:23,482
しかし、我々は挿入したとき、我々が見たように
トライにダートマス、

367
00:15:23,482 --> 00:15:25,940
時々、パスの一部
すでに私たちのためにクリアされることがあります。

368
00:15:25,940 --> 00:15:30,520
だから私たちのトライはにつれて大きく、
大きな、私たちは以下の作業を毎回行う必要があり

369
00:15:30,520 --> 00:15:32,270
新しいものを挿入します
我々はすでにきたので、

370
00:15:32,270 --> 00:15:35,746
中間の多くを建て
途中で分岐します。

371
00:15:35,746 --> 00:15:38,370
私たちは今まで見ている場合
4物事は、4だけで一定です。

372
00:15:38,370 --> 00:15:41,750
私たちは本当に種類の近づいています
一定時間の挿入

373
00:15:41,750 --> 00:15:44,501
そして一定時間のルックアップ。

374
00:15:44,501 --> 00:15:47,500
当然のトレードオフは、そのされ
あなたはおそらく言うことができるように、このトライ、

375
00:15:47,500 --> 00:15:49,030
巨大です。

376
00:15:49,030 --> 00:15:51,040
これらのノードの各々
多くのスペースを占有します。

377
00:15:51,040 --> 00:15:52,090
>> しかし、それはトレードオフです。

378
00:15:52,090 --> 00:15:55,260
私たちは本当に迅速にしたい場合
挿入、本当に迅速な削除、

379
00:15:55,260 --> 00:15:59,630
本当に迅速な検索は、我々がする必要はあり
飛んデータがたくさんあり​​ます。

380
00:15:59,630 --> 00:16:03,590
私たちは多くのスペースを別に設定する必要があります
そのデータ構造のためのメモリ

381
00:16:03,590 --> 00:16:04,290
存在します。

382
00:16:04,290 --> 00:16:05,415
>> そしてそうそれはトレードオフです。

383
00:16:05,415 --> 00:16:07,310
しかし、それは、私たちのように見えます
それを発見した可能性があります。

384
00:16:07,310 --> 00:16:09,560
我々はことを発見したかもしれません
データ構造の聖杯

385
00:16:09,560 --> 00:16:12,264
迅速な挿入と、
削除、および検索。

386
00:16:12,264 --> 00:16:14,430
そして多分これは次のようになります
適切なデータ構造

387
00:16:14,430 --> 00:16:18,890
どんな情報に使用します
我々は店にしようとしています。

388
00:16:18,890 --> 00:16:21,860
私はダグロイドだけど、これはCS50です。

389
00:16:21,860 --> 00:16:23,433