1
00:00:00,000 --> 00:00:02,000
[Powered by Google Translate] [Binary Axtarış]

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

3
00:00:04,000 --> 00:00:07,000
[Bu CS50 edir. - CS50.TV]

4
00:00:07,000 --> 00:00:09,000
>> Mən əlifba sırası ilə siz Disney xarakterli adları siyahısı verdi

5
00:00:09,000 --> 00:00:11,000
və Mickey Mouse tapmaq üçün xahiş

6
00:00:11,000 --> 00:00:13,000
necə bunu barədə getmək istəyirsiniz?

7
00:00:13,000 --> 00:00:15,000
Bir Aşkar şəkildə əvvəldən siyahısını scan olacaq

8
00:00:15,000 --> 00:00:18,000
və Mickey varsa görmək üçün hər ad oldu.

9
00:00:18,000 --> 00:00:22,000
Amma s Ələddin, Alice, Ariel, oxumaq və kimi,

10
00:00:22,000 --> 00:00:25,000
tez siyahısına qarşısında başlayan yaxşı bir fikir deyil ki, həyata lazımdır.

11
00:00:25,000 --> 00:00:29,000
OK, bəlkə siz siyahısına sonunda geri iş başlamaq lazımdır.

12
00:00:29,000 --> 00:00:33,000
İndi Tarzan, Stitch, Qar Ağ və s oxuyun.

13
00:00:33,000 --> 00:00:36,000
Still, bu barədə getmək üçün ən yaxşı yol kimi görünür deyil.

14
00:00:36,000 --> 00:00:38,000
>> Yaxşı, siz bunu edə bilər ki, başqa yol daraltmak üçün cəhd edir

15
00:00:38,000 --> 00:00:41,000
siz baxmaq ki, adları siyahısı.

16
00:00:41,000 --> 00:00:43,000
Əgər onlar əlifba sırası bilirik ildən,

17
00:00:43,000 --> 00:00:45,000
Siz yalnız siyahısı ortasında adları baxmaq bilər

18
00:00:45,000 --> 00:00:49,000
Mickey Mouse bu ad əvvəl və ya sonra əgər və yoxlamaq.

19
00:00:49,000 --> 00:00:51,000
İkinci sütun son adı baxanda

20
00:00:51,000 --> 00:00:54,000
siz ki, Mickey M Jasmine üçün J sonra gəlir reallaşdırmaq istədiyiniz

21
00:00:54,000 --> 00:00:57,000
siz sadəcə siyahısının birinci yarısında ignore ediyorum.

22
00:00:57,000 --> 00:00:59,000
Sonra yəqin ki, son sütun üst baxmaq istədiyiniz

23
00:00:59,000 --> 00:01:02,000
və Rapunzel başlayır görürük.

24
00:01:02,000 --> 00:01:06,000
Mickey Rapunzel əvvəl gəlir, biz də son sütun iqnor edə bilər kimi görünür.

25
00:01:06,000 --> 00:01:08,000
Axtarış strategiya davam etdirərək, tez görəcəksiniz ki, Mickey

26
00:01:08,000 --> 00:01:11,000
adları qalan siyahısı birinci yarısında edir

27
00:01:11,000 --> 00:01:14,000
və nəhayət Mickey Merlin və Minnie arasında gizli tapa bilərsiniz.

28
00:01:14,000 --> 00:01:17,000
>> Yalnız nə əsasən ikili axtarış idi.

29
00:01:17,000 --> 00:01:22,000
Bu adı nəzərdə tutur ki, bu ikili məsələ öz axtarış strategiya həyata keçirir.

30
00:01:22,000 --> 00:01:24,000
Bu nə deməkdir?

31
00:01:24,000 --> 00:01:27,000
Yaxşı, sıralanır əşyaların siyahısını nəzərə alaraq, ikili axtarış alqoritm ikili qərar qəbul edir -

32
00:01:27,000 --> 00:01:33,000
sol və ya sağ, daha çox və ya daha az əvvəl və ya sonra əlifba sırası ilə çox - hər bir nöqtədə.

33
00:01:33,000 --> 00:01:35,000
İndi bu axtarış alqoritmi ilə yanaşı gedir ki, bir adı var ki,

