1
00:00:00,000 --> 00:00:02,000
[Powered by Google Translate] [Binary Search]

2
00:00:02,000 --> 00:00:04,000
[Patrick Schmid - Đại học Harvard]

3
00:00:04,000 --> 00:00:07,000
[Đây là CS50. - CS50.TV]

4
00:00:07,000 --> 00:00:09,000
>> Nếu tôi đưa cho bạn một danh sách các tên nhân vật Disney trong thứ tự chữ cái

5
00:00:09,000 --> 00:00:11,000
và yêu cầu bạn tìm Mickey Mouse,

6
00:00:11,000 --> 00:00:13,000
làm thế nào bạn sẽ đi về việc này?

7
00:00:13,000 --> 00:00:15,000
Một cách rõ ràng sẽ được để quét các danh sách từ đầu

8
00:00:15,000 --> 00:00:18,000
và kiểm tra tất cả các tên để xem nếu nó là Mickey.

9
00:00:18,000 --> 00:00:22,000
Nhưng khi bạn đọc Aladdin, Alice, Ariel, và vv,

10
00:00:22,000 --> 00:00:25,000
bạn sẽ nhanh chóng nhận ra rằng bắt đầu ở phía trước của danh sách không phải là một ý tưởng tốt.

11
00:00:25,000 --> 00:00:29,000
Rồi, có lẽ bạn nên bắt đầu làm việc ngược trở lại từ cuối danh sách.

12
00:00:29,000 --> 00:00:33,000
Bây giờ bạn đọc Tarzan, Stitch, Snow White, và vv.

13
00:00:33,000 --> 00:00:36,000
Tuy nhiên, điều này không có vẻ như là cách tốt nhất để đi về nó.

14
00:00:36,000 --> 00:00:38,000
>> Vâng, một cách khác mà bạn có thể đi về việc này là cố gắng để thu hẹp

15
00:00:38,000 --> 00:00:41,000
danh sách các tên mà bạn phải nhìn vào.

16
00:00:41,000 --> 00:00:43,000
Vì bạn biết rằng họ đang có trong thứ tự chữ cái,

17
00:00:43,000 --> 00:00:45,000
bạn chỉ có thể nhìn vào những cái tên ở giữa của danh sách

18
00:00:45,000 --> 00:00:49,000
và kiểm tra xem Mickey Mouse là trước hoặc sau khi tên này.

19
00:00:49,000 --> 00:00:51,000
Nhìn vào tên cuối cùng trong cột thứ hai

20
00:00:51,000 --> 00:00:54,000
bạn sẽ nhận ra rằng M cho Mickey đến sau khi J cho Jasmine,

21
00:00:54,000 --> 00:00:57,000
vì vậy bạn chỉ đơn giản là muốn bỏ qua nửa đầu của danh sách.

22
00:00:57,000 --> 00:00:59,000
Sau đó, bạn có thể muốn nhìn vào phía trên cùng của cột cuối cùng

23
00:00:59,000 --> 00:01:02,000
và thấy rằng nó bắt đầu với Rapunzel.

24
00:01:02,000 --> 00:01:06,000
Mickey đến trước khi Rapunzel, trông giống như chúng ta có thể bỏ qua cột cuối cùng.

25
00:01:06,000 --> 00:01:08,000
Tiếp tục chiến lược tìm kiếm, bạn sẽ nhanh chóng thấy rằng Mickey

26
00:01:08,000 --> 00:01:11,000
trong nửa đầu của danh sách còn lại của tên

27
00:01:11,000 --> 00:01:14,000
và cuối cùng đã tìm thấy Mickey ẩn giữa Merlin và Minnie.

28
00:01:14,000 --> 00:01:17,000
>> Những gì bạn chỉ cần làm là về cơ bản tìm kiếm nhị phân.

29
00:01:17,000 --> 00:01:22,000
Như tên gọi này hàm ý, nó thực hiện chiến lược tìm kiếm của mình trong một vấn đề nhị phân.

30
00:01:22,000 --> 00:01:24,000
Điều này có nghĩa là gì?

