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 - Harvard University]

3
00:00:04,000 --> 00:00:07,000
[Ini adalah CS50. - CS50.TV]

4
00:00:07,000 --> 00:00:09,000
>> Jika saya memberi Anda daftar nama karakter Disney dalam urutan abjad

5
00:00:09,000 --> 00:00:11,000
dan meminta Anda untuk menemukan Mickey Mouse,

6
00:00:11,000 --> 00:00:13,000
bagaimana Anda akan pergi tentang melakukan ini?

7
00:00:13,000 --> 00:00:15,000
Salah satu cara yang jelas akan memindai daftar dari awal

8
00:00:15,000 --> 00:00:18,000
dan memeriksa setiap nama untuk melihat apakah itu Mickey.

9
00:00:18,000 --> 00:00:22,000
Tapi seperti yang Anda baca Aladdin, Alice, Ariel, dan sebagainya,

10
00:00:22,000 --> 00:00:25,000
Anda akan segera menyadari bahwa mulai di depan daftar itu bukan ide yang baik.

11
00:00:25,000 --> 00:00:29,000
Oke, mungkin Anda harus mulai bekerja mundur dari akhir daftar.

12
00:00:29,000 --> 00:00:33,000
Sekarang Anda membaca Tarzan, Stitch, Putri Salju, dan sebagainya.

13
00:00:33,000 --> 00:00:36,000
Namun, hal ini tidak tampak seperti cara terbaik untuk pergi tentang itu.

14
00:00:36,000 --> 00:00:38,000
>> Nah, cara lain yang bisa Anda pergi untuk melakukan ini adalah untuk mencoba untuk mempersempit

15
00:00:38,000 --> 00:00:41,000
daftar nama-nama yang Anda harus melihat.

16
00:00:41,000 --> 00:00:43,000
Karena Anda tahu bahwa mereka berada dalam urutan abjad,

17
00:00:43,000 --> 00:00:45,000
Anda hanya bisa melihat nama-nama di tengah daftar

18
00:00:45,000 --> 00:00:49,000
dan memeriksa apakah Mickey Mouse adalah sebelum atau setelah nama ini.

19
00:00:49,000 --> 00:00:51,000
Melihat nama terakhir di kolom kedua

20
00:00:51,000 --> 00:00:54,000
Anda akan menyadari bahwa M untuk Mickey datang setelah J untuk Jasmine,

21
00:00:54,000 --> 00:00:57,000
sehingga Anda hanya akan mengabaikan paruh pertama daftar.

22
00:00:57,000 --> 00:00:59,000
Maka Anda mungkin akan melihat di bagian atas kolom terakhir

23
00:00:59,000 --> 00:01:02,000
dan melihat bahwa itu dimulai dengan Rapunzel.

24
00:01:02,000 --> 00:01:06,000
Mickey datang sebelum Rapunzel, sepertinya kita dapat mengabaikan kolom terakhir juga.

25
00:01:06,000 --> 00:01:08,000
Melanjutkan strategi pencarian, Anda akan segera melihat bahwa Mickey

26
00:01:08,000 --> 00:01:11,000
adalah pada paruh pertama dari daftar sisa nama

27
00:01:11,000 --> 00:01:14,000
dan akhirnya menemukan Mickey bersembunyi antara Merlin dan Minnie.

28
00:01:14,000 --> 00:01:17,000
>> Apa yang baru saja Anda lakukan adalah pencarian biner pada dasarnya.

29
00:01:17,000 --> 00:01:22,000
Seperti nama ini menyiratkan, ia melakukan strategi pencarian dalam hitungan biner.

30
00:01:22,000 --> 00:01:24,000
Apa artinya ini?

31
00:01:24,000 --> 00:01:27,000
Nah, mengingat daftar item diurutkan, algoritma pencarian biner membuat keputusan biner -

32
00:01:27,000 --> 00:01:33,000
kiri atau kanan, lebih besar dari atau kurang dari, abjad sebelum atau setelah - pada setiap titik.

33
00:01:33,000 --> 00:01:35,000
Sekarang bahwa kita memiliki nama yang sejalan dengan algoritma pencarian,

34
00:01:35,000 --> 00:01:38,000
mari kita lihat contoh lain, tapi kali ini dengan daftar nomor diurutkan.