34
00:01:35,000 --> 00:01:38,000
nin başqa bir misal baxaq, lakin bu zaman sıralanır nömrələri siyahısı.

35
00:01:38,000 --> 00:01:43,000
Biz sıralanır nömrələri bu siyahıda sayı 144 axtarır söyləyin.

36
00:01:43,000 --> 00:01:46,000
Əvvəl istəyirəm Sadəcə, biz ortada olan sayı tapmaq -

37
00:01:46,000 --> 00:01:50,000
Bu halda 13 - və 144-dən çox və ya 13-dən az olduqda görürük.

38
00:01:50,000 --> 00:01:54,000
O 13-dən çox aydın böyük olduğundan, biz 13 və ya daha az hər şeyi iqnor edə bilər

39
00:01:54,000 --> 00:01:57,000
və yalnız yarım qalan üzərində.

40
00:01:57,000 --> 00:01:59,000
Biz sol maddələr daha da sayı, çünki

41
00:01:59,000 --> 00:02:01,000
biz sadəcə orta yaxındır ki, bir sıra seçin.

42
00:02:01,000 --> 00:02:03,000
Bu halda biz 55 seçin.

43
00:02:03,000 --> 00:02:06,000
Biz yalnız asanlıqla 89 seçilmiş ola bilər.

44
00:02:06,000 --> 00:02:11,000
Okay. Yenə 144 55 daha böyükdür, belə ki, biz doğru gedin.

45
00:02:11,000 --> 00:02:14,000
Xoşbəxtlikdən bizim üçün, növbəti orta sayı 144-dir

46
00:02:14,000 --> 00:02:16,000
biz aradığınız bir.

47
00:02:16,000 --> 00:02:21,000
Ikili istifadə edərək 144 tapmaq üçün üçün, biz yalnız 3 adımda ildə tapa istəyirik.

48
00:02:21,000 --> 00:02:24,000
Burada xətti axtarış istifadə etsəniz, bu bizə 12 addımlar olardı.

49
00:02:24,000 --> 00:02:28,000
Əslində kimi, ildən bu axtarış metodu maddələr sayı yarıya indirir

50
00:02:28,000 --> 00:02:31,000
hər addımda baxmaq var, onu axtarır maddə tapa

51
00:02:31,000 --> 00:02:35,000
siyahısında maddələrin sayı log haqqında.

52
00:02:35,000 --> 00:02:37,000
İndi 2 nümunələr gördük ki, in nəzər edək

53
00:02:37,000 --> 00:02:41,000
binar axtarış həyata rekursiv funksiya üçün bəzi pseudocode.

54
00:02:41,000 --> 00:02:44,000
Üst başlayaraq, biz 4 arqumentlər edir ki, funksiyası tapmaq lazımdır ki, bax:

55
00:02:44,000 --> 00:02:47,000
əsas, dizi, min və max.

56
00:02:47,000 --> 00:02:51,000
Əsas biz əvvəlki Məsələn belə 144, axtarır ki sayı.

57
00:02:51,000 --> 00:02:54,000
Array biz axtarış ki nömrələri siyahısı.

58
00:02:54,000 --> 00:02:57,000
Min və max minimum və maksimum vəzifələrin göstəriciləri var

59
00:02:57,000 --> 00:02:59,000
Hal-hazırda baxırıq ki.

60
00:02:59,000 --> 00:03:03,000
Beləliklə, biz başlattığınızda, min sıfır olacaq və max serialın maksimum göstərici olacaq.

61
00:03:03,000 --> 00:03:07,000
Biz axtarış kiçildə kimi, min və max yeniləyir

62
00:03:07,000 --> 00:03:10,000
biz hələ daxil axtarır ki, yalnız bir sıra olmaq

63
00:03:10,000 --> 00:03:12,000
>> Ilk maraqlı hissəsi keçmək edək.

64
00:03:12,000 --> 00:03:14,000
Biz ilk şey, orta tap

65
00:03:14,000 --> 00:03:19,000
ortasında biz hələ nəzərdən ki, serialın min və max arasında olduğunu index.