31
00:01:24,000 --> 00:01:27,000
Vâng, đưa ra một danh sách các mục được sắp xếp, các thuật toán tìm kiếm nhị phân làm cho một quyết định nhị phân -

32
00:01:27,000 --> 00:01:33,000
trái hoặc phải, lớn hơn hoặc ít hơn, theo thứ tự bảng chữ cái trước hoặc sau khi tại mỗi điểm.

33
00:01:33,000 --> 00:01:35,000
Bây giờ chúng ta có một cái tên mà đi cùng với thuật toán tìm kiếm này,

34
00:01:35,000 --> 00:01:38,000
chúng ta hãy nhìn vào một ví dụ khác, nhưng lần này với một danh sách các số được sắp xếp.

35
00:01:38,000 --> 00:01:43,000
Nói rằng chúng tôi đang tìm kiếm cho số 144 trong danh sách các số được sắp xếp.

36
00:01:43,000 --> 00:01:46,000
Giống như trước đây, chúng ta thấy số đó là ở giữa -

37
00:01:46,000 --> 00:01:50,000
trong trường hợp này là 13 - và xem nếu 144 là lớn hơn hoặc nhỏ hơn 13.

38
00:01:50,000 --> 00:01:54,000
Kể từ khi nó rõ ràng là lớn hơn 13, chúng ta có thể bỏ qua tất cả mọi thứ đó là 13 hoặc ít hơn

39
00:01:54,000 --> 00:01:57,000
và chỉ tập trung vào một nửa còn lại.

40
00:01:57,000 --> 00:01:59,000
Kể từ bây giờ chúng ta có một số chẵn các mục còn lại,

41
00:01:59,000 --> 00:02:01,000
chúng tôi chỉ đơn giản là lựa chọn một số đó là gần giữa.

42
00:02:01,000 --> 00:02:03,000
Trong trường hợp này, chúng tôi chọn 55.

43
00:02:03,000 --> 00:02:06,000
Chúng tôi có thể chỉ là một cách dễ dàng lựa chọn 89.

44
00:02:06,000 --> 00:02:11,000
Okay. Một lần nữa, 144 là lớn hơn 55, do đó, chúng tôi đi đến bên phải.

45
00:02:11,000 --> 00:02:14,000
May mắn cho chúng tôi, số lượng trung tiếp theo là 144,

46
00:02:14,000 --> 00:02:16,000
chúng ta đang tìm kiếm.

47
00:02:16,000 --> 00:02:21,000
Vì vậy, để tìm 144 bằng cách sử dụng tìm kiếm nhị phân, chúng tôi có thể tìm thấy nó trong chỉ có 3 bước.

48
00:02:21,000 --> 00:02:24,000
Nếu chúng tôi đã sử dụng tìm kiếm tuyến tính ở đây, nó sẽ đưa chúng ta 12 bước.

49
00:02:24,000 --> 00:02:28,000
Như một vấn đề của thực tế, kể từ khi phương pháp tìm kiếm nửa số lượng các mục

50
00:02:28,000 --> 00:02:31,000
nó có để xem xét tại mỗi bước, nó sẽ tìm thấy mục tìm kiếm

51
00:02:31,000 --> 00:02:35,000
trong nhật ký của số lượng các mục trong danh sách.

52
00:02:35,000 --> 00:02:37,000
Bây giờ chúng ta đã nhìn thấy 2 ví dụ, chúng ta hãy xem xét

53
00:02:37,000 --> 00:02:41,000
một số giả cho một hàm đệ quy mà thực hiện tìm kiếm nhị phân.

54
00:02:41,000 --> 00:02:44,000
Bắt đầu từ trên, chúng ta thấy rằng chúng ta phải tìm một chức năng mà mất 4 đối số:

55
00:02:44,000 --> 00:02:47,000
chìa khóa, mảng, min và max.

56
00:02:47,000 --> 00:02:51,000
Điều quan trọng là số lượng mà chúng tôi đang tìm kiếm, vì vậy 144 trong ví dụ trước.

57
00:02:51,000 --> 00:02:54,000
Array là danh sách các số mà chúng tôi đang tìm kiếm.

