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
道格·勞埃德：所以我們一直在緩慢接近
而接近該數據的聖杯

4
00:00:08,550 --> 00:00:13,050
結構，一個我們可以插入
成，刪除，並查找

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
並沒有兩段數據
有完全相同的路線圖

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
這是兩個相同的塊
數據吧，我們期待通過。

57
00:02:47,430 --> 00:02:49,880
但除此之外，任何
兩個數據是

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
所有年大學
將要四位數字。

67
00:03:15,380 --> 00:03:19,840
因此，我們將使用這四個數字來
導航通過這個數據結構。

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
對應的大學
到那個鍵，這四個數字。

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
>> 和這些數據的內
結構有兩片。

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
這是例子，我
在我的很多影片使用

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個國家
指針指向為null。

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
這確實兩個選項。

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
確定。

162
00:07:29,700 --> 00:07:31,810
>> 現在，1路目前為空。

163
00:07:31,810 --> 00:07:35,920
所以，如果我想繼續沿著這條道路
插入這個元素為線索，

164
00:07:35,920 --> 00:07:42,040
我對malloc一個新的節點，有1
點在那裡，然後我好去。

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不再指向空。

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
因此，在這點上，所有的餘
真正需要做的是說好。

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
我們要做兩個插入。

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
所以，我必須作出一個自己。

257
00:11:06,370 --> 00:11:09,360
>> 所以，我的malloc一個新的節點
並具有0點出現。

258
00:11:09,360 --> 00:11:12,770
再一次，我的malloc一個
新的節點，並有一個點出現。

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
在這個例子中，我們使用的是在這裡，
這些年來始終是四位數字。

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
往下看，做一個最後的確認。

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