1
00:00:00,000 --> 00:00:07,700

2
00:00:07,700 --> 00:00:10,890
>> KEVINシュミット：時々、ビルドするとき
このプログラムは、あなたが利用することをお勧めします

3
00:00:10,890 --> 00:00:13,190
辞書として知られているデータ構造。

4
00:00:13,190 --> 00:00:17,960
ある辞書のマップキー、
通常の値に、文字列、整数、

5
00:00:17,960 --> 00:00:21,900
文字、いくつかのオブジェクトへのポインタ、
我々は好き。

6
00:00:21,900 --> 00:00:26,510
それは、普通の辞書のようなものだ
定義を通じてそのマップは言葉。

7
00:00:26,510 --> 00:00:29,440
>> 辞書はを提供してくれる
情報を記憶する能力

8
00:00:29,440 --> 00:00:32,750
何かに関連付けられている
後でそれを検索します。

9
00:00:32,750 --> 00:00:36,620
では、どのように実際に実装するのですか
Cコード、たとえば、辞書たちができる

10
00:00:36,620 --> 00:00:38,460
私たちのプログラムのいずれかで使うのか？

11
00:00:38,460 --> 00:00:41,790
まあ、それの方法はたくさんあり​​ます
私たちは辞書を実装することができます。

12
00:00:41,790 --> 00:00:45,930
>> 1のために、我々は我々の配列を使用することができます
動的に再サイズや、我々は使用することができます

13
00:00:45,930 --> 00:00:49,150
リンクリスト、ハッシュテーブル
またはバイナリツリー。

14
00:00:49,150 --> 00:00:52,250
しかし、我々は選択したものは何でも、私たちはすべき
効率に留意し、

15
00:00:52,250 --> 00:00:54,300
実装のパフォーマンス。

16
00:00:54,300 --> 00:00:57,930
我々は、使用されるアルゴリズムを考える必要があります
に項目を挿入して、ルックアップする

17
00:00:57,930 --> 00:00:59,120
私たちのデータ構造。

18
00:00:59,120 --> 00:01:03,060
>> ここでは、のは、その私たちを想定してみましょう
キーとして文字列を使用したいと思います。

19
00:01:03,060 --> 00:01:07,290
それでは一つの可能​​性についてお話しましょう​​、
データ構造は、トライと呼ばれる。

20
00:01:07,290 --> 00:01:11,210
だからここに視覚的な表現です
トライの。

21
00:01:11,210 --> 00:01:14,590
>> 写真は、トライを示唆しているように
とツリーデータ構造である

22
00:01:14,590 --> 00:01:16,050
互いにリンクされたノード。

23
00:01:16,050 --> 00:01:19,420
我々はルートが明確があることを参照してください。
に至るいくつかのリンクを持つノード

24
00:01:19,420 --> 00:01:20,500
他のノード。

25
00:01:20,500 --> 00:01:23,040
しかし、各ノードは、で構成されていますか？

26
00:01:23,040 --> 00:01:26,700
私たちは鍵を格納していると仮定した場合
英字のみとし、

27
00:01:26,700 --> 00:01:30,150
私たちは、大文字と小文字を気にしない、
ここに、そのノードの定義を示します

28
00:01:30,150 --> 00:01:31,100
十分です。

29
00:01:31,100 --> 00:01:34,130
>> 型が構造体であるオブジェクト
ノードには2つの部分があります

30
00:01:34,130 --> 00:01:35,740
データや子供たちを呼んだ。

31
00:01:35,740 --> 00:01:39,200
私たちは、コメントとしてデータ部分を残してきた
成分によって置換される

32
00:01:39,200 --> 00:01:43,190
構造ノードである宣言
Cプログラムに組み込ま。

33
00:01:43,190 --> 00:01:47,040
ノードのデータ部分は次のようになります。
かどうかを示すブール値

34
00:01:47,040 --> 00:01:51,160
いないノードが完了したことを表している
辞書のキーのまたはそれはあるかもしれない

35
00:01:51,160 --> 00:01:54,240
定義を表す文字列
辞書内の単語の。

36
00:01:54,240 --> 00:01:58,870
>> 我々は示すためにスマイリーフェイスを使用します
データは、ノード内に存在する場合。

37
00:01:58,870 --> 00:02:02,310
私たちの中の26の要素があります。
子配列、1インデックス