58
00:02:54,000 --> 00:02:57,000
Min và max là các chỉ số của các vị trí tối thiểu và tối đa

59
00:02:57,000 --> 00:02:59,000
mà chúng tôi đang xem xét.

60
00:02:59,000 --> 00:03:03,000
Vì vậy, khi chúng tôi bắt đầu, min sẽ là số không và tối đa sẽ là chỉ số tối đa của mảng.

61
00:03:03,000 --> 00:03:07,000
Như chúng ta đã thu hẹp tìm kiếm, chúng tôi sẽ cập nhật min và max

62
00:03:07,000 --> 00:03:10,000
là phạm vi mà chúng tôi vẫn đang tìm kiếm.

63
00:03:10,000 --> 00:03:12,000
>> Hãy bỏ qua phần thú vị đầu tiên.

64
00:03:12,000 --> 00:03:14,000
Điều đầu tiên chúng tôi làm là tìm ra điểm giữa,

65
00:03:14,000 --> 00:03:19,000
chỉ số nằm giữa min và max của mảng mà chúng tôi vẫn đang xem xét.

66
00:03:19,000 --> 00:03:22,000
Sau đó, chúng ta nhìn vào giá trị của mảng tại vị trí đó trung điểm

67
00:03:22,000 --> 00:03:25,000
và xem nếu số lượng mà chúng ta đang tìm kiếm là quan trọng mà.

68
00:03:25,000 --> 00:03:27,000
Nếu số ở vị trí đó là ít hơn,

69
00:03:27,000 --> 00:03:31,000
sau đó nó có nghĩa chính là lớn hơn so với tất cả các số bên trái của vị trí đó.

70
00:03:31,000 --> 00:03:33,000
Vì vậy, chúng ta có thể gọi chức năng tìm kiếm nhị phân một lần nữa,

71
00:03:33,000 --> 00:03:36,000
nhưng lần này cập nhật các thông số min và max để đọc nửa

72
00:03:36,000 --> 00:03:40,000
đó là lớn hơn hoặc bằng giá trị mà chúng ta chỉ cần nhìn vào.

73
00:03:40,000 --> 00:03:44,000
Mặt khác, nếu chính là ít hơn so với số lượng tại trung điểm hiện tại của mảng,

74
00:03:44,000 --> 00:03:47,000
chúng tôi muốn đi bên trái và bỏ qua tất cả các số lớn.

75
00:03:47,000 --> 00:03:52,000
Một lần nữa, chúng ta gọi là tìm kiếm nhị phân, nhưng thời gian này với phạm vi của các min và max cập nhật

76
00:03:52,000 --> 00:03:54,000
bao gồm chỉ thấp hơn một nửa.

77
00:03:54,000 --> 00:03:57,000
Nếu giá trị tại trung điểm hiện tại trong mảng không phải là

78
00:03:57,000 --> 00:04:01,000
lớn hơn cũng không nhỏ hơn khoá, sau đó nó phải có bằng chìa khóa.

79
00:04:01,000 --> 00:04:05,000
Vì vậy, chúng tôi chỉ đơn giản là có thể quay trở lại các chỉ số trung điểm hiện tại, và chúng tôi đang thực hiện.

80
00:04:05,000 --> 00:04:09,000
Cuối cùng, việc kiểm tra này ở đây là đối với trường hợp số lượng

81
00:04:09,000 --> 00:04:11,000
không phải là thực sự trong mảng các số chúng tôi đang tìm kiếm.

82
00:04:11,000 --> 00:04:14,000
Nếu chỉ số tối đa của phạm vi mà chúng tôi đang tìm kiếm

83
00:04:14,000 --> 00:04:17,000
bao giờ ít hơn mức tối thiểu, có nghĩa là chúng ta đã đi quá xa.

84
00:04:17,000 --> 00:04:20,000
Kể từ khi con số này là không có trong mảng đầu vào, chúng tôi trở về -1

85
00:04:20,000 --> 00:04:24,000
để cho biết rằng không có gì đã được tìm thấy.