66
00:03:19,000 --> 00:03:22,000
Sonra biz orta yerdə serialın dəyəri baxmaq

67
00:03:22,000 --> 00:03:25,000
biz axtarır ki sayı əsas az olduqda və görürük.

68
00:03:25,000 --> 00:03:27,000
Ki, vəziyyəti sayı az olarsa,

69
00:03:27,000 --> 00:03:31,000
sonra əsas ki, vəziyyəti sol bütün nömrələri daha böyük deməkdir.

70
00:03:31,000 --> 00:03:33,000
Beləliklə, biz yenə ikili axtarış funksiyası zəng edə bilərsiniz

71
00:03:33,000 --> 00:03:36,000
lakin bu zaman yalnız yarısı oxumaq min və max parametrləri updating

72
00:03:36,000 --> 00:03:40,000
ki və ya daha çox biz yalnız baxdı dəyəri bərabərdir.

73
00:03:40,000 --> 00:03:44,000
Digər tərəfdən, əsas serialın cari orta olan saydan az olarsa,

74
00:03:44,000 --> 00:03:47,000
biz sola getmək və daha çox olan bütün nömrələr ignore etmək istəyirəm.

75
00:03:47,000 --> 00:03:52,000
Yenə min və max Updated çeşidi ilə ikili axtarış lakin bu zaman zəng

76
00:03:52,000 --> 00:03:54,000
yalnız aşağı yarım daxildir.

77
00:03:54,000 --> 00:03:57,000
Serialın cari orta olan dəyəri nə varsa,

78
00:03:57,000 --> 00:04:01,000
daha böyük, nə də əsas daha kiçik, o, əsas bərabər olmalıdır.

79
00:04:01,000 --> 00:04:05,000
Beləliklə, biz sadəcə, mövcud orta göstərici ola bilər, və biz tamamlayın.

80
00:04:05,000 --> 00:04:09,000
Nəhayət, burada bu çek halda üçün ki sayı

81
00:04:09,000 --> 00:04:11,000
biz axtarış nömrələr sıra həqiqətən deyil.

82
00:04:11,000 --> 00:04:14,000
Əgər biz axtarır ki, bir sıra maksimum index

83
00:04:14,000 --> 00:04:17,000
minimum daha heç azdır ki, biz çox getdi sonra deməkdir.

84
00:04:17,000 --> 00:04:20,000
Sayı daxil array deyil olduğundan, biz -1 qayıtmaq

85
00:04:20,000 --> 00:04:24,000
heç bir şey qeyd edib.

86
00:04:24,000 --> 00:04:26,000
>> Siz, bu alqoritm işləmək üçün qeyd ola bilər

87
00:04:26,000 --> 00:04:28,000
nömrələrin siyahısına sıralanır var.

88
00:04:28,000 --> 00:04:31,000
Başqa sözlə, biz yalnız ikili axtarış istifadə edərək 144 tapa bilərsiniz

89
00:04:31,000 --> 00:04:34,000
bütün nömrələri aşağı olan ən yüksək əmr olunur.

90
00:04:34,000 --> 00:04:38,000
Bu halda deyil, biz hər addımda nömrələri yarısı istisna edə bilməz.

91
00:04:38,000 --> 00:04:40,000
Belə ki, 2 variantları var.

92
00:04:40,000 --> 00:04:43,000
Ya biz, ikili axtarış istifadə edərək əvvəl çeşidlənməmiş siyahısını almaq və sıralayabilirsiniz

93
00:04:43,000 --> 00:04:48,000
və ya biz bu nömrələrin əlavə kimi nömrələrin siyahısına sıralanır əmin edə bilərsiniz.

94
00:04:48,000 --> 00:04:50,000
Belə ki, əvəzinə biz axtarmaq üçün yalnız zaman çeşidlənməsi ki,

95
00:04:50,000 --> 00:04:53,000
niyə hər zaman sıralaması siyahısını saxlamaq deyil?

96
00:04:53,000 --> 00:04:57,000
>> Eyni zamanda imkan isə nömrələrin siyahısını saxlamaq üçün bir yol sıralanır

