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
Але, як вы праглядаеце Aladdin, Аліса, Арыэль, і гэтак далей,

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
Мінімальная і максімальная з'яўляюцца паказчыкі мінімальнай і максімальнай пазіцыі

59
00:02:57,000 --> 00:02:59,000
што мы зараз глядзім.

60
00:02:59,000 --> 00:03:03,000
Таму, калі мы пачнем, мін будзе роўная нулю і Макс будзе максімальным індэксам масіву.

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
Усё, што нам трэба зрабіць, гэта пераканацца, што мы ідзём 3 двайковых ўласцівасці дрэва пошуку

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
Voila! Мы дадалі шэраг нашых бінарнае дрэва пошуку.

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
>> Ура! Гэта было -