35
00:01:38,000 --> 00:01:43,000
Katakanlah kita sedang mencari nomor 144 dalam daftar nomor diurutkan.

36
00:01:43,000 --> 00:01:46,000
Sama seperti sebelumnya, kita menemukan nomor yang ada di tengah -

37
00:01:46,000 --> 00:01:50,000
yang dalam hal ini adalah 13 - dan melihat apakah lebih besar dari 144 atau kurang dari 13.

38
00:01:50,000 --> 00:01:54,000
Karena itu jelas lebih besar dari 13, kita dapat mengabaikan segala sesuatu yang 13 atau kurang

39
00:01:54,000 --> 00:01:57,000
dan hanya berkonsentrasi pada tersisa separuhnya.

40
00:01:57,000 --> 00:01:59,000
Karena kita sekarang memiliki bahkan jumlah item yang tersisa,

41
00:01:59,000 --> 00:02:01,000
kita hanya memilih nomor yang dekat ke tengah.

42
00:02:01,000 --> 00:02:03,000
Dalam hal ini kita pilih 55.

43
00:02:03,000 --> 00:02:06,000
Kita bisa dengan mudah memilih 89.

44
00:02:06,000 --> 00:02:11,000
Oke. Sekali lagi, 144 lebih besar dari 55, jadi kami pergi ke kanan.

45
00:02:11,000 --> 00:02:14,000
Untungnya bagi kita, jumlah menengah berikutnya adalah 144,

46
00:02:14,000 --> 00:02:16,000
yang kita cari.

47
00:02:16,000 --> 00:02:21,000
Jadi dalam rangka untuk menemukan 144 menggunakan pencarian biner, kita dapat menemukannya hanya dalam 3 langkah.

48
00:02:21,000 --> 00:02:24,000
Jika kita akan menggunakan pencarian linear di sini, itu akan membawa kami 12 langkah.

49
00:02:24,000 --> 00:02:28,000
Sebagai soal fakta, karena ini metode pencarian membagi dua jumlah item

50
00:02:28,000 --> 00:02:31,000
itu harus melihat pada setiap langkah, ia akan menemukan item itu mencari

51
00:02:31,000 --> 00:02:35,000
di sekitar log dari jumlah item dalam daftar.

52
00:02:35,000 --> 00:02:37,000
Sekarang yang kita lihat 2 contoh, mari kita lihat

53
00:02:37,000 --> 00:02:41,000
beberapa pseudocode untuk fungsi rekursif yang mengimplementasikan pencarian biner.

54
00:02:41,000 --> 00:02:44,000
Mulai di atas, kita melihat bahwa kita harus menemukan fungsi yang mengambil 4 argumen:

55
00:02:44,000 --> 00:02:47,000
kunci, array, min, dan max.

56
00:02:47,000 --> 00:02:51,000
Kuncinya adalah jumlah yang kita cari, jadi 144 pada contoh sebelumnya.

57
00:02:51,000 --> 00:02:54,000
Array adalah daftar nomor yang kita cari.

58
00:02:54,000 --> 00:02:57,000
Min dan max adalah indeks dari posisi minimum dan maksimum

59
00:02:57,000 --> 00:02:59,000
bahwa kita sedang melihat.

60
00:02:59,000 --> 00:03:03,000
Jadi ketika kita mulai, min akan menjadi nol dan max akan menjadi indeks maksimum array.

61
00:03:03,000 --> 00:03:07,000
Seperti kita mempersempit pencarian ke bawah, kami akan memperbarui min dan max

62
00:03:07,000 --> 00:03:10,000
menjadi hanya kisaran yang kita masih mencari masuk

63
00:03:10,000 --> 00:03:12,000
>> Mari kita melompat ke bagian yang menarik pertama.

64
00:03:12,000 --> 00:03:14,000
Hal pertama yang kita lakukan adalah menemukan titik tengah,

65
00:03:14,000 --> 00:03:19,000
indeks yang setengah jalan antara min dan max dari array yang kita masih mempertimbangkan.

66
00:03:19,000 --> 00:03:22,000
Kemudian kita melihat nilai dari array di lokasi titik tengah

