1
00:00:00,000 --> 00:00:02,000
[Powered by Google Translate] [二進制搜索]

2
00:00:02,000 --> 00:00:04,000
[帕特里克·施密德 - 哈佛大學]

3
00:00:04,000 --> 00:00:07,000
[這是CS50。 -  CS50.TV]

4
00:00:07,000 --> 00:00:09,000
>> 如果我給你的迪士尼人物名稱按字母順序排列的列表

5
00:00:09,000 --> 00:00:11,000
問你找到米老鼠，

6
00:00:11,000 --> 00:00:13,000
你會如何去這樣做呢？

7
00:00:13,000 --> 00:00:15,000
一個顯而易見的方法將是從開始掃描列表

8
00:00:15,000 --> 00:00:18,000
並檢查每一個名字，看它是否是米奇。

9
00:00:18,000 --> 00:00:22,000
但是，當你閱讀阿拉丁，愛麗絲，碧浪，等等，

10
00:00:22,000 --> 00:00:25,000
你很快就會意識到，在前面的列表是不是一個好主意。

11
00:00:25,000 --> 00:00:29,000
好吧，也許你應該開始從列表末尾向後工作。

12
00:00:29,000 --> 00:00:33,000
現在你看泰山，史迪仔，白雪公主，等等。

13
00:00:33,000 --> 00:00:36,000
不過，這似乎並不像最好的方式去了解它。

14
00:00:36,000 --> 00:00:38,000
>> 那麼，另一種方式，你可以去這樣做的，是盡量縮小

15
00:00:38,000 --> 00:00:41,000
名稱的列表，你必須看。

16
00:00:41,000 --> 00:00:43,000
既然你知道，他們是按字母順序排列，

17
00:00:43,000 --> 00:00:45,000
在中間的列表中，你可以看名字

18
00:00:45,000 --> 00:00:49,000
檢查，如果米老鼠這個名字之前或之後。

19
00:00:49,000 --> 00:00:51,000
在第二列中的最後一個名稱綜觀

20
00:00:51,000 --> 00:00:54,000
你會意識到M的米奇在J茉莉，

21
00:00:54,000 --> 00:00:57,000
所以，你會簡單地忽略上半年的列表。

22
00:00:57,000 --> 00:00:59,000
然後，你可能會在頂部的最後一列

23
00:00:59,000 --> 00:01:02,000
，並認為它與長發姑娘開始。

24
00:01:02,000 --> 00:01:06,000
米奇之前，長發姑娘，看起來我們可以忽略的最後一列。

25
00:01:06,000 --> 00:01:08,000
繼續搜索策略，你很快就會發現，米奇

26
00:01:08,000 --> 00:01:11,000
是在其它的名稱列表中的第一個一半的

27
00:01:11,000 --> 00:01:14,000
終於找到米奇隱藏在梅林和米妮之間。

28
00:01:14,000 --> 00:01:17,000
>> 你剛才做的基本上是二進制搜索。

29
00:01:17,000 --> 00:01:22,000
正如這個名字所暗示的，它執行它的搜索策略，在一個二進制的問題。

30
00:01:22,000 --> 00:01:24,000
這是什麼意思呢？

31
00:01:24,000 --> 00:01:27,000
那麼，給出一個列表排序的項目，二進制搜索算法使得一個二進制的決定 - 

32
00:01:27,000 --> 00:01:33,000
左或右，大於或小於，之前或之後的字母順序 - 在每一個點。

33
00:01:33,000 --> 00:01:35,000
現在，我們有一個名字伴隨著本次搜索算法，

34
00:01:35,000 --> 00:01:38,000
讓我們來看看另一個例子，但這次的列表排序的數字。

35
00:01:38,000 --> 00:01:43,000
說我們正在為數字144在此列表中的排序號碼。

36
00:01:43,000 --> 00:01:46,000
就像以前一樣，我們發現在中間的數字 - 

37
00:01:46,000 --> 00:01:50,000
在這種情況下是13  - 和看到，如果144是大於或小於13。

