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

2
00:00:02,000 --> 00:00:04,000
[Patrick Schmid - Universiti Harvard]

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 berikan anda satu senarai nama-nama watak Disney dalam susunan abjad

5
00:00:09,000 --> 00:00:11,000
dan meminta anda untuk mencari Mickey Mouse,

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

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

8
00:00:15,000 --> 00:00:18,000
dan memeriksa setiap nama untuk melihat jika ia adalah Mickey.

9
00:00:18,000 --> 00:00:22,000
Tetapi kerana anda membaca Aladdin, Alice, Ariel, dan sebagainya,

10
00:00:22,000 --> 00:00:25,000
anda dengan cepat akan menyedari bahawa bermula di hadapan senarai tidak adalah idea yang baik.

11
00:00:25,000 --> 00:00:29,000
Okay, mungkin anda perlu mula bekerja ke belakang dari akhir senarai.

12
00:00:29,000 --> 00:00:33,000
Sekarang anda membaca Tarzan, Jahit, Snow White, dan sebagainya.

13
00:00:33,000 --> 00:00:36,000
Namun, ini tidak kelihatan seperti cara terbaik untuk pergi mengenainya.

14
00:00:36,000 --> 00:00:38,000
>> Nah, satu lagi cara yang anda boleh pergi tentang melakukan ini adalah untuk cuba untuk mengecilkan

15
00:00:38,000 --> 00:00:41,000
senarai nama-nama yang anda perlu melihat.

16
00:00:41,000 --> 00:00:43,000
Sejak anda tahu bahawa mereka berada dalam susunan abjad,

17
00:00:43,000 --> 00:00:45,000
anda hanya boleh melihat nama-nama di tengah-tengah senarai

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

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

20
00:00:51,000 --> 00:00:54,000
anda akan menyedari bahawa M untuk Mickey datang selepas J untuk Jasmine,

21
00:00:54,000 --> 00:00:57,000
jadi anda hanya akan mengabaikan separuh pertama senarai.

22
00:00:57,000 --> 00:00:59,000
Kemudian anda mungkin akan melihat bahagian atas lajur terakhir

23
00:00:59,000 --> 00:01:02,000
dan melihat bahawa ia bermula dengan Rapunzel.

24
00:01:02,000 --> 00:01:06,000
Mickey datang sebelum Rapunzel; kelihatan seperti kita boleh mengabaikan lajur terakhir serta.

25
00:01:06,000 --> 00:01:08,000
Meneruskan strategi carian, anda dengan cepat akan melihat bahawa Mickey

26
00:01:08,000 --> 00:01:11,000
pada separuh pertama senarai nama baki

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

28
00:01:14,000 --> 00:01:17,000
>> Apa yang anda hanya lakukan adalah carian pada dasarnya binari.

29
00:01:17,000 --> 00:01:22,000
Seperti nama ini membayangkan, ia melaksanakan strategi mencari dalam perkara binari.

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

31
00:01:24,000 --> 00:01:27,000
Nah, diberi senarai barangan disusun, algoritma carian binari membuat keputusan binari -

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

33
00:01:33,000 --> 00:01:35,000
Sekarang bahawa kita mempunyai nama yang pergi bersama-sama dengan algoritma carian ini,

34
00:01:35,000 --> 00:01:38,000
mari kita melihat contoh yang lain, tetapi kali ini dengan senarai nombor yang disusun.

35
00:01:38,000 --> 00:01:43,000
Katakanlah kami sedang mencari bilangan 144 dalam senarai ini nombor yang disusun.

36
00:01:43,000 --> 00:01:46,000
Sama seperti sebelum ini, kita dapati bilangan yang di tengah-tengah -

37
00:01:46,000 --> 00:01:50,000
yang dalam kes ini ialah 13 - dan lihat jika 144 adalah lebih besar atau kurang daripada 13.

38
00:01:50,000 --> 00:01:54,000
Sejak ia adalah jelas lebih besar daripada 13, kita boleh mengabaikan bahawa segala-galanya adalah 13 atau kurang

39
00:01:54,000 --> 00:01:57,000
dan hanya menumpukan perhatian pada separuh baki.

40
00:01:57,000 --> 00:01:59,000
Sejak kita kini mempunyai nombor genap item kiri,