38
00:02:02,310 --> 00:02:03,690
英字あたり。

39
00:02:03,690 --> 00:02:06,570
私たちは、意義が表示されます
すぐにこのの。

40
00:02:06,570 --> 00:02:10,759
>> のルートノードを詳しく見ていきましょう
データがない私たちの図に

41
00:02:10,759 --> 00:02:14,740
で示されるように、それに関連付けられた
中スマイリーフェイスの欠如

42
00:02:14,740 --> 00:02:16,110
データ部。

43
00:02:16,110 --> 00:02:19,910
の部分から延びる矢印
子配列は、非ノードを表す

44
00:02:19,910 --> 00:02:21,640
他のノードへのポインタ。

45
00:02:21,640 --> 00:02:25,500
例えば、矢印は、から延びる
子供の二番目の要素

46
00:02:25,500 --> 00:02:28,400
手紙Bを表し、
辞書のキーにある。

47
00:02:28,400 --> 00:02:31,920
より大きな図中の
我々はBでラベルを付け

48
00:02:31,920 --> 00:02:35,810
>> より大きな図では、ときに我々に注意してください
別のノードへのポインタを描き、それ

49
00:02:35,810 --> 00:02:39,100
どこ矢じりは関係ありません
そのほかのノードを満たしています。

50
00:02:39,100 --> 00:02:43,850
このサンプル辞書トライは含まれています
二つの言葉は、そのズーム。

51
00:02:43,850 --> 00:02:47,040
それではの例を見てみましょう
キーのデータを検索する。

52
00:02:47,040 --> 00:02:50,800
>> 我々が見ていたとします
キー風呂の値を対応する。

53
00:02:50,800 --> 00:02:53,610
私たちは、ルックアップを始めましょう
ルートノードた。

54
00:02:53,610 --> 00:02:57,870
その後、我々は我々の最初の文字を取るよ
、鍵B、および対応を見つける

55
00:02:57,870 --> 00:03:00,020
私たちの子供たち配列内のスポット。

56
00:03:00,020 --> 00:03:04,490
正確に26のスポットがあることに注意してください
配列の各文字のための1中

57
00:03:04,490 --> 00:03:05,330
アルファベット。

58
00:03:05,330 --> 00:03:08,800
そして、我々は斑点が表す必要があります
順にアルファベットの文字。

59
00:03:08,800 --> 00:03:13,960
>> 私たちは、2番目のインデックスを見てみましょう
一般的にはBのインデックス1、我々の場合

60
00:03:13,960 --> 00:03:17,990
いくつかのアルファベット文字C、我々が持っている
対応するスポットを決定することができる

61
00:03:17,990 --> 00:03:21,520
使用して子配列内の
このような計算。

62
00:03:21,520 --> 00:03:25,140
私たちは、より大きな子を使用することもできます
我々は、ルックアップを提供したい場合は、アレイ

63
00:03:25,140 --> 00:03:28,380
文字の広い範囲でキー、
このような全体としての

64
00:03:28,380 --> 00:03:29,880
ASCII文字セット。

65
00:03:29,880 --> 00:03:32,630
>> この場合、ポインタ
で私達の子供·アレイ内の

66
00:03:32,630 --> 00:03:34,320
インデックス1はNULLではありません。

67
00:03:34,320 --> 00:03:36,600
だから我々は見続けます
キー風呂上り。

68
00:03:36,600 --> 00:03:40,130
我々はこれまでに、nullポインタが発生した場合
子供の適切な箇所に

69
00:03:40,130 --> 00:03:43,230
配列我々はノードを横断しながら、
その後、我々はその我々が言うことがあるでしょう

70
00:03:43,230 --> 00:03:45,630
そのキーの何かを見つけることができませんでした。

71
00:03:45,630 --> 00:03:49,370
>> 今、私たちは第二の手紙を取るよ
当社の主要A、および以下継続

72
00:03:49,370 --> 00:03:52,400
私たちまで、このように、ポインタ
当社の主要の最後に到達する。

73
00:03:52,400 --> 00:03:56,530
私たちはせずに、キーの最後に到達した場合
任意の行き止まり、ヌルポインタを打つ、

74
00:03:56,530 --> 00:03:59,730
我々だけにして、ここではそうであるように
もう一つのことをチェックする必要があります。