38
00:01:50,000 --> 00:01:54,000
因為它是明顯大於13，我們可以忽略一切，這是13或更小

39
00:01:54,000 --> 00:01:57,000
只集中在剩下的一半。

40
00:01:57,000 --> 00:01:59,000
因為我們現在有一個偶數留下的物品，

41
00:01:59,000 --> 00:02:01,000
我們簡單地選擇一個數字，接近中間。

42
00:02:01,000 --> 00:02:03,000
在這種情況下，我們選擇55。

43
00:02:03,000 --> 00:02:06,000
我們可以很容易地選擇89。

44
00:02:06,000 --> 00:02:11,000
好吧。同樣，144是大於55，所以我們去的權利。

45
00:02:11,000 --> 00:02:14,000
幸運的是，在未來的中間數是144，

46
00:02:14,000 --> 00:02:16,000
我們正在尋找的。

47
00:02:16,000 --> 00:02:21,000
因此，為了找到144使用二進制搜索，我們可以找到它的只有3個步驟。

48
00:02:21,000 --> 00:02:24,000
如果我們將使用線性搜索，將採取12個步驟。

49
00:02:24,000 --> 00:02:28,000
事實上，由於這個搜索方法的項目數減半

50
00:02:28,000 --> 00:02:31,000
它的每一步看，會發現它正在尋找的項目

51
00:02:31,000 --> 00:02:35,000
大約在日誌列表中的項目的數目。

52
00:02:35,000 --> 00:02:37,000
現在，我們已經看到了2個例子，讓我們一起來看看

53
00:02:37,000 --> 00:02:41,000
一個遞歸函數的偽代碼實現二進制搜索。

54
00:02:41,000 --> 00:02:44,000
從頂部開始，我們可以看到，我們必須找到一個函數，它接受4個參數：

55
00:02:44,000 --> 00:02:47,000
鍵，陣列，最小和最大。

56
00:02:47,000 --> 00:02:51,000
最關鍵的是我們正在尋找的數字，所以144在前面的例子。

57
00:02:51,000 --> 00:02:54,000
數組是數字列表，我們正在尋找。

58
00:02:54,000 --> 00:02:57,000
min和max是最小和最大位置的指數，其中

59
00:02:57,000 --> 00:02:59,000
我們正在尋找。

60
00:02:59,000 --> 00:03:03,000
因此，當我們開始的時候，min將是零和最大將是最大的索引的數組。

61
00:03:03,000 --> 00:03:07,000
當我們縮小搜索範圍，我們將更新的最小值和最大值

62
00:03:07,000 --> 00:03:10,000
的範圍內，我們仍然往裡看。

63
00:03:10,000 --> 00:03:12,000
>> 讓我們先跳到最有趣的部分。

64
00:03:12,000 --> 00:03:14,000
我們做的第一件事是找到中點，

65
00:03:14,000 --> 00:03:19,000
該指數中間的最小值和最大值的數組，我們還在考慮。

66
00:03:19,000 --> 00:03:22,000
然後我們看一下，中點位置的值的數組

67
00:03:22,000 --> 00:03:25,000
看到，我們正在尋找的數字，如果是小於該鍵。

68
00:03:25,000 --> 00:03:27,000
如果在該位置上的數目比較少，

69
00:03:27,000 --> 00:03:31,000
那麼它意味著關鍵是大於所有編號，以該位置的左側的。

70
00:03:31,000 --> 00:03:33,000
因此，我們可以稱之為二進制搜索功能，

71
00:03:33,000 --> 00:03:36,000
但這次更新的最小值和最大值參數只讀取一半

72
00:03:36,000 --> 00:03:40,000
也就是大於或等於的值，我們剛剛看到的。

73
00:03:40,000 --> 00:03:44,000
在另一方面，如果該鍵的數目小於在當前陣列中點，

74
00:03:44,000 --> 00:03:47,000
我們想要去的左側，而忽略所有的數字是更大的。

75
00:03:47,000 --> 00:03:52,000
同樣，我們稱之為二進制搜索，但這個時間範圍內的最小值和最大值更新