41
00:01:59,000 --> 00:02:01,000
kita hanya memilih beberapa yang terletak berhampiran ke tengah.

42
00:02:01,000 --> 00:02:03,000
Dalam kes ini kita memilih 55.

43
00:02:03,000 --> 00:02:06,000
Kita boleh hanya sebagai mudah dipilih 89.

44
00:02:06,000 --> 00:02:11,000
Okay. Sekali lagi, 144 adalah lebih daripada 55 tahun, jadi kita pergi ke kanan.

45
00:02:11,000 --> 00:02:14,000
Nasib baik untuk kita, bilangan pertengahan seterusnya adalah 144,

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

47
00:02:16,000 --> 00:02:21,000
Jadi untuk mencari 144 menggunakan carian binari, kita dapat mencari ia dalam hanya 3 langkah.

48
00:02:21,000 --> 00:02:24,000
Jika kita akan menggunakan carian linear di sini, ia akan kami mengambil 12 langkah.

49
00:02:24,000 --> 00:02:28,000
Sebagai hakikatnya, sejak kaedah ini carian bahagian bilangan item

50
00:02:28,000 --> 00:02:31,000
ia mempunyai melihat pada setiap langkah, ia akan mencari item yang ia mencari

51
00:02:31,000 --> 00:02:35,000
dalam kira-kira log bilangan item dalam senarai.

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

53
00:02:37,000 --> 00:02:41,000
beberapa pseudokod untuk fungsi rekursi yang melaksanakan gelintaran perduaan.

54
00:02:41,000 --> 00:02:44,000
Bermula di bahagian atas, kita melihat bahawa kita perlu untuk mencari fungsi yang mengambil masa 4 hujah:

55
00:02:44,000 --> 00:02:47,000
utama, tatasusunan, min, dan maks.

56
00:02:47,000 --> 00:02:51,000
Utama adalah nombor yang kita cari, jadi 144 dalam contoh sebelumnya.

57
00:02:51,000 --> 00:02:54,000
Tatasusunan adalah senarai nombor yang kita sedang mencari.

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

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

60
00:02:59,000 --> 00:03:03,000
Jadi apabila kita mula, min akan menjadi sifar dan maks akan menjadi indeks maksimum array.

61
00:03:03,000 --> 00:03:07,000
Seperti yang kita menyempitkan carian bawah, kami akan mengemaskini min dan maks

62
00:03:07,000 --> 00:03:10,000
untuk menjadi hanya pelbagai bahawa kita masih mencari masuk

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

64
00:03:12,000 --> 00:03:14,000
Perkara pertama yang kami lakukan ialah mencari titik tengah,

65
00:03:14,000 --> 00:03:19,000
indeks yang di tengah-tengah antara min dan maks pelbagai bahawa kita masih mengingati.

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

67
00:03:22,000 --> 00:03:25,000
dan melihat jika nombor yang kita cari adalah kurang daripada utama yang.

68
00:03:25,000 --> 00:03:27,000
Jika nombor pada kedudukan itu adalah kurang,

69
00:03:27,000 --> 00:03:31,000
maka ia bermakna utama adalah lebih besar daripada semua nombor ke kiri jawatan itu.

70
00:03:31,000 --> 00:03:33,000
Jadi, kita boleh memanggil fungsi carian binari lagi,

71
00:03:33,000 --> 00:03:36,000
tetapi kali ini mengemaskini parameter min dan max untuk membaca hanya separuh

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

73
00:03:40,000 --> 00:03:44,000
Sebaliknya, jika kunci kurang daripada bilangan pada titik tengah semasa array,

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

75
00:03:47,000 --> 00:03:52,000
Sekali lagi, kita panggil carian binari tetapi kali ini dengan julat min dan maks dikemaskini

76
00:03:52,000 --> 00:03:54,000
untuk memasukkan hanya separuh lebih rendah.

77
00:03:54,000 --> 00:03:57,000
Jika nilai pada titik semasa dalam pelbagai adalah tidak

78
00:03:57,000 --> 00:04:01,000
lebih besar daripada mahupun yang lebih kecil daripada kunci, maka ia mesti sama dengan kunci.

79
00:04:01,000 --> 00:04:05,000
Oleh itu, kita hanya boleh mengembalikan indeks titik tengah semasa, dan kami sudah selesai.