97
00:04:57,000 --> 00:04:59,000
Bu siyahı sayı əlavə və ya hərəkət

98
00:04:59,000 --> 00:05:02,000
ikili axtarış ağac deyilən bir şey istifadə edir.

99
00:05:02,000 --> 00:05:05,000
A ikili axtarış ağac 3 xüsusiyyətləri var ki, data strukturu.

100
00:05:05,000 --> 00:05:09,000
Birincisi, hər node sol subtree az olan yalnız dəyərlər şey

101
00:05:09,000 --> 00:05:11,000
və ya node dəyəri bərabər.

102
00:05:11,000 --> 00:05:15,000
İkincisi, bir node hüququ subtree yalnız daha çox olan dəyərləri ehtiva

103
00:05:15,000 --> 00:05:17,000
və ya node dəyəri bərabər.

104
00:05:17,000 --> 00:05:20,000
Bütün qovşaqlarının və nəhayət, sol və sağ subtrees həm

105
00:05:20,000 --> 00:05:23,000
də ikili axtarış ağacları daxildir.

106
00:05:23,000 --> 00:05:26,000
Biz əvvəllər istifadə olunan eyni nömrə ilə nümunə baxaq.

107
00:05:26,000 --> 00:05:30,000
Kompüter elm ağac əvvəl görüldü heç vaxt olan sizin üçün,

108
00:05:30,000 --> 00:05:34,000
Mənə bir kompüter ağac aşağı artır ki, siz izah edərək başlamaq imkan verir.

109
00:05:34,000 --> 00:05:36,000
Bəli, vərdiş ağaclar fərqli olaraq,

110
00:05:36,000 --> 00:05:38,000
kompüter elm ağac kökü, üst edir

111
00:05:38,000 --> 00:05:41,000
və yarpaqları altında var.

112
00:05:41,000 --> 00:05:45,000
Hər bir kiçik qutu bir node adlandırırlar və qovşaqlarının kənarları bir-birinə bağlıdır.

113
00:05:45,000 --> 00:05:48,000
Belə ki, bu ağacın kökü, dəyəri 13 ilə node dəyəri

114
00:05:48,000 --> 00:05:52,000
hansı dəyərlər 5 və 34 ilə 2 uşaq qovşaqlarının var.

115
00:05:52,000 --> 00:05:57,000
A subtree yalnız bütün ağac bir alt bölüm baxaraq formalaşır ki, ağac.

116
00:05:57,000 --> 00:06:03,000
>> Məsələn, node 3-sol subtree the qovşaqlarının 0, 1, 2 yaratdığı ağac.

117
00:06:03,000 --> 00:06:06,000
Belə ki, biz ikili axtarış ağac xüsusiyyətləri geri əgər,

118
00:06:06,000 --> 00:06:09,000
biz, ağac hər node yəni bütün 3 xassələri uyğun bax

119
00:06:09,000 --> 00:06:15,000
sol subtree yalnız az və ya node dəyəri eyni dəyərlər ehtiva edir;

120
00:06:15,000 --> 00:06:16,000
bütün qovşaqlarının hüququ subtree

121
00:06:16,000 --> 00:06:19,000
yalnız daha çox və ya node dəyəri eyni dəyərlər ehtiva edir; və

122
00:06:19,000 --> 00:06:25,000
bütün qovşaqlarının sol və sağ, həm də subtrees də ikili axtarış ağacları daxildir.

123
00:06:25,000 --> 00:06:28,000
Bu ağac müxtəlif görünür baxmayaraq, bu düzgün ikili axtarış ağac

124
00:06:28,000 --> 00:06:30,000
ədəd eyni üçün.

125
00:06:30,000 --> 00:06:32,000
Əslində kimi, yaratmaq bilər ki, çox mümkün yolları var

126
00:06:32,000 --> 00:06:35,000
bu nömrələr cari ikili axtarış ağac.

127
00:06:35,000 --> 00:06:38,000
Yaxşı, biz yaradılmış ilk bir geri imkan verir.

128
00:06:38,000 --> 00:06:40,000
Belə ki, bu ağacları ilə nə edə bilər?