67
00:03:22,000 --> 00:03:25,000
dan melihat apakah jumlah yang kita cari adalah kurang dari kunci yang.

68
00:03:25,000 --> 00:03:27,000
Jika nomor pada posisi yang kurang,

69
00:03:27,000 --> 00:03:31,000
maka itu berarti kuncinya adalah lebih besar dari semua nomor di sebelah kiri posisi itu.

70
00:03:31,000 --> 00:03:33,000
Jadi kita bisa memanggil fungsi pencarian biner lagi,

71
00:03:33,000 --> 00:03:36,000
tapi kali ini memperbarui min dan parameter max untuk membaca hanya setengah

72
00:03:36,000 --> 00:03:40,000
yang lebih besar dari atau sama dengan nilai kita hanya melihat.

73
00:03:40,000 --> 00:03:44,000
Di sisi lain, jika kuncinya adalah kurang dari jumlah pada titik tengah saat array,

74
00:03:44,000 --> 00:03:47,000
kita ingin pergi ke kiri dan mengabaikan semua nomor yang lebih besar.

75
00:03:47,000 --> 00:03:52,000
Sekali lagi, kita sebut pencarian biner tapi kali ini dengan kisaran min dan max updated

76
00:03:52,000 --> 00:03:54,000
untuk menyertakan hanya bagian bawah.

77
00:03:54,000 --> 00:03:57,000
Jika nilai pada titik tengah saat ini dalam array bukanlah

78
00:03:57,000 --> 00:04:01,000
lebih besar dari atau lebih kecil dari kunci, maka harus sama dengan kunci.

79
00:04:01,000 --> 00:04:05,000
Jadi, kita hanya bisa mengembalikan indeks titik tengah saat ini, dan kami sudah selesai.

80
00:04:05,000 --> 00:04:09,000
Akhirnya, cek ini di sini adalah untuk kasus yang nomor

81
00:04:09,000 --> 00:04:11,000
tidak benar-benar dalam array angka yang kita cari.

82
00:04:11,000 --> 00:04:14,000
Jika indeks maksimum kisaran yang kita cari

83
00:04:14,000 --> 00:04:17,000
yang pernah kurang dari minimum, itu berarti bahwa kita sudah terlalu jauh.

84
00:04:17,000 --> 00:04:20,000
Karena jumlah itu tidak dalam array masukan, kita kembali -1

85
00:04:20,000 --> 00:04:24,000
untuk menunjukkan bahwa tidak ada yang ditemukan.

86
00:04:24,000 --> 00:04:26,000
>> Anda mungkin telah memperhatikan bahwa untuk algoritma ini untuk bekerja,

87
00:04:26,000 --> 00:04:28,000
daftar nomor harus diurutkan.

88
00:04:28,000 --> 00:04:31,000
Dengan kata lain, kita hanya dapat menemukan 144 menggunakan pencarian biner

89
00:04:31,000 --> 00:04:34,000
jika semua nomor yang dipesan dari terendah hingga tertinggi.

90
00:04:34,000 --> 00:04:38,000
Jika hal ini tidak terjadi, kita tidak akan dapat mengecualikan setengah dari angka pada setiap langkah.

91
00:04:38,000 --> 00:04:40,000
Jadi kita memiliki 2 pilihan.

92
00:04:40,000 --> 00:04:43,000
Entah kita dapat mengambil daftar unsorted dan semacam itu sebelum menggunakan pencarian biner,

93
00:04:43,000 --> 00:04:48,000
atau kita dapat memastikan bahwa daftar nomor diurutkan seperti kita menambahkan nomor untuk itu.

94
00:04:48,000 --> 00:04:50,000
Dengan demikian, bukan hanya menyortir ketika kita harus mencari,

95
00:04:50,000 --> 00:04:53,000
mengapa tidak menjaga daftar diurutkan setiap saat?

96
00:04:53,000 --> 00:04:57,000
>> Salah satu cara untuk menjaga daftar nomor diurutkan sekaligus memungkinkan

97
00:04:57,000 --> 00:04:59,000
satu untuk menambah atau memindahkan nomor dari daftar ini

98
00:04:59,000 --> 00:05:02,000
adalah dengan menggunakan sesuatu yang disebut pohon pencarian biner.