76
00:03:52,000 --> 00:03:54,000
以僅包括下半部。

77
00:03:54,000 --> 00:03:57,000
如果陣列中的當前的中點處的值既不是

78
00:03:57,000 --> 00:04:01,000
大於也不小於鍵，那麼它必須是相等的關鍵。

79
00:04:01,000 --> 00:04:05,000
因此，我們可以簡單地返回當前的中點指數，我們就大功告成了。

80
00:04:05,000 --> 00:04:09,000
最後，這裡此檢查為的情況下，數字

81
00:04:09,000 --> 00:04:11,000
實際上不是在數組中的數字，我們正在尋找。

82
00:04:11,000 --> 00:04:14,000
如果在最大的範圍內，我們正在尋找的指數

83
00:04:14,000 --> 00:04:17,000
高於最低要求是越來越少，這意味著我們已經走得太遠了。

84
00:04:17,000 --> 00:04:20,000
由於數字輸入數組中，我們返回-1

85
00:04:20,000 --> 00:04:24,000
表明，沒有被發現。

86
00:04:24,000 --> 00:04:26,000
>> 您可能已經注意到了這個算法的工作，

87
00:04:26,000 --> 00:04:28,000
的號碼列表進行排序。

88
00:04:28,000 --> 00:04:31,000
換句話說，我們只能找到144使用二進制搜索

89
00:04:31,000 --> 00:04:34,000
如果所有的數字都下令從最低到最高。

90
00:04:34,000 --> 00:04:38,000
如果不是這樣的情況下，我們將無法排除一半的數字在每個步驟。

91
00:04:38,000 --> 00:04:40,000
因此，我們有2個選擇。

92
00:04:40,000 --> 00:04:43,000
要么我們可以採取一個無序的列表，並使用二進制搜索，排序前，

93
00:04:43,000 --> 00:04:48,000
或者我們可以肯定，我們將號碼添加到列表中的數字進行排序。

94
00:04:48,000 --> 00:04:50,000
因此，而不是排序的時候，我們要搜索，

95
00:04:50,000 --> 00:04:53,000
為什麼不排序的列表，在任何時候都保持？

96
00:04:53,000 --> 00:04:57,000
>> 同時允許排序的方式，讓一個數字列表

97
00:04:57,000 --> 00:04:59,000
一個添加或移動號碼從這個名單

98
00:04:59,000 --> 00:05:02,000
是通過使用一種稱為二叉搜索樹。

99
00:05:02,000 --> 00:05:05,000
二叉搜索樹是一種數據結構，有3個屬性。

100
00:05:05,000 --> 00:05:09,000
首先，左子樹中的任何節點只包含值小於

101
00:05:09,000 --> 00:05:11,000
或等於節點的值。

102
00:05:11,000 --> 00:05:15,000
其次，節點的右子樹中包含的值大於

103
00:05:15,000 --> 00:05:17,000
或等於節點的值。

104
00:05:17,000 --> 00:05:20,000
以及最後，無論是左和右子樹的所有節點

105
00:05:20,000 --> 00:05:23,000
二叉搜索樹。

106
00:05:23,000 --> 00:05:26,000
讓我們看一個例子，與我們之前使用的相同的號碼。

107
00:05:26,000 --> 00:05:30,000
對於那些你從來沒有見過計算機科學樹前，

108
00:05:30,000 --> 00:05:34,000
首先，讓我告訴你，計算機科學樹是向下增長的。

109
00:05:34,000 --> 00:05:36,000
是的，不像你習慣的樹木，

110
00:05:36,000 --> 00:05:38,000
計算機科學樹的根是在頂部，

111
00:05:38,000 --> 00:05:41,000
和葉子都在底部。

112
00:05:41,000 --> 00:05:45,000
每個小方塊被稱為一個節點，節點由邊緣彼此連接。

113
00:05:45,000 --> 00:05:48,000
因此，這棵樹的根是一個節點值的值13，

114
00:05:48,000 --> 00:05:52,000
具有2個孩子的節點的值5和34。