80
00:04:05,000 --> 00:04:09,000
Akhirnya, ini cek di sini adalah untuk kes itu bahawa nombor

81
00:04:09,000 --> 00:04:11,000
tidak sebenarnya dalam pelbagai nombor yang kita sedang mencari.

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

83
00:04:14,000 --> 00:04:17,000
pernah kurang daripada minimum, yang bermakna bahawa kita telah pergi terlalu jauh.

84
00:04:17,000 --> 00:04:20,000
Sejak nombor tidak dalam pelbagai input, kita kembali -1

85
00:04:20,000 --> 00:04:24,000
untuk menunjukkan apa-apa yang telah dijumpai.

86
00:04:24,000 --> 00:04:26,000
>> Anda mungkin perasan bahawa bagi algoritma ini untuk bekerja,

87
00:04:26,000 --> 00:04:28,000
mempunyai senarai nombor yang perlu diselesaikan.

88
00:04:28,000 --> 00:04:31,000
Dalam erti kata lain, kita hanya boleh mencari 144 menggunakan gelintaran perduaan

89
00:04:31,000 --> 00:04:34,000
jika semua nombor disusun dari terendah kepada tertinggi.

90
00:04:34,000 --> 00:04:38,000
Jika ini tidak berlaku, kita tidak akan dapat mengecualikan separuh daripada nombor pada setiap langkah.

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

92
00:04:40,000 --> 00:04:43,000
Sama ada kita boleh mengambil senarai Unsorted dan menyusun ia sebelum menggunakan gelintaran perduaan,

93
00:04:43,000 --> 00:04:48,000
atau kita boleh memastikan bahawa senarai nombor yang disusun seperti yang kita menambah nombor.

94
00:04:48,000 --> 00:04:50,000
Oleh itu, bukannya sorting hanya apabila kita perlu mencari,

95
00:04:50,000 --> 00:04:53,000
mengapa tidak menyimpan senarai yang disusun pada setiap masa?

96
00:04:53,000 --> 00:04:57,000
>> Salah satu cara untuk menyimpan senarai nombor disusun pada masa yang sama membenarkan

97
00:04:57,000 --> 00:04:59,000
seseorang untuk menambah atau memindahkan nombor dari senarai ini

98
00:04:59,000 --> 00:05:02,000
adalah dengan menggunakan sesuatu yang dipanggil pokok carian binari.

99
00:05:02,000 --> 00:05:05,000
Satu pokok carian binari adalah satu struktur data yang mempunyai 3 sifat.

100
00:05:05,000 --> 00:05:09,000
Pertama, pohon kiri mana-mana nod mengandungi nilai sahaja yang kurang daripada

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

102
00:05:11,000 --> 00:05:15,000
Kedua, hak pohon nod hanya mengandungi nilai-nilai yang lebih besar daripada

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

104
00:05:17,000 --> 00:05:20,000
Dan, akhirnya, kedua-dua subtrees kiri dan kanan semua nod

105
00:05:20,000 --> 00:05:23,000
juga pohon-pohon carian dedua.

106
00:05:23,000 --> 00:05:26,000
Mari kita melihat contoh dengan nombor yang sama kita digunakan lebih awal.

107
00:05:26,000 --> 00:05:30,000
Bagi anda yang tidak pernah melihat pokok sains komputer sebelum,

108
00:05:30,000 --> 00:05:34,000
biarlah saya mulakan dengan memberitahu anda bahawa pokok sains komputer tumbuh ke bawah.

109
00:05:34,000 --> 00:05:36,000
Ya, tidak seperti pokok yang anda biasa,

110
00:05:36,000 --> 00:05:38,000
akar pokok sains komputer adalah di bahagian atas,

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

112
00:05:41,000 --> 00:05:45,000
Setiap kotak kecil dipanggil nod, dan nod disambungkan antara satu sama lain oleh tepi.

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

114
00:05:48,000 --> 00:05:52,000
yang mempunyai nod 2 kanak-kanak dengan nilai 5 dan 34.

115
00:05:52,000 --> 00:05:57,000
Sebuah pohon adalah pokok yang dibentuk hanya dengan melihat pada subseksyen keseluruhan pokok.

116
00:05:57,000 --> 00:06:03,000
>> Sebagai contoh, anak pohon kiri nod 3 adalah pokok yang dicipta oleh nod 0, 1, dan 2.