129
00:06:40,000 --> 00:06:44,000
Bəli, biz çox sadəcə minimum və maksimum dəyərləri tapa bilərsiniz.

130
00:06:44,000 --> 00:06:46,000
Minimum dəyərlər həmişə sola gedərək bilər

131
00:06:46,000 --> 00:06:48,000
səfər çox qovşaqlarının var qədər.

132
00:06:48,000 --> 00:06:53,000
Əksinə, maksimum tapmaq üçün sadəcə yalnız hər vaxt doğru enir.

133
00:06:54,000 --> 00:06:56,000
>> Hər hansı digər sayı tapmaq minimum və ya maksimum deyil

134
00:06:56,000 --> 00:06:58,000
kimi asandır.

135
00:06:58,000 --> 00:07:00,000
Biz sayı 89 aradığınız söyləyin.

136
00:07:00,000 --> 00:07:03,000
Biz sadəcə, hər bir node dəyəri kontrol və sol və ya sağ getmək

137
00:07:03,000 --> 00:07:06,000
node dəyəri az və ya daha çox olub asılı olaraq

138
00:07:06,000 --> 00:07:08,000
biz aradığınız bir.

139
00:07:08,000 --> 00:07:11,000
Belə ki, 13-kök başlayaraq, biz 89 daha çox olduğunu görürük

140
00:07:11,000 --> 00:07:13,000
və biz doğru gedin.

141
00:07:13,000 --> 00:07:16,000
Sonra 34 üçün node görmək və yenə biz doğru gedin.

142
00:07:16,000 --> 00:07:20,000
89 hələ 55-dən çox, belə ki, biz doğru gedir davam edir.

143
00:07:20,000 --> 00:07:24,000
Biz 144 dəyəri ilə node ilə gəlmək və sol gedin.

144
00:07:24,000 --> 00:07:26,000
Yalnız və dərhal, 89 sağ var.

145
00:07:26,000 --> 00:07:31,000
>> Biz nə edə bilər ki, başqa bir şey bir inorder traversal həyata tərəfindən bütün nömrələri çap edir.

146
00:07:31,000 --> 00:07:35,000
Bir inorder traversal sol subtree hər şeyi çap etmək deməkdir

147
00:07:35,000 --> 00:07:37,000
node özü çap izlədi

148
00:07:37,000 --> 00:07:40,000
və sonra sağ subtree hər şeyi həyata çap izlədi.

149
00:07:40,000 --> 00:07:43,000
Məsələn, bizim sevimli ikili axtarış ağac qoy

150
00:07:43,000 --> 00:07:46,000
və sorted üçün nömrələri çap.

151
00:07:46,000 --> 00:07:49,000
Biz 13-kök başlamaq, lakin çap 13 əvvəl çap etmək

152
00:07:49,000 --> 00:07:51,000
sol subtree hər şey.

153
00:07:51,000 --> 00:07:55,000
Belə ki, 5 gedin. Biz hələ ki, sol ən node tapmaq qədər ağac daha aşağı getmək

154
00:07:55,000 --> 00:07:57,000
olan sıfır.

155
00:07:57,000 --> 00:08:00,000
Çap sıfır sonra, biz 1-geri getmək və çap.

156
00:08:00,000 --> 00:08:03,000
Sonra 2 olan, sağ subtree getmək və çap.

157
00:08:03,000 --> 00:08:05,000
İndi biz ki, subtree ilə tamamlayın

158
00:08:05,000 --> 00:08:07,000
biz 3-geri getmək və onu çap edə bilərsiniz.

159
00:08:07,000 --> 00:08:11,000
Qədər geri davam, biz 8 sonra 5 çap və.

160
00:08:11,000 --> 00:08:13,000
İndi biz bütün başa ki, subtree sol

161
00:08:13,000 --> 00:08:17,000
biz 13 çap və sağ subtree haqqında iş başlaya bilərsiniz.

162
00:08:17,000 --> 00:08:21,000
Biz 34-aşağı hop, amma çap 34 əvvəl biz onun sol subtree çap var.

163
00:08:21,000 --> 00:08:27,000
Belə ki, 21 çap, sonra biz 34 çap və onun sağ subtree ziyarət almaq.