86
00:04:24,000 --> 00:04:26,000
>> Bạn có thể đã nhận thấy rằng thuật toán này để làm việc,

87
00:04:26,000 --> 00:04:28,000
danh sách các số đã được sắp xếp.

88
00:04:28,000 --> 00:04:31,000
Nói cách khác, chúng ta chỉ có thể tìm thấy 144 bằng cách sử dụng tìm kiếm nhị phân

89
00:04:31,000 --> 00:04:34,000
nếu tất cả các số được sắp xếp từ thấp nhất đến cao nhất.

90
00:04:34,000 --> 00:04:38,000
Nếu đây không phải là trường hợp, chúng tôi sẽ không thể loại trừ một nửa của con số ở mỗi bước.

91
00:04:38,000 --> 00:04:40,000
Vì vậy, chúng tôi có 2 lựa chọn.

92
00:04:40,000 --> 00:04:43,000
Hoặc là chúng ta có thể có một danh sách được phân loại và sắp xếp nó trước khi sử dụng tìm kiếm nhị phân,

93
00:04:43,000 --> 00:04:48,000
hoặc chúng tôi có thể chắc chắn rằng danh sách các số được sắp xếp như chúng ta thêm số vào nó.

94
00:04:48,000 --> 00:04:50,000
Như vậy, thay vì sắp xếp chỉ khi chúng ta phải tìm kiếm,

95
00:04:50,000 --> 00:04:53,000
tại sao không giữ danh sách được sắp xếp ở tất cả các lần?

96
00:04:53,000 --> 00:04:57,000
>> Một cách để giữ một danh sách các số được sắp xếp trong khi đồng thời cho phép

97
00:04:57,000 --> 00:04:59,000
một để thêm hoặc di chuyển số từ danh sách này

98
00:04:59,000 --> 00:05:02,000
là bằng cách sử dụng một cái gì đó gọi là cây tìm kiếm nhị phân.

99
00:05:02,000 --> 00:05:05,000
Một cây tìm kiếm nhị phân là một cấu trúc dữ liệu có 3 thuộc tính.

100
00:05:05,000 --> 00:05:09,000
Trước tiên, các cây con trái của nút bất kỳ chỉ chứa các giá trị nhỏ hơn

101
00:05:09,000 --> 00:05:11,000
hoặc bằng giá trị của nút.

102
00:05:11,000 --> 00:05:15,000
Thứ hai, bên phải cây con của một node chỉ chứa các giá trị lớn hơn

103
00:05:15,000 --> 00:05:17,000
hoặc bằng giá trị của nút.

104
00:05:17,000 --> 00:05:20,000
Và, cuối cùng, cả hai bên trái và phải subtrees của tất cả các nút

105
00:05:20,000 --> 00:05:23,000
cũng là cây tìm kiếm nhị phân.

106
00:05:23,000 --> 00:05:26,000
Hãy xem một ví dụ có cùng số chúng tôi đã sử dụng trước đó.

107
00:05:26,000 --> 00:05:30,000
Đối với những người bạn của những người chưa bao giờ thấy một cây trước khi khoa học máy tính,

108
00:05:30,000 --> 00:05:34,000
hãy để tôi bắt đầu bằng cách nói với bạn rằng một cây khoa học máy tính phát triển xuống dưới.

109
00:05:34,000 --> 00:05:36,000
Có, không giống như cây bạn đã quen với,

110
00:05:36,000 --> 00:05:38,000
gốc rễ của một cây khoa học máy tính ở đầu trang,

111
00:05:38,000 --> 00:05:41,000
và lá ở phía dưới.

112
00:05:41,000 --> 00:05:45,000
Mỗi hộp nhỏ được gọi là một nút, và các nút được kết nối với nhau bởi các cạnh.

113
00:05:45,000 --> 00:05:48,000
Vì vậy, các thư mục gốc của cây này là một giá trị nút với giá trị 13,

114
00:05:48,000 --> 00:05:52,000
trong đó có 2 trẻ em các nút với các giá trị 5 và 34.