115
00:05:52,000 --> 00:05:57,000
子樹是樹，形成整個樹在第。

116
00:05:57,000 --> 00:06:03,000
>> 例如，左邊的子樹的節點3是建立的樹由節點0，1和2。

117
00:06:03,000 --> 00:06:06,000
所以，如果我們回到一個二叉搜索樹的性質，

118
00:06:06,000 --> 00:06:09,000
我們可以看到，在樹中的每個節點符合所有3個屬性，即，

119
00:06:09,000 --> 00:06:15,000
左子樹僅包含節點的值小於或等於的值;

120
00:06:15,000 --> 00:06:16,000
所有節點的右子樹

121
00:06:16,000 --> 00:06:19,000
只包含節點的值大於或等於值;

122
00:06:19,000 --> 00:06:25,000
左，右子樹的所有節點也有二叉​​搜索樹。

123
00:06:25,000 --> 00:06:28,000
雖然這棵樹看起來不一樣，這是一個有效的二叉搜索樹

124
00:06:28,000 --> 00:06:30,000
對於同一組的數字。

125
00:06:30,000 --> 00:06:32,000
事實上，有許多可能的方式，你可以創建

126
00:06:32,000 --> 00:06:35,000
從這些數字的一個有效的二叉搜索樹。

127
00:06:35,000 --> 00:06:38,000
好吧，讓我們回到我們創建的第一個。

128
00:06:38,000 --> 00:06:40,000
所以，我們可以做什麼與這些樹呢？

129
00:06:40,000 --> 00:06:44,000
好了，我們可以很簡單地找到的最低值和最高值。

130
00:06:44,000 --> 00:06:46,000
可以找到的最小值總是要在左邊

131
00:06:46,000 --> 00:06:48,000
直到有沒有更多的節點訪問。

132
00:06:48,000 --> 00:06:53,000
相反，找到的最大的僅僅只是下山的權利在每個時間。

133
00:06:54,000 --> 00:06:56,000
>> 查找任何其他數目的最小值或最大值

134
00:06:56,000 --> 00:06:58,000
也很容易。

135
00:06:58,000 --> 00:07:00,000
假設我們正在尋找數89。

136
00:07:00,000 --> 00:07:03,000
我們簡單地檢查每個節點的值，向左或向右，

137
00:07:03,000 --> 00:07:06,000
根據節點的值是否小於或大於

138
00:07:06,000 --> 00:07:08,000
我們正在尋找的。

139
00:07:08,000 --> 00:07:11,000
所以，從13根，我們可以看到，89，

140
00:07:11,000 --> 00:07:13,000
所以我們去正確的。

141
00:07:13,000 --> 00:07:16,000
然後，我們看到了34節點，我們再次去正確的。

142
00:07:16,000 --> 00:07:20,000
89大於55，所以我們繼續去合適。

143
00:07:20,000 --> 00:07:24,000
然後，我們來到了一個節點的值144，和去左邊。

144
00:07:24,000 --> 00:07:26,000
你瞧，89是正確的。

145
00:07:26,000 --> 00:07:31,000
>> 我們可以做的另一件事，是打印出所有進行中序遍歷。

146
00:07:31,000 --> 00:07:35,000
中序遍歷是指打印任何事物的左子樹

147
00:07:35,000 --> 00:07:37,000
隨後由打印節點本身

148
00:07:37,000 --> 00:07:40,000
然後印刷一切在右子樹。

149
00:07:40,000 --> 00:07:43,000
例如，讓我們最喜歡的二叉搜索樹

150
00:07:43,000 --> 00:07:46,000
的排序順序打印出來的數字。

151
00:07:46,000 --> 00:07:49,000
首先，我們在13根的，但我們必須在打印前13打印出

152
00:07:49,000 --> 00:07:51,000
一切都在左子樹。

153
00:07:51,000 --> 00:07:55,000
因此，我們轉到5。我們仍然有更深入的倒在了樹，直到我們找到了最左邊的節點，

154
00:07:55,000 --> 00:07:57,000
這是零。