117
00:06:03,000 --> 00:06:06,000
Jadi, jika kita kembali kepada sifat-sifat pokok carian binari,

118
00:06:06,000 --> 00:06:09,000
kita lihat bahawa setiap nod dalam pokok itu mematuhi semua 3 harta, iaitu,

119
00:06:09,000 --> 00:06:15,000
anak pohon kiri sahaja mengandungi nilai-nilai yang kurang daripada atau sama dengan nilai nod;

120
00:06:15,000 --> 00:06:16,000
hak pohon semua nod

121
00:06:16,000 --> 00:06:19,000
hanya mengandungi nilai-nilai yang lebih besar daripada atau sama dengan nilai nod;

122
00:06:19,000 --> 00:06:25,000
kedua-dua kiri dan kanan subtrees semua nod juga adalah pokok gelintaran perduaan.

123
00:06:25,000 --> 00:06:28,000
Walaupun pokok ini kelihatan berbeza, ini adalah pokok carian binari sah

124
00:06:28,000 --> 00:06:30,000
bagi set nombor yang sama.

125
00:06:30,000 --> 00:06:32,000
Sebagai hakikatnya, terdapat banyak cara yang mungkin bahawa anda boleh membuat

126
00:06:32,000 --> 00:06:35,000
pokok carian binari yang sah daripada nombor-nombor ini.

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

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

129
00:06:40,000 --> 00:06:44,000
Nah, kita hanya boleh mencari nilai minimum dan maksimum.

130
00:06:44,000 --> 00:06:46,000
Nilai minimum boleh didapati dengan sentiasa pergi ke kiri

131
00:06:46,000 --> 00:06:48,000
sehingga terdapat tidak lebih nod untuk melawat.

132
00:06:48,000 --> 00:06:53,000
Sebaliknya, untuk mencari satu maksimum hanya sekadar pergi ke kanan pada setiap kali.

133
00:06:54,000 --> 00:06:56,000
>> Mencari mana-mana nombor lain yang tidak adalah minimum atau maksimum

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

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

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

137
00:07:03,000 --> 00:07:06,000
bergantung kepada sama ada nilai nod adalah kurang daripada atau lebih daripada

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

139
00:07:08,000 --> 00:07:11,000
Jadi, bermula pada akar 13 tahun, kita melihat bahawa 89 adalah lebih besar,

140
00:07:11,000 --> 00:07:13,000
dan sebagainya kita pergi ke kanan.

141
00:07:13,000 --> 00:07:16,000
Kemudian kita lihat nod selama 34, dan sekali lagi kita pergi ke kanan.

142
00:07:16,000 --> 00:07:20,000
89 berada masih lebih besar daripada 55 tahun, jadi kami terus pergi ke kanan.

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

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

145
00:07:26,000 --> 00:07:31,000
>> Satu lagi perkara yang boleh kita lakukan adalah mencetak semua nombor dengan melaksanakan satu inorder traversal.

146
00:07:31,000 --> 00:07:35,000
Satu inorder traversal bermakna untuk mencetak segala-galanya dalam anak pohon kiri

147
00:07:35,000 --> 00:07:37,000
diikuti oleh percetakan nod sendiri

148
00:07:37,000 --> 00:07:40,000
dan kemudian diikuti oleh mencetak semua keluar dalam hak anak pohon.

149
00:07:40,000 --> 00:07:43,000
Sebagai contoh, mari kita pokok carian binari kegemaran kami

150
00:07:43,000 --> 00:07:46,000
dan mencetak nombor dalam perintah disusun.

151
00:07:46,000 --> 00:07:49,000
Kami bermula pada akar 13 tahun, tetapi sebelum 13 percetakan kita perlu untuk mencetak keluar

152
00:07:49,000 --> 00:07:51,000
segala-galanya dalam anak pohon yang kiri.

153
00:07:51,000 --> 00:07:55,000
Jadi kita pergi ke 5. Kita masih perlu pergi lebih jauh ke dalam pokok itu sehingga kita dapati nod paling kiri,

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

155
00:07:57,000 --> 00:08:00,000
Selepas percetakan sifar, kita kembali sehingga kepada 1 dan mencetak yang keluar.

156
00:08:00,000 --> 00:08:03,000
Kemudian kita pergi ke anak pohon yang betul, yang merupakan 2, dan mencetak yang keluar.