115
00:05:52,000 --> 00:05:57,000
Cây con là cây được hình thành chỉ bằng cách nhìn vào một tiểu mục của toàn bộ cây.

116
00:05:57,000 --> 00:06:03,000
>> Ví dụ, cây con trái của nút 3 là cây được tạo ra bởi các nút 0, 1, và 2.

117
00:06:03,000 --> 00:06:06,000
Vì vậy, nếu chúng ta quay trở lại các thuộc tính của một cây tìm kiếm nhị phân,

118
00:06:06,000 --> 00:06:09,000
chúng ta thấy rằng mỗi nút trong cây phù hợp với tất cả 3 thuộc tính, cụ thể là,

119
00:06:09,000 --> 00:06:15,000
cây con trái chỉ chứa các giá trị nhỏ hơn hoặc bằng giá trị của nút;

120
00:06:15,000 --> 00:06:16,000
bên phải cây con của tất cả các nút

121
00:06:16,000 --> 00:06:19,000
chỉ chứa các giá trị lớn hơn hoặc bằng giá trị của nút;

122
00:06:19,000 --> 00:06:25,000
subtrees trái và phải của tất cả các nút cũng là cây tìm kiếm nhị phân.

123
00:06:25,000 --> 00:06:28,000
Mặc dù cây này có vẻ khác nhau, đây là một cây nhị phân tìm kiếm hợp lệ

124
00:06:28,000 --> 00:06:30,000
cho cùng một tập hợp số.

125
00:06:30,000 --> 00:06:32,000
Như một vấn đề của thực tế, có rất nhiều cách có thể là bạn có thể tạo

126
00:06:32,000 --> 00:06:35,000
một cây nhị phân tìm kiếm hợp lệ từ những con số này.

127
00:06:35,000 --> 00:06:38,000
Vâng, chúng ta hãy quay trở lại với một trong những đầu tiên chúng tôi tạo ra.

128
00:06:38,000 --> 00:06:40,000
Vì vậy, những gì chúng ta có thể làm gì với những cây này?

129
00:06:40,000 --> 00:06:44,000
Vâng, chúng tôi rất đơn giản có thể tìm thấy những giá trị tối thiểu và tối đa.

130
00:06:44,000 --> 00:06:46,000
Các giá trị tối thiểu có thể được tìm thấy bằng cách luôn luôn đi bên trái

131
00:06:46,000 --> 00:06:48,000
cho đến khi có các nút không đến thăm.

132
00:06:48,000 --> 00:06:53,000
Ngược lại, để tìm ra một tối đa chỉ đơn giản chỉ đi xuống bên phải trong từng thời điểm.

133
00:06:54,000 --> 00:06:56,000
>> Tìm kiếm bất kỳ số nào khác mà không phải là tối thiểu hoặc tối đa

134
00:06:56,000 --> 00:06:58,000
chỉ là dễ dàng.

135
00:06:58,000 --> 00:07:00,000
Nói rằng chúng tôi đang tìm kiếm cho số 89.

136
00:07:00,000 --> 00:07:03,000
Chúng tôi chỉ đơn giản là kiểm tra giá trị của mỗi nút và đi sang trái hoặc phải,

137
00:07:03,000 --> 00:07:06,000
tuỳ thuộc vào việc giá trị của nút nhỏ hơn hoặc lớn hơn

138
00:07:06,000 --> 00:07:08,000
chúng ta đang tìm kiếm.

139
00:07:08,000 --> 00:07:11,000
Vì vậy, bắt đầu từ thư mục gốc của 13, chúng ta thấy rằng 89 là lớn hơn,

140
00:07:11,000 --> 00:07:13,000
và do đó, chúng tôi đi về bên phải.

141
00:07:13,000 --> 00:07:16,000
Sau đó, chúng ta thấy nút cho 34, và một lần nữa chúng tôi đi đến bên phải.

142
00:07:16,000 --> 00:07:20,000
89 vẫn còn lớn hơn 55, vì vậy chúng tôi tiếp tục đi về bên phải.

143
00:07:20,000 --> 00:07:24,000
Sau đó chúng tôi đi lên với một nút với giá trị trên 144 và đi bên trái.