75
00:03:59,730 --> 00:04:02,110
このキーは、実際には
辞書内の？

76
00:04:02,110 --> 00:04:07,660
>> もしそうなら、我々はAだけでなく、値を見つける必要があります
私たちの図中のスマイリーフェイスアイコンを場所

77
00:04:07,660 --> 00:04:08,750
言葉は終了します。

78
00:04:08,750 --> 00:04:12,270
何か他のものがあった場合に格納されている
データは、その後、我々はそれを返すことができます。

79
00:04:12,270 --> 00:04:16,500
例えば、キー動物園ではありません
我々が持っている可能性にもかかわらず、辞書、

80
00:04:16,500 --> 00:04:19,810
これまでにすることなく、このキーの終わりに達し
我ながら、NULLポインタを打つ

81
00:04:19,810 --> 00:04:21,089
トライを反復。

82
00:04:21,089 --> 00:04:25,436
>> 我々は主要なお風呂を検索しようとすると、
第二の最後のノードの配列インデックスに、

83
00:04:25,436 --> 00:04:28,750
、文字Hになり、対応する
NULLポインタを開催しています。

84
00:04:28,750 --> 00:04:31,120
だから、お風呂は辞書にありません。

85
00:04:31,120 --> 00:04:34,800
だからトライは、キーという点で独特である
明示的に保存されることはありません

86
00:04:34,800 --> 00:04:36,650
データ構造。

87
00:04:36,650 --> 00:04:38,810
では、どのように何かを挿入しない
トライへ？

88
00:04:38,810 --> 00:04:41,780
>> キーを挿入してみましょう
私たちのトライに動物園があります。

89
00:04:41,780 --> 00:04:46,120
覚えておいて、そのノードのスマイリーフェイス
簡単な、コードに対応することができる

90
00:04:46,120 --> 00:04:50,170
その動物園を示すブール値
辞書にあるか、それができた

91
00:04:50,170 --> 00:04:53,710
我々より多くの情報に対応
キー動物園に関連付ける、

92
00:04:53,710 --> 00:04:56,860
の定義のような
単語または何か他のもの。

93
00:04:56,860 --> 00:05:00,350
ある意味では、プロセスは、挿入する
トライへ何かに似ている

94
00:05:00,350 --> 00:05:02,060
トライで何かを調べる。

95
00:05:02,060 --> 00:05:05,720
>> 我々は再びルートノードから始めましょう、
に対応する次のポインタ

96
00:05:05,720 --> 00:05:07,990
当社の主要の手紙。

97
00:05:07,990 --> 00:05:11,310
幸いなことに、我々はポインタをたどることができました
私たちに達するまで、すべての道

98
00:05:11,310 --> 00:05:12,770
キーの最後。

99
00:05:12,770 --> 00:05:16,480
動物園は、単語の接頭語であるため、
のメンバーである、ズーム、

100
00:05:16,480 --> 00:05:19,440
辞書には、我々はする必要はありません
任意の新しいノードを割り当てます。

101
00:05:19,440 --> 00:05:23,140
>> 我々はそれを示すためにノードを変更することができます
につながる文字のパス

102
00:05:23,140 --> 00:05:25,360
それが私たちの辞書内のキーを表します。

103
00:05:25,360 --> 00:05:28,630
それでは、挿入してみましょう
トライにキーBATH。

104
00:05:28,630 --> 00:05:32,260
私たちは、ルート·ノードから開始します
そして、再びポインタに従ってください。

105
00:05:32,260 --> 00:05:35,620
しかし、このような状況では、我々は死者を打つ
我々が得ることができるしている前に終了

106
00:05:35,620 --> 00:05:36,940
キーの最後。

107
00:05:36,940 --> 00:05:40,980
今、我々はいくつかの新しいを割り当てる必要があります
ノードは、新しいものを割り当てる必要があります

108
00:05:40,980 --> 00:05:43,660
残りの各ノードのための
当社の主要の手紙。

109
00:05:43,660 --> 00:05:46,740
>> この場合、我々だけが必要
1新しいノードを割り当てます。

110
00:05:46,740 --> 00:05:50,590
その後、我々は、H·インデックスを作成する必要があります
この新しいノードを参照。

111
00:05:50,590 --> 00:05:54,070
もう一度、我々は、ノードを変更することができます
文字のパスを示している