99
00:05:02,000 --> 00:05:05,000
Sebuah pohon pencarian biner adalah struktur data yang memiliki 3 sifat.

100
00:05:05,000 --> 00:05:09,000
Pertama, subtree kiri setiap node hanya mengandung nilai-nilai yang kurang dari

101
00:05:09,000 --> 00:05:11,000
atau sama dengan nilai node.

102
00:05:11,000 --> 00:05:15,000
Kedua, hak subtree dari node hanya berisi nilai-nilai yang lebih besar dari

103
00:05:15,000 --> 00:05:17,000
atau sama dengan nilai node.

104
00:05:17,000 --> 00:05:20,000
Dan, akhirnya, baik kiri dan kanan subtrees dari semua node

105
00:05:20,000 --> 00:05:23,000
juga pohon pencarian biner.

106
00:05:23,000 --> 00:05:26,000
Mari kita lihat contoh dengan angka yang sama kita gunakan sebelumnya.

107
00:05:26,000 --> 00:05:30,000
Bagi anda yang belum pernah melihat pohon ilmu komputer sebelumnya,

108
00:05:30,000 --> 00:05:34,000
Mari saya mulai dengan mengatakan bahwa pohon ilmu komputer tumbuh ke bawah.

109
00:05:34,000 --> 00:05:36,000
Ya, tidak seperti pohon Anda terbiasa,

110
00:05:36,000 --> 00:05:38,000
akar pohon ilmu komputer adalah di bagian atas,

111
00:05:38,000 --> 00:05:41,000
dan daun di bagian bawah.

112
00:05:41,000 --> 00:05:45,000
Setiap kotak kecil yang disebut node, dan node yang terhubung satu sama lain dengan tepi.

113
00:05:45,000 --> 00:05:48,000
Jadi akar pohon ini adalah nilai node dengan nilai 13,

114
00:05:48,000 --> 00:05:52,000
yang memiliki 2 node anak dengan nilai 5 dan 34.

115
00:05:52,000 --> 00:05:57,000
Sebuah subtree adalah pohon yang dibentuk hanya dengan melihat subbagian dari seluruh pohon.

116
00:05:57,000 --> 00:06:03,000
>> Misalnya, subtree kiri 3 node pohon diciptakan oleh, node 0 1, dan 2.

117
00:06:03,000 --> 00:06:06,000
Jadi, jika kita kembali ke sifat dari pohon pencarian biner,

118
00:06:06,000 --> 00:06:09,000
kita melihat bahwa setiap node di pohon sesuai dengan semua 3 sifat, yaitu,

119
00:06:09,000 --> 00:06:15,000
subtree kiri hanya berisi nilai-nilai yang kurang dari atau sama dengan nilai node;

120
00:06:15,000 --> 00:06:16,000
hak subtree dari semua node

121
00:06:16,000 --> 00:06:19,000
hanya berisi nilai-nilai yang lebih besar dari atau sama dengan nilai node, dan

122
00:06:19,000 --> 00:06:25,000
subtrees baik kiri dan kanan dari semua node juga merupakan biner pohon pencarian.

123
00:06:25,000 --> 00:06:28,000
Meskipun pohon ini terlihat berbeda, ini adalah pohon biner yang sah pencarian

124
00:06:28,000 --> 00:06:30,000
untuk set yang sama angka.

125
00:06:30,000 --> 00:06:32,000
Sebagai soal fakta, ada banyak cara yang mungkin bahwa Anda dapat membuat

126
00:06:32,000 --> 00:06:35,000
pencarian berlaku pohon biner dari angka-angka.

127
00:06:35,000 --> 00:06:38,000
Nah, mari kita kembali ke yang pertama kita buat.

128
00:06:38,000 --> 00:06:40,000
Jadi apa yang bisa kita lakukan dengan pohon-pohon?

129
00:06:40,000 --> 00:06:44,000
Nah, kita bisa sangat sederhana menemukan nilai-nilai minimum dan maksimum.

130
00:06:44,000 --> 00:06:46,000
Nilai minimum dapat ditemukan dengan selalu pergi ke kiri

131
00:06:46,000 --> 00:06:48,000
sampai ada node lagi untuk mengunjungi.