164
00:08:27,000 --> 00:08:31,000
55 heç sol subtree ildən, biz onu çap və onun sağ subtree üçün davam edir.

165
00:08:31,000 --> 00:08:36,000
144 bir sol subtree var və belə biz, 144 sonra 89 çap

166
00:08:36,000 --> 00:08:39,000
233 və nəhayət sağ ən node.

167
00:08:39,000 --> 00:08:44,000
Burada o, bütün nömrələri aşağı olan ən yüksək üçün çap olunur.

168
00:08:44,000 --> 00:08:47,000
>> Ağac bir şey əlavə həmçinin nisbətən ağrısız edir.

169
00:08:47,000 --> 00:08:51,000
Biz bütün biz 3 ikili axtarış ağac xassələri riayət əmin edir

170
00:08:51,000 --> 00:08:53,000
yer olduğu və sonra dəyər daxil edin.

171
00:08:53,000 --> 00:08:55,000
Gəlin biz 7 dəyəri daxil etmək istəyirik deyirlər.

172
00:08:55,000 --> 00:08:58,000
7-dən az 13 olduğu üçün, sol gedin.

173
00:08:58,000 --> 00:09:01,000
Lakin 5-dən böyük, buna görə biz doğru axır.

174
00:09:01,000 --> 00:09:04,000
Bu 8 və 8 bir yarpaq node deyil az olduğundan, biz 8-sol uşaq üçün 7 əlavə edin.

175
00:09:04,000 --> 00:09:09,000
İşte! Biz ikili axtarış ağac bir sıra əlavə etdik.

176
00:09:09,000 --> 00:09:12,000
>> Biz şeyi əlavə edə bilərsiniz, biz daha yaxşı həmçinin şeyi silmək mümkün.

177
00:09:12,000 --> 00:09:14,000
Təəssüf ki, bizim üçün, silmə bir az daha mürəkkəbdir -

178
00:09:14,000 --> 00:09:16,000
çox, lakin yalnız bir az deyil.

179
00:09:16,000 --> 00:09:18,000
Hesab edirik ki, 3 müxtəlif ssenariləri var

180
00:09:18,000 --> 00:09:21,000
binar axtarış ağac elementləri silerken.

181
00:09:21,000 --> 00:09:24,000
Birincisi, asan iş element bir yarpaq node olmasıdır.

182
00:09:24,000 --> 00:09:27,000
Bu halda, biz sadəcə silin və biznes ilə getmək.

183
00:09:27,000 --> 00:09:30,000
Biz yalnız əlavə edib ki, 7 silmək istədiyiniz söyləyin.

184
00:09:30,000 --> 00:09:34,000
Bəli, biz sadəcə tapmaq, aradan qaldırılması və bu.

185
00:09:35,000 --> 00:09:37,000
Node yalnız 1 uşaq var növbəti haldır.

186
00:09:37,000 --> 00:09:40,000
Burada node silə bilərsiniz, ancaq ilk əmin etmək

187
00:09:40,000 --> 00:09:42,000
indi kimsəsiz qalan subtree qoşulmaq üçün

188
00:09:42,000 --> 00:09:44,000
node və valideyn biz yalnız silindi.

189
00:09:44,000 --> 00:09:47,000
Biz ağac 3 silmək istədiyiniz söyləyin.

190
00:09:47,000 --> 00:09:50,000
Biz node uşaq element almaq və node müəssisənin əlavə edin.

191
00:09:50,000 --> 00:09:54,000
Bu halda, biz indi 5 1 əlavə edirik.

192
00:09:54,000 --> 00:09:57,000
Biz bilirik çünki Bu, ikili axtarış ağac əmlak görə, problem olmadan işləyir

193
00:09:57,000 --> 00:10:01,000
3-sol subtree ki, hər şey az 5 idi.

194
00:10:01,000 --> 00:10:05,000
3 in subtree qayğı indi ki, biz onu silə bilərsiniz.

195
00:10:05,000 --> 00:10:08,000
Üçüncü və son halda ən kompleksidir.

196
00:10:08,000 --> 00:10:11,000
Biz silmek, istədiyiniz node 2 övladı var Bu belədir.