155
00:07:57,000 --> 00:08:00,000
印刷零後，我們回去到1，並打印了這一點。

156
00:08:00,000 --> 00:08:03,000
然後我們去的右子樹，也就是2，打印了這一點。

157
00:08:03,000 --> 00:08:05,000
現在，我們已經完成了該子樹，

158
00:08:05,000 --> 00:08:07,000
我們可以回去了3個，並把它打印出來。

159
00:08:07,000 --> 00:08:11,000
持續回升，我們打印5和8。

160
00:08:11,000 --> 00:08:13,000
現在，我們已經完成了整個左子樹，

161
00:08:13,000 --> 00:08:17,000
我們可以打印出13個，並開始工作的右子樹。

162
00:08:17,000 --> 00:08:21,000
我們跳了34，但我們必須在打印前34打印出其左子樹。

163
00:08:21,000 --> 00:08:27,000
所以，我們打印出21，然後打印出34，訪問右子樹。

164
00:08:27,000 --> 00:08:31,000
由於55沒有左子樹，我們打印出來，並繼續其右子樹。

165
00:08:31,000 --> 00:08:36,000
144有一個左子樹，所以我們打印出89，其次是144，

166
00:08:36,000 --> 00:08:39,000
233，最後最右邊的節點。

167
00:08:39,000 --> 00:08:44,000
有你有它，所有的號碼都打印出來，以便從最低到最高。

168
00:08:44,000 --> 00:08:47,000
>> 添加的樹是什麼，以及相對無痛的。

169
00:08:47,000 --> 00:08:51,000
我們要做的是確保我們按照二叉搜索樹性能

170
00:08:51,000 --> 00:08:53,000
然後插入值有空間的地方。

171
00:08:53,000 --> 00:08:55,000
比方說，我們要插入的值是7。

172
00:08:55,000 --> 00:08:58,000
自7是小於13，我們去左邊。

173
00:08:58,000 --> 00:09:01,000
但它大於5，所以我們遍歷的權利。

174
00:09:01,000 --> 00:09:04,000
由於它是小於8和圖8是一個葉節點，我們添加7至8的左子。

175
00:09:04,000 --> 00:09:09,000
瞧！我們已經添加了一個數字，我們的二叉搜索樹。

176
00:09:09,000 --> 00:09:12,000
>> 如果我們可以添加的東西，我們最好是能夠刪除的東西。

177
00:09:12,000 --> 00:09:14,000
不幸的是，對我們來說，刪除是一個有點複雜 - 

178
00:09:14,000 --> 00:09:16,000
雖然不大，但只是一點點。

179
00:09:16,000 --> 00:09:18,000
有3種不同的情況下，我們要考慮的

180
00:09:18,000 --> 00:09:21,000
刪除元素時，從二叉搜索樹。

181
00:09:21,000 --> 00:09:24,000
首先，最簡單的情況是，該元素是一個葉節點。

182
00:09:24,000 --> 00:09:27,000
在這種情況下，我們簡單地將其刪除，並繼續與我們的業務。

183
00:09:27,000 --> 00:09:30,000
假設我們要刪除我們剛才添加的7。

184
00:09:30,000 --> 00:09:34,000
好了，我們只要找到它，刪除它，就是這樣。

185
00:09:35,000 --> 00:09:37,000
接下來的情況是，如果節點只有1名兒童。

186
00:09:37,000 --> 00:09:40,000
在這裡，我們可以刪除該節點，但我們首先必須確保

187
00:09:40,000 --> 00:09:42,000
連接的子樹，現在是離開父母雙亡的孤兒

188
00:09:42,000 --> 00:09:44,000
節點的父節點，我們只是刪除了。

189
00:09:44,000 --> 00:09:47,000
假設我們從我們的樹，要刪除3。

190
00:09:47,000 --> 00:09:50,000
我們把該節點的子元素，並將它附加到節點的父節點。

191
00:09:50,000 --> 00:09:54,000
在這種情況下，我們現在將1到5。