132
00:06:48,000 --> 00:06:53,000
Sebaliknya, untuk menemukan satu maksimum hanya hanya turun ke kanan pada setiap waktu.

133
00:06:54,000 --> 00:06:56,000
>> Menemukan nomor lain yang tidak minimum atau maksimum

134
00:06:56,000 --> 00:06:58,000
sama mudah.

135
00:06:58,000 --> 00:07:00,000
Katakanlah kita sedang mencari nomor 89.

136
00:07:00,000 --> 00:07:03,000
Kami hanya memeriksa nilai setiap node dan pergi ke kiri atau kanan,

137
00:07:03,000 --> 00:07:06,000
tergantung pada apakah nilai node kurang dari atau lebih besar dari

138
00:07:06,000 --> 00:07:08,000
yang kita cari.

139
00:07:08,000 --> 00:07:11,000
Jadi, mulai dari akar 13, kita melihat bahwa 89 lebih besar,

140
00:07:11,000 --> 00:07:13,000
dan jadi kami pergi ke kanan.

141
00:07:13,000 --> 00:07:16,000
Kemudian kita melihat node untuk 34, dan lagi kita pergi ke kanan.

142
00:07:16,000 --> 00:07:20,000
89 masih lebih besar dari 55, jadi kita terus pergi ke kanan.

143
00:07:20,000 --> 00:07:24,000
Kami kemudian datang dengan simpul dengan nilai 144 dan pergi ke kiri.

144
00:07:24,000 --> 00:07:26,000
Lo dan lihatlah, 89 ada di sana.

145
00:07:26,000 --> 00:07:31,000
>> Hal lain yang dapat kita lakukan adalah mencetak semua nomor dengan melakukan traversal inorder.

146
00:07:31,000 --> 00:07:35,000
Sebuah traversal inorder berarti untuk mencetak semuanya keluar di subtree kiri

147
00:07:35,000 --> 00:07:37,000
diikuti dengan mencetak node itu sendiri

148
00:07:37,000 --> 00:07:40,000
dan kemudian diikuti dengan mencetak segala sesuatu di kanan subtree.

149
00:07:40,000 --> 00:07:43,000
Sebagai contoh, mari kita biner favorit kami pohon pencarian

150
00:07:43,000 --> 00:07:46,000
dan mencetak angka dalam urutan diurutkan.

151
00:07:46,000 --> 00:07:49,000
Kami mulai dari akar 13, namun sebelum mencetak 13 kita harus mencetak

152
00:07:49,000 --> 00:07:51,000
segala sesuatu di subtree kiri.

153
00:07:51,000 --> 00:07:55,000
Jadi kita pergi ke 5. Kami masih harus pergi lebih dalam ke dalam pohon sampai kita menemukan simpul paling kiri,

154
00:07:55,000 --> 00:07:57,000
yang adalah nol.

155
00:07:57,000 --> 00:08:00,000
Setelah mencetak nol, kita kembali ke 1 dan mencetak yang keluar.

156
00:08:00,000 --> 00:08:03,000
Kemudian kami pergi ke kanan subtree, yaitu 2, dan mencetak yang keluar.

157
00:08:03,000 --> 00:08:05,000
Sekarang kita sudah selesai dengan itu subtree,

158
00:08:05,000 --> 00:08:07,000
kita bisa kembali ke 3 dan mencetaknya.

159
00:08:07,000 --> 00:08:11,000
Melanjutkan kembali, kami mencetak 5 dan kemudian 8.

160
00:08:11,000 --> 00:08:13,000
Sekarang kami telah menyelesaikan seluruh subtree kiri,

161
00:08:13,000 --> 00:08:17,000
kita bisa mencetak 13 dan mulai bekerja di sebelah kanan subtree.

162
00:08:17,000 --> 00:08:21,000
Kami melompat turun ke 34, tapi sebelum mencetak 34 kita harus mencetak subtree kiri.

163
00:08:21,000 --> 00:08:27,000
Jadi kita mencetak 21; maka kita bisa mencetak 34 dan mengunjungi subpohon kanan nya.

164
00:08:27,000 --> 00:08:31,000
Sejak 55 tidak memiliki subtree kiri, kita mencetaknya dan melanjutkan ke subtree kanan.