112
00:05:54,070 --> 00:05:57,120
それにつながることを表す
私たちのディクショナリのキー。

113
00:05:57,120 --> 00:06:00,730
漸近約レッツ理由
これらのための私たちの手続きの複雑さ

114
00:06:00,730 --> 00:06:02,110
2事業。

115
00:06:02,110 --> 00:06:06,420
>> 我々は両方のケースで数いることがわかり
我々のアルゴリズムがかかった手順

116
00:06:06,420 --> 00:06:09,470
の数に比例
キーワードの文字。

117
00:06:09,470 --> 00:06:10,220
そう。

118
00:06:10,220 --> 00:06:13,470
あなたが単語を検索したいとき
あなただけを反復処理する必要がトライ

119
00:06:13,470 --> 00:06:17,100
文字1つずつ必要になるまでのどちらか
単語の最後に到達するか、

120
00:06:17,100 --> 00:06:19,060
トライで行き止まりにヒット。

121
00:06:19,060 --> 00:06:22,470
>> そして、あなたはキーを挿入したいとき
使用してトライへと値のペア

122
00:06:22,470 --> 00:06:26,250
我々は議論の手順、最悪の場合
新しいノードを割り当てる必要があります

123
00:06:26,250 --> 00:06:27,550
各文字。

124
00:06:27,550 --> 00:06:31,290
そして、我々はその割り当てを仮定します
一定時間操作があ​​る。

125
00:06:31,290 --> 00:06:35,850
我々は、キーの長さであると仮定しそうである場合
固定された定数の両方で囲まれた

126
00:06:35,850 --> 00:06:39,400
挿入と見上げる一定である
トライの時間操作。

127
00:06:39,400 --> 00:06:42,930
>> 私たちは、この仮定をしない場合は、その
キーの長さは固定で囲まれ

128
00:06:42,930 --> 00:06:46,650
定数は、挿入と見上げる、
最悪の場合には、線形である

129
00:06:46,650 --> 00:06:48,240
キーの長さ。

130
00:06:48,240 --> 00:06:51,800
項目の数が格納されていることに注意してください
トライでルックアップには影響しません

131
00:06:51,800 --> 00:06:52,820
または挿入時間。

132
00:06:52,820 --> 00:06:55,360
それが唯一の影響を受けているの
キーの長さ。

133
00:06:55,360 --> 00:06:59,300
>> これとは対照的に、たとえば、にエントリを追加する
ハッシュテーブルは作成する傾向がある

134
00:06:59,300 --> 00:07:01,250
未来が遅く調べる。

135
00:07:01,250 --> 00:07:04,520
これは、最初は魅力的に聞こえるかもしれないが、
我々は心に留めておくべきこと

136
00:07:04,520 --> 00:07:08,740
有利な漸近的複雑さはない
実際には、データをその意味

137
00:07:08,740 --> 00:07:11,410
構造は必然である
非難を超えた。

138
00:07:11,410 --> 00:07:15,860
我々はまた、保存するためにそれを考慮する必要があります
我々が必要とトライ中の単語、最悪の中

139
00:07:15,860 --> 00:07:19,700
ケース、ノード数に比例
単語自体の長さに。

140
00:07:19,700 --> 00:07:21,880
>> 試みは、多くのスペースを使用する傾向がある。

141
00:07:21,880 --> 00:07:25,620
すなわち、ハッシュテーブルとは対照的だ
私たちは、1つの新しいノードを必要な場所

142
00:07:25,620 --> 00:07:27,940
いくつかのキーと値のペアを格納します。

143
00:07:27,940 --> 00:07:31,370
今、再び理論的には、大きなスペース
消費量が大きいように見えるしていません

144
00:07:31,370 --> 00:07:34,620
特に現代のことを考えると契約、
コンピュータはギガバイトを持っており、

145
00:07:34,620 --> 00:07:36,180
メモリのギガバイト。

146
00:07:36,180 --> 00:07:39,200
しかし、それは、我々はまだ持っていることが判明
メモリ使用量を気にすると

147
00:07:39,200 --> 00:07:42,540
のための組織
現代のコンピュータからパフォーマンス、

148
00:07:42,540 --> 00:07:46,960
下の場所でのメカニズムを持っている
メモリアクセスを高速化するフード。