144
00:07:24,000 --> 00:07:26,000
Nhìn kìa, 89 là phải có.

145
00:07:26,000 --> 00:07:31,000
>> Một điều mà chúng ta có thể làm là in ra tất cả các số bằng cách thực hiện một traversal inorder.

146
00:07:31,000 --> 00:07:35,000
An inorder traversal có nghĩa là để in ra tất cả mọi thứ trong cây con trái

147
00:07:35,000 --> 00:07:37,000
tiếp theo là in ấn các nút đó

148
00:07:37,000 --> 00:07:40,000
và sau đó theo sau bằng cách in ra tất cả mọi thứ ở bên phải cây con.

149
00:07:40,000 --> 00:07:43,000
Ví dụ, chúng ta hãy lấy cây nhị phân tìm kiếm của chúng tôi yêu thích

150
00:07:43,000 --> 00:07:46,000
và in ra các con số theo thứ tự sắp xếp.

151
00:07:46,000 --> 00:07:49,000
Chúng tôi bắt đầu từ thư mục gốc của 13, nhưng trước khi in 13 chúng tôi phải in ra

152
00:07:49,000 --> 00:07:51,000
tất cả mọi thứ trong cây con trái.

153
00:07:51,000 --> 00:07:55,000
Vì vậy, chúng tôi đi đến 5. Chúng tôi vẫn phải đi sâu hơn xuống trong cây cho đến khi chúng tôi tìm thấy các nút trái nhất,

154
00:07:55,000 --> 00:07:57,000
đó là số không.

155
00:07:57,000 --> 00:08:00,000
Sau khi in không, chúng tôi trở lại lên đến số 1 và in mà ra.

156
00:08:00,000 --> 00:08:03,000
Sau đó, chúng tôi đi đến cây con phải, đó là 2, và in mà ra.

157
00:08:03,000 --> 00:08:05,000
Bây giờ chúng ta đang thực hiện với cây con,

158
00:08:05,000 --> 00:08:07,000
chúng ta có thể trở lại lên đến 3 và in ra.

159
00:08:07,000 --> 00:08:11,000
Tiếp tục trở lại, chúng tôi in 5 và sau đó là 8.

160
00:08:11,000 --> 00:08:13,000
Bây giờ chúng ta đã hoàn thành toàn bộ trái cây con,

161
00:08:13,000 --> 00:08:17,000
chúng ta có thể in ra 13 và bắt đầu làm việc trên bên phải cây con.

162
00:08:17,000 --> 00:08:21,000
Chúng tôi nhảy xuống đến 34, nhưng trước khi in 34 chúng tôi phải in ra cây con trái của nó.

163
00:08:21,000 --> 00:08:27,000
Vì vậy, chúng tôi in ra 21; sau đó chúng tôi nhận được để in ra 34 và truy cập quyền của mình cây con.

164
00:08:27,000 --> 00:08:31,000
Kể từ khi 55 không có cây con bên trái, chúng tôi in nó ra và tiếp tục sang phải cây con của nó.

165
00:08:31,000 --> 00:08:36,000
144 có một cây con bên trái, và vì vậy chúng tôi in ra 89, tiếp theo là các 144,

166
00:08:36,000 --> 00:08:39,000
và cuối cùng là nút phải nhất trong tổng số 233.

167
00:08:39,000 --> 00:08:44,000
Có bạn có nó, tất cả các con số được in ra theo thứ tự từ thấp nhất đến cao nhất.

168
00:08:44,000 --> 00:08:47,000
>> Thêm một cái gì đó để cây là tương đối không đau là tốt.

169
00:08:47,000 --> 00:08:51,000
Tất cả chúng ta phải làm là đảm bảo rằng chúng tôi theo 3 thuộc tính cây tìm kiếm nhị phân

170
00:08:51,000 --> 00:08:53,000
và sau đó chèn giá trị nơi có không gian.

171
00:08:53,000 --> 00:08:55,000
Hãy nói rằng chúng tôi muốn chèn giá trị của 7.