165
00:08:31,000 --> 00:08:36,000
144 memiliki subtree kiri, dan jadi kami mencetak 89, diikuti oleh 144,

166
00:08:36,000 --> 00:08:39,000
dan akhirnya simpul paling kanan dari 233.

167
00:08:39,000 --> 00:08:44,000
Di sana Anda memilikinya, semua angka yang dicetak dalam urutan dari terendah hingga tertinggi.

168
00:08:44,000 --> 00:08:47,000
>> Menambahkan sesuatu untuk pohon ini relatif tanpa rasa sakit juga.

169
00:08:47,000 --> 00:08:51,000
Yang harus kita lakukan adalah memastikan bahwa kita mengikuti 3 sifat pencarian biner pohon

170
00:08:51,000 --> 00:08:53,000
dan kemudian memasukkan nilai di mana ada ruang.

171
00:08:53,000 --> 00:08:55,000
Katakanlah kita ingin memasukkan nilai 7.

172
00:08:55,000 --> 00:08:58,000
Sejak 7 kurang dari 13, kita pergi ke kiri.

173
00:08:58,000 --> 00:09:01,000
Tapi itu lebih besar dari 5, jadi kami melintasi ke kanan.

174
00:09:01,000 --> 00:09:04,000
Karena itu kurang dari 8 dan 8 adalah simpul daun, kita menambahkan 7 ke anak kiri dari 8.

175
00:09:04,000 --> 00:09:09,000
Voila! Kami telah menambahkan nomor ke pohon pencarian kami biner.

176
00:09:09,000 --> 00:09:12,000
>> Jika kita dapat menambahkan hal-hal, lebih baik kita bisa menghapus hal-hal juga.

177
00:09:12,000 --> 00:09:14,000
Sayangnya bagi kita, menghapus adalah sedikit lebih rumit -

178
00:09:14,000 --> 00:09:16,000
tidak banyak, tetapi hanya sedikit.

179
00:09:16,000 --> 00:09:18,000
Ada 3 skenario yang berbeda bahwa kita harus mempertimbangkan

180
00:09:18,000 --> 00:09:21,000
saat menghapus elemen dari pohon pencarian biner.

181
00:09:21,000 --> 00:09:24,000
Pertama, hal termudah adalah bahwa elemen adalah simpul daun.

182
00:09:24,000 --> 00:09:27,000
Dalam kasus ini, kita hanya menghapusnya dan melanjutkan bisnis kami.

183
00:09:27,000 --> 00:09:30,000
Katakanlah kita ingin menghapus 7 yang baru saja kita menambahkan.

184
00:09:30,000 --> 00:09:34,000
Nah, kita hanya menemukan itu, menghapusnya, dan hanya itu.

185
00:09:35,000 --> 00:09:37,000
Kasus berikutnya adalah jika node hanya memiliki 1 anak.

186
00:09:37,000 --> 00:09:40,000
Di sini kita dapat menghapus node, tapi pertama-tama kita harus memastikan

187
00:09:40,000 --> 00:09:42,000
untuk menghubungkan subtree yang sekarang kiri yatim

188
00:09:42,000 --> 00:09:44,000
ke node induk kami hanya dihapus.

189
00:09:44,000 --> 00:09:47,000
Katakanlah kita ingin menghapus 3 dari pohon kami.

190
00:09:47,000 --> 00:09:50,000
Kami mengambil elemen anak dari simpul tersebut dan melampirkannya pada orang tua dari node.

191
00:09:50,000 --> 00:09:54,000
Dalam kasus ini, kita sekarang melampirkan 1 ke 5.

192
00:09:54,000 --> 00:09:57,000
Ini bekerja tanpa masalah karena kita tahu, menurut properti biner pencarian pohon,

193
00:09:57,000 --> 00:10:01,000
bahwa segala sesuatu di subtree kiri 3 adalah kurang dari 5.

194
00:10:01,000 --> 00:10:05,000
Sekarang itulah subtree 3 yang diurus, kita bisa menghapusnya.

195
00:10:05,000 --> 00:10:08,000
Kasus ketiga dan terakhir adalah yang paling kompleks.

196
00:10:08,000 --> 00:10:11,000
Ini adalah kasus ketika node kita ingin menghapus memiliki 2 anak.