197
00:10:11,000 --> 00:10:15,000
Bunu etmək üçün, biz ilk, növbəti ən böyük dəyəri var ki, node tapmaq

198
00:10:15,000 --> 00:10:18,000
iki dəyişdirmək və sonra bu node silin.

199
00:10:18,000 --> 00:10:22,000
Növbəti böyük dəyər 2 uşaq özü ola bilməz ki node edək

200
00:10:22,000 --> 00:10:26,000
onun sol uşaq növbəti böyük üçün daha yaxşı namizəd olacağını ildən.

201
00:10:26,000 --> 00:10:30,000
Buna görə də, 2 övladı bir node silmə, 2 qovşaqlarının dəyişdirmə təşkil

202
00:10:30,000 --> 00:10:33,000
və sonra silmek 2 yuxarıda qeyd olunan qaydalarına 1 işləndiyini.

203
00:10:33,000 --> 00:10:37,000
Məsələn, qoy biz kök node, 13 silmək istəyirsiniz.

204
00:10:37,000 --> 00:10:39,000
Biz ilk şey biz ağac növbəti böyük dəyər tapmaq deyil

205
00:10:39,000 --> 00:10:41,000
ki, bu halda, 21-dir.

206
00:10:41,000 --> 00:10:46,000
Biz 13 bir yarpaq və 21 mərkəzi qrup node edilməsi, 2 qovşaqlarının dəyişdirmək.

207
00:10:46,000 --> 00:10:49,000
İndi biz sadəcə 13 silə bilərsiniz.

208
00:10:50,000 --> 00:10:53,000
>> Əvvəllər üçün alluded, cari ikili axtarış ağac etmək üçün bir çox mümkün yolları var.

209
00:10:53,000 --> 00:10:56,000
Təəssüf ki, bizim üçün, bəziləri daha pisdir.

210
00:10:56,000 --> 00:10:59,000
Biz ikili axtarış ağac qurmaq Məsələn, nə olar

211
00:10:59,000 --> 00:11:01,000
sayı sıralanır siyahısı?

212
00:11:01,000 --> 00:11:04,000
Bütün nömrələri yalnız hər bir addım doğru əlavə olunur.

213
00:11:04,000 --> 00:11:06,000
Biz bir sıra axtarmaq istəyirsinizsə,

214
00:11:06,000 --> 00:11:08,000
biz heç bir seçimi var, lakin yalnız hər bir addım doğru baxmaq.

215
00:11:08,000 --> 00:11:11,000
Bu bütün xətti axtarış daha yaxşı deyil.

216
00:11:11,000 --> 00:11:13,000
Biz burada onları əhatə edəcək, baxmayaraq ki, daha mürəkkəb, digər var

217
00:11:13,000 --> 00:11:16,000
Bu baş vermir ki, əmin olun data strukturlar.

218
00:11:16,000 --> 00:11:18,000
Lakin, bu qarşısını almaq üçün edilə bilər ki, sadə bir şey deyil

219
00:11:18,000 --> 00:11:21,000
yalnız təsadüfi shuffle giriş dəyərlər.

220
00:11:21,000 --> 00:11:26,000
Bu təsadüfi təsadüfən nömrələri qarışdırılmış siyahısı çeşidlənir ehtimalı var.

221
00:11:26,000 --> 00:11:29,000
Bu halda olsaydı, kazinolarda uzun iş qalmaq olmaz.

222
00:11:29,000 --> 00:11:31,000
>> Burada var.

223
00:11:31,000 --> 00:11:34,000
İndi ikili axtarış və ikili axtarış ağac bilirik.

224
00:11:34,000 --> 00:11:36,000
Mən Patrick Schmid oldum və bu CS50 edir.

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

226
00:11:38,000 --> 00:11:43,000
Bir Aşkar yolu siyahısını scan olardı ... [beep]

227
00:11:43,000 --> 00:11:46,000
... Əşyaların sayı ... yep

228
00:11:46,000 --> 00:11:50,000
[Gülür]

229
00:11:50,000 --> 00:11:55,000
... 234 ... augh və node göndərin.

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