172
00:08:55,000 --> 00:08:58,000
Vì 7 nhỏ hơn 13, chúng tôi đi về bên trái.

173
00:08:58,000 --> 00:09:01,000
Nhưng nó lớn hơn 5, vì vậy chúng tôi đi qua bên phải.

174
00:09:01,000 --> 00:09:04,000
Kể từ khi nó ít hơn 8 và 8 là một nút lá, chúng tôi thêm 7 con trái của 8.

175
00:09:04,000 --> 00:09:09,000
Thì đấy! Chúng tôi đã thêm một số cây tìm kiếm nhị phân của chúng tôi.

176
00:09:09,000 --> 00:09:12,000
>> Nếu chúng ta có thể thêm những điều, chúng ta tốt hơn có thể xóa những thứ như là tốt.

177
00:09:12,000 --> 00:09:14,000
Thật không may cho chúng ta, xóa là một ít phức tạp hơn

178
00:09:14,000 --> 00:09:16,000
không nhiều, nhưng chỉ cần một chút ít.

179
00:09:16,000 --> 00:09:18,000
Có 3 kịch bản khác nhau mà chúng ta phải xem xét

180
00:09:18,000 --> 00:09:21,000
khi xóa các yếu tố từ cây tìm kiếm nhị phân.

181
00:09:21,000 --> 00:09:24,000
Đầu tiên, trường hợp đơn giản nhất là phần tử là một nút lá.

182
00:09:24,000 --> 00:09:27,000
Trong trường hợp này, chúng tôi chỉ đơn giản là xóa nó và đi về với kinh doanh của chúng tôi.

183
00:09:27,000 --> 00:09:30,000
Nói rằng chúng tôi muốn xóa 7 mà chúng ta chỉ cần thêm.

184
00:09:30,000 --> 00:09:34,000
Vâng, chúng tôi chỉ đơn giản là tìm thấy nó, loại bỏ nó, và đó là nó.

185
00:09:35,000 --> 00:09:37,000
Các trường hợp tiếp theo là nếu nút chỉ có 1 trẻ em.

186
00:09:37,000 --> 00:09:40,000
Ở đây chúng ta có thể xóa các nút, nhưng trước tiên chúng ta phải chắc chắn

187
00:09:40,000 --> 00:09:42,000
để kết nối các cây con mà bây giờ còn lại parentless

188
00:09:42,000 --> 00:09:44,000
phụ huynh của các nút, chúng tôi chỉ cần xóa.

189
00:09:44,000 --> 00:09:47,000
Nói rằng chúng tôi muốn xóa 3 từ cây của chúng tôi.

190
00:09:47,000 --> 00:09:50,000
Chúng tôi có các phần tử con của nút đó và đính kèm nó cho phụ huynh của các nút.

191
00:09:50,000 --> 00:09:54,000
Trong trường hợp này, chúng ta đang gắn 1 đến 5.

192
00:09:54,000 --> 00:09:57,000
Điều này làm việc mà không có một vấn đề bởi vì chúng ta biết, theo tài sản cây tìm kiếm nhị phân,

193
00:09:57,000 --> 00:10:01,000
rằng tất cả mọi thứ trong cây con bên trái trong 3 là nhỏ hơn 5.

194
00:10:01,000 --> 00:10:05,000
Bây giờ 3 của cây con được đưa về chăm sóc, chúng ta có thể xóa nó.

195
00:10:05,000 --> 00:10:08,000
Trường hợp thứ ba và cuối cùng là phức tạp nhất.

196
00:10:08,000 --> 00:10:11,000
Đây là trường hợp khi các nút chúng tôi muốn xóa có 2 trẻ em.

197
00:10:11,000 --> 00:10:15,000
Để làm điều này, đầu tiên chúng ta phải tìm các nút có giá trị lớn nhất tiếp theo,

198
00:10:15,000 --> 00:10:18,000
trao đổi hai, và sau đó xóa các nút trong câu hỏi.

199
00:10:18,000 --> 00:10:22,000
Chú ý nút có giá trị lớn nhất tiếp theo không thể có 2 con riêng của mình