157
00:08:03,000 --> 00:08:05,000
Sekarang kita sedang dilakukan dengan pohon,

158
00:08:05,000 --> 00:08:07,000
kita boleh kembali sehingga ke 3 dan mencetak keluar.

159
00:08:07,000 --> 00:08:11,000
Meneruskan sandaran, kita mencetak 5 dan kemudian 8.

160
00:08:11,000 --> 00:08:13,000
Sekarang kita telah selesai keseluruhan meninggalkan pohon,

161
00:08:13,000 --> 00:08:17,000
kita boleh mencetak out 13 dan mula bekerja di sebelah kanan pohon.

162
00:08:17,000 --> 00:08:21,000
Kami hop ke 34, tetapi sebelum 34 percetakan kita mempunyai untuk mencetak pohon kiri.

163
00:08:21,000 --> 00:08:27,000
Jadi kita mencetak 21; maka kita akan mendapat untuk mencetak 34 dan melawat pohon haknya.

164
00:08:27,000 --> 00:08:31,000
Sejak 55 tidak mempunyai pohon yang kiri, kita cetak keluar dan terus kepada anak pohon kanan.

165
00:08:31,000 --> 00:08:36,000
144 mempunyai pohon yang kiri, dan sebagainya kita mencetak 89, diikuti oleh 144,

166
00:08:36,000 --> 00:08:39,000
dan akhirnya nod yang paling kanan ada 233.

167
00:08:39,000 --> 00:08:44,000
Terdapat anda memilikinya, semua nombor dicetak dalam perintah dari terendah kepada tertinggi.

168
00:08:44,000 --> 00:08:47,000
>> Menambah sesuatu untuk pokok itu adalah agak menyakitkan juga.

169
00:08:47,000 --> 00:08:51,000
Semua yang perlu kita lakukan adalah pastikan bahawa kita mengikuti 3 pokok binari hartanah carian

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

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

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

173
00:08:58,000 --> 00:09:01,000
Tetapi ia adalah lebih daripada 5, jadi kita merentasi ke kanan.

174
00:09:01,000 --> 00:09:04,000
Sejak ia adalah kurang daripada 8 dan 8 adalah nod daun, kita menambah 7 kepada anak kiri 8.

175
00:09:04,000 --> 00:09:09,000
Voilà! Kami telah menambah nombor kepada pohon carian dedua kami.

176
00:09:09,000 --> 00:09:12,000
>> Jika kita boleh menambah perkara, kita lebih baik dapat untuk memadam perkara serta.

177
00:09:12,000 --> 00:09:14,000
Malangnya bagi kita, memotong 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
Terdapat 3 senario yang berbeza yang perlu kita pertimbangkan

180
00:09:18,000 --> 00:09:21,000
apabila memotong elemen daripada pokok-pokok carian binari.

181
00:09:21,000 --> 00:09:24,000
Pertama, kes yang paling mudah adalah bahawa elemen nod daun.

182
00:09:24,000 --> 00:09:27,000
Dalam kes ini, kita hanya memadamnya dan pergi dengan perniagaan kami.

183
00:09:27,000 --> 00:09:30,000
Katakan kita mahu memadam 7 yang kita hanya menambah.

184
00:09:30,000 --> 00:09:34,000
Nah, kita hanya mencari ia, keluarkan ia, dan itulah ia.

185
00:09:35,000 --> 00:09:37,000
Kes seterusnya ialah jika nod mempunyai hanya 1 kanak-kanak.

186
00:09:37,000 --> 00:09:40,000
Di sini kita boleh memadam nod, tetapi kita perlu memastikan

187
00:09:40,000 --> 00:09:42,000
untuk menyambung anak pohon yang kini ditinggalkan parentless

188
00:09:42,000 --> 00:09:44,000
induk nod kita hanya dipadam.

189
00:09:44,000 --> 00:09:47,000
Katakanlah kita mahu untuk memadam 3 dari pokok kita.

190
00:09:47,000 --> 00:09:50,000
Kami mengambil elemen anak nod tersebut dan lampirkan ia ke induk nod.

191
00:09:50,000 --> 00:09:54,000
Dalam kes ini, kita sedang melampirkan 1 hingga 5.

192
00:09:54,000 --> 00:09:57,000
Ini kerja-kerja tanpa sebarang masalah kerana kita tahu, mengikut carian pokok harta binari,