197
00:10:11,000 --> 00:10:15,000
Untuk melakukan hal ini, pertama-tama kita harus menemukan simpul yang memiliki nilai terbesar berikutnya,

198
00:10:15,000 --> 00:10:18,000
swap dua, dan kemudian menghapus node yang bersangkutan.

199
00:10:18,000 --> 00:10:22,000
Perhatikan node yang memiliki nilai terbesar berikutnya tidak dapat memiliki 2 anak itu sendiri

200
00:10:22,000 --> 00:10:26,000
sejak anak kiri akan menjadi calon yang lebih baik untuk terbesar berikutnya.

201
00:10:26,000 --> 00:10:30,000
Oleh karena itu, menghapus simpul dengan 2 anak berjumlah swapping dari 2 node,

202
00:10:30,000 --> 00:10:33,000
dan kemudian menghapus ditangani oleh 1 dari 2 aturan tersebut.

203
00:10:33,000 --> 00:10:37,000
Sebagai contoh, katakanlah kita ingin menghapus simpul akar, 13.

204
00:10:37,000 --> 00:10:39,000
Hal pertama yang kita lakukan adalah kita menemukan nilai terbesar berikutnya dalam pohon

205
00:10:39,000 --> 00:10:41,000
yang, dalam hal ini, adalah 21.

206
00:10:41,000 --> 00:10:46,000
Kami kemudian swap 2 node, membuat 13 daun dan 21 node kelompok pusat.

207
00:10:46,000 --> 00:10:49,000
Sekarang kita hanya dapat menghapus 13.

208
00:10:50,000 --> 00:10:53,000
>> Seperti disinggung sebelumnya, ada banyak cara yang mungkin untuk membuat sebuah pohon pencarian biner yang valid.

209
00:10:53,000 --> 00:10:56,000
Sayangnya bagi kita, beberapa lebih buruk daripada yang lain.

210
00:10:56,000 --> 00:10:59,000
Sebagai contoh, apa yang terjadi ketika kita membangun sebuah pohon pencarian biner

211
00:10:59,000 --> 00:11:01,000
dari daftar diurutkan dari nomor?

212
00:11:01,000 --> 00:11:04,000
Semua nomor yang hanya ditambahkan ke kanan pada setiap langkah.

213
00:11:04,000 --> 00:11:06,000
Ketika kita ingin mencari nomor,

214
00:11:06,000 --> 00:11:08,000
kita tidak punya pilihan selain hanya untuk melihat kanan di setiap langkah.

215
00:11:08,000 --> 00:11:11,000
Hal ini tidak lebih baik daripada pencarian linear sama sekali.

216
00:11:11,000 --> 00:11:13,000
Meskipun kami tidak akan menutupi mereka di sini, ada yang lain, lebih kompleks,

217
00:11:13,000 --> 00:11:16,000
Data struktur yang memastikan bahwa hal ini tidak terjadi.

218
00:11:16,000 --> 00:11:18,000
Namun, satu hal sederhana yang dapat dilakukan untuk menghindari hal ini adalah

219
00:11:18,000 --> 00:11:21,000
hanya secara acak mengocok nilai masukan.

220
00:11:21,000 --> 00:11:26,000
Ini sangat tidak mungkin bahwa secara kebetulan acak daftar beringsut dari nomor yang diurutkan.

221
00:11:26,000 --> 00:11:29,000
Jika ini terjadi, kasino tidak akan tinggal dalam bisnis untuk waktu yang lama.

222
00:11:29,000 --> 00:11:31,000
>> Di sana Anda memilikinya.

223
00:11:31,000 --> 00:11:34,000
Anda sekarang tahu tentang pencarian biner dan pohon pencarian biner.

224
00:11:34,000 --> 00:11:36,000
Saya Patrick Schmid, dan ini adalah CS50.

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

226
00:11:38,000 --> 00:11:43,000
Salah satu cara yang jelas akan memindai daftar dari ... [bip]

227
00:11:43,000 --> 00:11:46,000
... Jumlah item ... yep

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

229
00:11:50,000 --> 00:11:55,000
... Posting simpul dari 234 ... Augh.

230
00:11:55,000 --> 00:11:58,000
>> Yay! Itu -