149
00:07:46,960 --> 00:07:51,180
>> しかし、これらのメカニズムは、最高のときに動作
メモリアクセスはコンパクトに作られてい

150
00:07:51,180 --> 00:07:52,810
領域または地域。

151
00:07:52,810 --> 00:07:55,910
とトライのノードが存在する可能性が
そのヒープ内の任意の場所。

152
00:07:55,910 --> 00:07:58,390
しかし、これらはトレードオフである
我々は考慮しなければならないこと。

153
00:07:58,390 --> 00:08:01,440
>> データを選択する際に、以下のことを覚えている
特定のタスクのための構造、私たち

154
00:08:01,440 --> 00:08:04,420
どのような考えなければならない
操作は、データ構造は、必要に

155
00:08:04,420 --> 00:08:07,140
サポートとどのくらいの性能
それらの各々の

156
00:08:07,140 --> 00:08:09,080
操作は、私たちにとって重要。

157
00:08:09,080 --> 00:08:11,300
これらの操作でもよい
ちょうど超えて拡張

158
00:08:11,300 --> 00:08:13,430
基本的なルックアップおよび挿入。

159
00:08:13,430 --> 00:08:17,010
我々は親切を実装したいとし
オートコンプリート機能は、多くの

160
00:08:17,010 --> 00:08:18,890
Googleのように検索エンジンがありません。

161
00:08:18,890 --> 00:08:22,210
つまり、すべてのキーを返し、
潜在的にどの値

162
00:08:22,210 --> 00:08:24,130
指定された接頭辞が付いています。

163
00:08:24,130 --> 00:08:27,050
>> トライは一意に便利です
この動作を行います。

164
00:08:27,050 --> 00:08:29,890
これは、反復処理するために簡単です
各文字のためのトライ

165
00:08:29,890 --> 00:08:30,950
接頭辞。

166
00:08:30,950 --> 00:08:33,559
ただ見上げる動作と同様に、
私たちは、ポインタをたどることができ

167
00:08:33,559 --> 00:08:35,400
文字単位。

168
00:08:35,400 --> 00:08:38,659
その後、我々は最後に到着したとき
接頭辞は、反復処理ができ

169
00:08:38,659 --> 00:08:42,049
データ構造の残りの部分
キーのいずれかを超えて以来、

170
00:08:42,049 --> 00:08:43,980
この点は、接頭辞を持っている。

171
00:08:43,980 --> 00:08:47,670
>> それは、このリストを得ることも簡単です
以来、アルファベット順に

172
00:08:47,670 --> 00:08:50,970
子配列の要素
アルファベット順に並べられます。

173
00:08:50,970 --> 00:08:54,420
だから、うまくいけば、検討します
寄付は、トライをしようとします。

174
00:08:54,420 --> 00:08:56,085
私はケビン·シュミットだし、これはCS50である。

175
00:08:56,085 --> 00:08:58,745

176
00:08:58,745 --> 00:09:00,790
>> ああ、これが始まりです
衰退。

177
00:09:00,790 --> 00:09:01,350
ごめんなさい。

178
00:09:01,350 --> 00:09:01,870
申し訳ありません。

179
00:09:01,870 --> 00:09:02,480
申し訳ありません。

180
00:09:02,480 --> 00:09:03,130
申し訳ありません。

181
00:09:03,130 --> 00:09:03,950
>> ストライク4。

182
00:09:03,950 --> 00:09:04,360
私は思います。

183
00:09:04,360 --> 00:09:05,280
申し訳ありません。

184
00:09:05,280 --> 00:09:06,500
申し訳ありません。

185
00:09:06,500 --> 00:09:07,490
申し訳ありません。

186
00:09:07,490 --> 00:09:12,352
誰が人を作るために残念
これは夢中に編集することがあります。

187
00:09:12,352 --> 00:09:13,280
>> 申し訳ありません。

188
00:09:13,280 --> 00:09:13,880
申し訳ありません。

189
00:09:13,880 --> 00:09:15,080
申し訳ありません。

190
00:09:15,080 --> 00:09:15,680
申し訳ありません。

191
00:09:15,680 --> 00:09:16,280
>> スピーカ1：よくやった。

192
00:09:16,280 --> 00:09:17,530
それは本当によく行われていた。

193
00:09:17,530 --> 00:09:18,430