193
00:09:57,000 --> 00:10:01,000
bahawa segala-galanya di pohon kiri 3 adalah kurang daripada 5.

194
00:10:01,000 --> 00:10:05,000
Sekarang bahawa pohon 3 diambil penjagaan, kita boleh memadamnya.

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

196
00:10:08,000 --> 00:10:11,000
Ini adalah kes apabila nod yang kita mahu untuk memadam mempunyai 2 orang anak.

197
00:10:11,000 --> 00:10:15,000
Dalam usaha untuk melakukan ini, kita perlu mencari nod yang mempunyai nilai seterusnya terbesar,

198
00:10:15,000 --> 00:10:18,000
swap dua, dan kemudian memadam nod dalam soalan.

199
00:10:18,000 --> 00:10:22,000
Notis nod yang mempunyai nilai seterusnya terbesar tidak boleh mempunyai 2 orang anak sendiri

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

201
00:10:26,000 --> 00:10:30,000
Oleh itu, memotong nod dengan 2 kanak-kanak berjumlah bertukar-tukar dari 2 nod,

202
00:10:30,000 --> 00:10:33,000
dan kemudian memadam dikendalikan oleh 1 daripada 2 peraturan yang disebutkan di atas.

203
00:10:33,000 --> 00:10:37,000
Sebagai contoh, katakan kita mahu memadam nod akar, 13.

204
00:10:37,000 --> 00:10:39,000
Perkara pertama yang kita lakukan ialah kita mencari nilai seterusnya terbesar di pokok itu

205
00:10:39,000 --> 00:10:41,000
yang, dalam kes ini, ialah 21.

206
00:10:41,000 --> 00:10:46,000
Kami kemudian menukar 2 nod, membuat 13 daun dan 21 nod kumpulan pusat.

207
00:10:46,000 --> 00:10:49,000
Sekarang kita hanya boleh memadam 13.

208
00:10:50,000 --> 00:10:53,000
>> Seperti yang disentuh sebelum ini, terdapat banyak cara yang mungkin untuk membuat carian binari pokok yang sah.

209
00:10:53,000 --> 00:10:56,000
Malangnya bagi kita, ada yang lebih teruk daripada yang lain.

210
00:10:56,000 --> 00:10:59,000
Sebagai contoh, apa yang berlaku apabila kita membina pokok carian binari

211
00:10:59,000 --> 00:11:01,000
dari senarai yang disusun nombor?

212
00:11:01,000 --> 00:11:04,000
Semua nombor hanya ditambah ke kanan pada setiap langkah.

213
00:11:04,000 --> 00:11:06,000
Apabila kita hendak mencari nombor,

214
00:11:06,000 --> 00:11:08,000
kita tidak mempunyai pilihan tetapi hanya untuk melihat di sebelah kanan pada setiap langkah.

215
00:11:08,000 --> 00:11:11,000
Ini bukan adalah lebih baik daripada carian linear pada semua.

216
00:11:11,000 --> 00:11:13,000
Walaupun kita tidak akan melindungi mereka di sini, terdapat lain, lebih kompleks,

217
00:11:13,000 --> 00:11:16,000
struktur data yang memastikan bahawa ini tidak berlaku.

218
00:11:16,000 --> 00:11:18,000
Walau bagaimanapun, satu perkara mudah yang boleh dilakukan untuk mengelakkan ini adalah

219
00:11:18,000 --> 00:11:21,000
hanya shuffle secara rawak nilai input.

220
00:11:21,000 --> 00:11:26,000
Ia adalah sangat tidak mungkin bahawa secara kebetulan rawak senarai yang dikocok nombor disusun.

221
00:11:26,000 --> 00:11:29,000
Jika ini berlaku, kasino tidak akan kekal dalam perniagaan untuk tempoh yang lama.

222
00:11:29,000 --> 00:11:31,000
>> Terdapat anda memilikinya.

223
00:11:31,000 --> 00:11:34,000
Anda kini tahu tentang mencari binari dan pokok gelintaran perduaan.

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 mengimbas senarai dari ... [bip]

227
00:11:43,000 --> 00:11:46,000
... Bilangan item ... Ya

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

229
00:11:50,000 --> 00:11:55,000
... Hantar nod 234 ... augh.

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