192
00:09:54,000 --> 00:09:57,000
這沒有問題，因為我們知道，根據二叉搜索樹的性質，

193
00:09:57,000 --> 00:10:01,000
3的左子樹，一切均小於5。

194
00:10:01,000 --> 00:10:05,000
現在，3的子樹的照顧，我們可以將其刪除。

195
00:10:05,000 --> 00:10:08,000
第三個和最後的情況是最複雜的。

196
00:10:08,000 --> 00:10:11,000
這是我們要刪除的節點有2個孩子的情況下。

197
00:10:11,000 --> 00:10:15,000
為了做到這一點，我們首先要找到的節點有一個最大的價值，

198
00:10:15,000 --> 00:10:18,000
交換了兩下，然後刪除有問題的節點。

199
00:10:18,000 --> 00:10:22,000
請注意，節點，下一個最大的值不能有2個孩子

200
00:10:22,000 --> 00:10:26,000
因為它的左孩子為下一個最大的將是一個更好的人選。

201
00:10:26,000 --> 00:10:30,000
因此，刪除一個節點有2個孩子，2個節點交換，

202
00:10:30,000 --> 00:10:33,000
然後刪除處理由1 2上述規則。

203
00:10:33,000 --> 00:10:37,000
例如，讓我們說，我們要刪除的根節點，13。

204
00:10:37,000 --> 00:10:39,000
我們做的第一件事情是，我們發現在樹中的下一個最大的價值

205
00:10:39,000 --> 00:10:41,000
其中，在這種情況下，為21。

206
00:10:41,000 --> 00:10:46,000
然後，我們交換的2個節點，13葉和21個中心組節點。

207
00:10:46,000 --> 00:10:49,000
現在，我們可以簡單地刪除13。

208
00:10:50,000 --> 00:10:53,000
>> 正如前面提到的，有許多可能的方法來進行有效的二叉搜索樹。

209
00:10:53,000 --> 00:10:56,000
不幸的是，對我們來說，有些是比別人差。

210
00:10:56,000 --> 00:10:59,000
例如，會發生什麼事時，我們建立了一個二叉搜索樹

211
00:10:59,000 --> 00:11:01,000
從排序列表中的號碼嗎？

212
00:11:01,000 --> 00:11:04,000
所有的數字都只是添加到右邊的每一步。

213
00:11:04,000 --> 00:11:06,000
當我們要搜索一個數字，

214
00:11:06,000 --> 00:11:08,000
我們別無選擇，只有看的權利，在每一個步驟。

215
00:11:08,000 --> 00:11:11,000
這是不是比在所有的線性搜索。

216
00:11:11,000 --> 00:11:13,000
雖然我們不會掩蓋他們在這裡，還有其他更複雜的，

217
00:11:13,000 --> 00:11:16,000
數據結構，確保不會發生這種情況。

218
00:11:16,000 --> 00:11:18,000
然而，一個簡單的事情可以做，以避免這種情況的是

219
00:11:18,000 --> 00:11:21,000
只是隨機洗牌的輸入值。

220
00:11:21,000 --> 00:11:26,000
這是極不可能的，一個偶然的機會洗牌的數字列表進行排序。

221
00:11:26,000 --> 00:11:29,000
如果是這樣的話，賭場會不會留在企業長久的。

222
00:11:29,000 --> 00:11:31,000
>> 有你有它。

223
00:11:31,000 --> 00:11:34,000
您現在所了解的二進制搜索和二叉搜索樹。

224
00:11:34,000 --> 00:11:36,000
我是帕特里克·施密德，這是CS50。

225
00:11:36,000 --> 00:11:38,000
[CS50.TV]

226
00:11:38,000 --> 00:11:43,000
一個明顯的方法是將掃描列表... [嗶]

227
00:11:43,000 --> 00:11:46,000
的項目數...是的

228
00:11:46,000 --> 00:11:50,000
[笑]

229
00:11:50,000 --> 00:11:55,000
...發布節點234 ... augh。

230
00:11:55,000 --> 00:11:58,000
>>耶！這是 -