200
00:10:22,000 --> 00:10:26,000
kể từ khi con trái của nó sẽ là một ứng cử viên tốt hơn cho lớn nhất tiếp theo.

201
00:10:26,000 --> 00:10:30,000
Vì vậy, việc xóa một nút với 2 trẻ em số tiền để trao đổi 2 nút,

202
00:10:30,000 --> 00:10:33,000
và sau đó xóa được xử lý bởi 1 của 2 quy tắc nói trên.

203
00:10:33,000 --> 00:10:37,000
Ví dụ, chúng ta hãy nói rằng chúng tôi muốn xóa nút gốc, 13.

204
00:10:37,000 --> 00:10:39,000
Điều đầu tiên chúng tôi làm là chúng ta tìm thấy những giá trị lớn nhất trong cây

205
00:10:39,000 --> 00:10:41,000
trong đó, trong trường hợp này, là 21.

206
00:10:41,000 --> 00:10:46,000
Chúng tôi sau đó trao đổi 2 nút, làm cho 13 một chiếc lá và 21 nút nhóm trung tâm.

207
00:10:46,000 --> 00:10:49,000
Bây giờ chúng tôi chỉ đơn giản là có thể xóa 13.

208
00:10:50,000 --> 00:10:53,000
>> Như ám chỉ trước đó, có rất nhiều cách có thể làm cho một cây nhị phân tìm kiếm hợp lệ.

209
00:10:53,000 --> 00:10:56,000
Thật không may cho chúng ta, một số tồi tệ hơn so với những người khác.

210
00:10:56,000 --> 00:10:59,000
Ví dụ, những gì xảy ra khi chúng ta xây dựng một cây tìm kiếm nhị phân

211
00:10:59,000 --> 00:11:01,000
từ một danh sách sắp xếp các con số?

212
00:11:01,000 --> 00:11:04,000
Tất cả số chỉ cần thêm vào bên phải trong mỗi bước.

213
00:11:04,000 --> 00:11:06,000
Khi chúng tôi muốn tìm kiếm một số,

214
00:11:06,000 --> 00:11:08,000
chúng tôi không có sự lựa chọn, nhưng chỉ cần nhìn vào bên phải ở mỗi bước.

215
00:11:08,000 --> 00:11:11,000
Đây không phải là tốt hơn so với tìm kiếm tuyến tính ở tất cả.

216
00:11:11,000 --> 00:11:13,000
Mặc dù chúng tôi không đề cập tới chúng ở đây, có khác, phức tạp hơn,

217
00:11:13,000 --> 00:11:16,000
cấu trúc dữ liệu mà làm cho chắc chắn rằng điều này không xảy ra.

218
00:11:16,000 --> 00:11:18,000
Tuy nhiên, một đơn giản, điều mà có thể được thực hiện để tránh điều này là

219
00:11:18,000 --> 00:11:21,000
để shuffle ngẫu nhiên chỉ là các giá trị đầu vào.

220
00:11:21,000 --> 00:11:26,000
Đó là không cao mà bởi cơ hội ngẫu nhiên một danh sách xáo trộn các con số được sắp xếp.

221
00:11:26,000 --> 00:11:29,000
Nếu đây là trường hợp, sòng bạc sẽ không tiếp tục kinh doanh cho lâu dài.

222
00:11:29,000 --> 00:11:31,000
>> Có bạn có nó.

223
00:11:31,000 --> 00:11:34,000
Bây giờ bạn biết về tìm kiếm nhị phân và cây tìm kiếm nhị phân.

224
00:11:34,000 --> 00:11:36,000
Tôi là Patrick Schmid, và đây là CS50.

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

226
00:11:38,000 --> 00:11:43,000
Một cách rõ ràng sẽ được để quét các danh sách từ ... [beep]

227
00:11:43,000 --> 00:11:46,000
... Số lượng mặt hàng ... yep

228
00:11:46,000 --> 00:11:50,000
[Cười]

229
00:11:50,000 --> 00:11:55,000
... Gửi nút ... 234 augh.

230
00:11:55,000 --> 00:11:58,000
>> Yay! Đó là