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

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

3
00:00:04,000 --> 00:00:07,000
[Mae hyn yn CS50. - CS50.TV]

4
00:00:07,000 --> 00:00:09,000
>> Os byddaf yn rhoi i chi restr o enwau cymeriad Disney yn nhrefn yr wyddor

5
00:00:09,000 --> 00:00:11,000
ac yn gofyn i chi ddod o hyd i Mickey Mouse,

6
00:00:11,000 --> 00:00:13,000
sut fyddech chi'n mynd ati i wneud hyn?

7
00:00:13,000 --> 00:00:15,000
Un ffordd amlwg fyddai i sganio y rhestr o'r cychwyn

8
00:00:15,000 --> 00:00:18,000
ac yn gwirio pob enw i weld os yw'n Mickey.

9
00:00:18,000 --> 00:00:22,000
Ond wrth i chi ddarllen Aladdin, Alice, Ariel, ac yn y blaen,

10
00:00:22,000 --> 00:00:25,000
byddwch yn gyflym yn sylweddoli nad yw dechrau ar flaen y rhestr yn syniad da.

11
00:00:25,000 --> 00:00:29,000
Iawn, efallai y dylech ddechrau gweithio tuag yn ôl o ddiwedd y rhestr.

12
00:00:29,000 --> 00:00:33,000
Nawr eich bod yn darllen Tarzan, Pwyth, Snow White, ac yn y blaen.

13
00:00:33,000 --> 00:00:36,000
Still, nid yw hyn yn ymddangos fel y ffordd orau o fynd o'i chwmpas hi.

14
00:00:36,000 --> 00:00:38,000
>> Wel, mewn ffordd arall y gallech fynd ati i wneud hyn yw i geisio cyfyngu'r i lawr

15
00:00:38,000 --> 00:00:41,000
y rhestr o enwau sydd yn rhaid i chi edrych ar.

16
00:00:41,000 --> 00:00:43,000
Gan eich bod yn gwybod eu bod yn nhrefn yr wyddor,

17
00:00:43,000 --> 00:00:45,000
fe allech chi jyst yn edrych ar yr enwau yn y nghanol y rhestr

18
00:00:45,000 --> 00:00:49,000
a gwirio os yw Mickey Mouse yn cyn neu ar ôl yr enw hwn.

19
00:00:49,000 --> 00:00:51,000
O edrych ar yr enw olaf yn yr ail golofn

20
00:00:51,000 --> 00:00:54,000
byddech yn sylweddoli bod M am Mickey dod ar ôl J am Jasmine,

21
00:00:54,000 --> 00:00:57,000
felly byddech yn anwybyddu'r hanner cyntaf y rhestr.

22
00:00:57,000 --> 00:00:59,000
Yna mae'n debyg y byddech yn edrych ar frig y golofn olaf

23
00:00:59,000 --> 00:01:02,000
a gweld ei fod yn dechrau gyda Rapunzel.

24
00:01:02,000 --> 00:01:06,000
Mickey dod cyn Rapunzel; edrych fel y gallwn anwybyddu'r golofn olaf yn ogystal.

25
00:01:06,000 --> 00:01:08,000
Gan barhau â'r strategaeth chwilio, byddwch yn gyflym yn gweld bod Mickey

26
00:01:08,000 --> 00:01:11,000
yn hanner cyntaf y rhestr sy'n weddill o enwau

27
00:01:11,000 --> 00:01:14,000
ac yn olaf dod o hyd i Mickey cuddio rhwng Merlin a Minnie.

28
00:01:14,000 --> 00:01:17,000
>> Hyn yr ydych yn unig oedd yn chwilio yn y bôn deuaidd.

29
00:01:17,000 --> 00:01:22,000
Gan fod y enw'n awgrymu, mae'n cyflawni ei strategaeth chwilio mewn mater deuaidd.

30
00:01:22,000 --> 00:01:24,000
Beth yw ystyr hyn?

31
00:01:24,000 --> 00:01:27,000
Wel, o ystyried rhestr o eitemau didoli, y deuaidd algorithm chwilio yn gwneud penderfyniad deuaidd -

32
00:01:27,000 --> 00:01:33,000
chwith neu i'r dde, yn fwy na neu'n llai na, yn nhrefn yr wyddor cyn neu ar ôl - ar bob pwynt.

33
00:01:33,000 --> 00:01:35,000
Nawr bod gennym enw sy'n mynd ynghyd â hyn algorithm chwilio,

34
00:01:35,000 --> 00:01:38,000
gadewch i ni edrych ar enghraifft arall, ond y tro hwn gyda rhestr o rifau didoli.

35
00:01:38,000 --> 00:01:43,000
Dweud rydym yn chwilio am y rhif 144 yn y rhestr hon o rifau didoli.

36
00:01:43,000 --> 00:01:46,000
Yn union fel o'r blaen, rydym yn dod o hyd i'r rhif sydd yn y canol -

37
00:01:46,000 --> 00:01:50,000
sydd yn yr achos hwn yn 13 - a gweld os 144 yn fwy na neu'n llai na 13.

38
00:01:50,000 --> 00:01:54,000
Ers mae'n amlwg yn fwy na 13, gallwn anwybyddu popeth sy'n 13 neu lai

39
00:01:54,000 --> 00:01:57,000
a dim ond yn canolbwyntio ar yr hanner arall.

40
00:01:57,000 --> 00:01:59,000
Ers i ni yn awr yn cael nifer hyd yn oed o eitemau ar ôl,

41
00:01:59,000 --> 00:02:01,000
rydym yn syml ddewis rhif sy'n agos at y canol.

42
00:02:01,000 --> 00:02:03,000
Yn yr achos hwn rydym yn dewis 55.

43
00:02:03,000 --> 00:02:06,000
Gallem fod wedi yr un mor hawdd dewis 89.

44
00:02:06,000 --> 00:02:11,000
Iawn. Unwaith eto, 144 yn fwy na 55, felly rydym yn mynd i'r dde.

45
00:02:11,000 --> 00:02:14,000
Yn ffodus i ni, y rhif canol nesaf yw 144,

46
00:02:14,000 --> 00:02:16,000
un yr ydym yn chwilio amdano.

47
00:02:16,000 --> 00:02:21,000
Felly, er mwyn dod o hyd i 144 gan ddefnyddio chwiliad deuaidd, rydym yn gallu ddod o hyd iddo mewn dim ond 3 camau.

48
00:02:21,000 --> 00:02:24,000
Os ydym wedi defnyddio chwiliad llinol yma, byddai wedi cymryd 12 cam i ni.

49
00:02:24,000 --> 00:02:28,000
Fel mater o ffaith, gan fod y dull hwn chwilio yn haneru'r nifer o eitemau

50
00:02:28,000 --> 00:02:31,000
mae'n rhaid iddo edrych ar ar bob cam, bydd yn dod o hyd i'r eitem ei fod yn chwilio am

51
00:02:31,000 --> 00:02:35,000
mewn tua y log y nifer o eitemau yn y rhestr.

52
00:02:35,000 --> 00:02:37,000
Nawr ein bod wedi gweld 2 enghraifft, gadewch i ni edrych ar

53
00:02:37,000 --> 00:02:41,000
rhywfaint o pseudocode ar gyfer swyddogaeth recursive sy'n gweithredu chwiliad deuaidd.

54
00:02:41,000 --> 00:02:44,000
Gan ddechrau ar y top, rydym yn gweld bod yn rhaid inni ddod o hyd i swyddogaeth sy'n cymryd 4 dadleuon:

55
00:02:44,000 --> 00:02:47,000
allweddol, array, mun, a max.

56
00:02:47,000 --> 00:02:51,000
Yr allwedd yw nifer yr ydym yn chwilio amdanynt, fel 144 yn yr enghraifft flaenorol.

57
00:02:51,000 --> 00:02:54,000
Array yn y rhestr o niferoedd yr ydym yn ei chwilio.

58
00:02:54,000 --> 00:02:57,000
Min a max yn y mynegeion o'r swyddi isaf ac uchaf

59
00:02:57,000 --> 00:02:59,000
ein bod ar hyn o bryd yn edrych ar.

60
00:02:59,000 --> 00:03:03,000
Felly, pan fyddwn yn dechrau, bydd min yn sero, a bydd uchafswm fydd y mynegai mwyaf y rhesi.

61
00:03:03,000 --> 00:03:07,000
Wrth i ni gyfyngu'r chwilio i lawr, byddwn yn diweddaru mun a max

62
00:03:07,000 --> 00:03:10,000
i fod yr un ystod ein bod yn dal i chwilio i mewn

63
00:03:10,000 --> 00:03:12,000
>> Gadewch i sgip i'r rhan ddiddorol yn gyntaf.

64
00:03:12,000 --> 00:03:14,000
Y peth cyntaf a wnawn yw dod o hyd i'r man canol,

65
00:03:14,000 --> 00:03:19,000
y mynegai sydd hanner ffordd rhwng y lleiafswm a'r uchafswm y rhesi yr ydym yn dal i ystyried.

66
00:03:19,000 --> 00:03:22,000
Yna rydym yn edrych ar y gwerth y rhesi yn y lleoliad hwnnw bwynt canol

67
00:03:22,000 --> 00:03:25,000
a gweld os bydd y nifer yr ydym yn chwilio am yn llai na hynny allweddol.

68
00:03:25,000 --> 00:03:27,000
Os yw'r nifer yn y sefyllfa honno yn llai,

69
00:03:27,000 --> 00:03:31,000
yna mae'n golygu bod y allweddol yn fwy na'r holl rhifau i'r chwith y sefyllfa honno.

70
00:03:31,000 --> 00:03:33,000
Felly, gallwn alw swyddogaeth chwilio deuaidd eto,

71
00:03:33,000 --> 00:03:36,000
ond y tro hwn diweddaru'r mun a paramedrau max i ddarllen dim ond hanner

72
00:03:36,000 --> 00:03:40,000
sy'n fwy na neu'n hafal i werth ydym yn unig yn edrych ar.

73
00:03:40,000 --> 00:03:44,000
Ar y llaw arall, os yw'r allweddol yn llai na'r nifer yn y man canol ar hyn o bryd y rhesi,

74
00:03:44,000 --> 00:03:47,000
ydym am fynd i'r chwith ac yn anwybyddu'r holl rifau sy'n fwy.

75
00:03:47,000 --> 00:03:52,000
Unwaith eto, rydym yn galw chwiliad deuaidd ond y tro hwn gyda'r ystod o mun a max updated

76
00:03:52,000 --> 00:03:54,000
i gynnwys dim ond yr hanner isaf.

77
00:03:54,000 --> 00:03:57,000
Os yw'r gwerth yn y man canol ar hyn o bryd yn yr amrywiaeth yw'n

78
00:03:57,000 --> 00:04:01,000
mwy na nac yn llai nag yn allwedd, yna rhaid iddo fod yn hafal i'r allwedd.

79
00:04:01,000 --> 00:04:05,000
Felly, gallwn yn syml ddychwelyd y mynegai man canol ar hyn o bryd, ac rydym yn ei wneud.

80
00:04:05,000 --> 00:04:09,000
Yn olaf, mae'r gwiriad yma ar gyfer yr achos bod y nifer

81
00:04:09,000 --> 00:04:11,000
Nid yw mewn gwirionedd yn yr amrywiaeth o niferoedd yr ydym yn ei chwilio.

82
00:04:11,000 --> 00:04:14,000
Os yw'r mynegai uchafswm yr ystod ein bod yn chwilio am

83
00:04:14,000 --> 00:04:17,000
byth yn llai na'r isafswm, mae hynny'n golygu ein bod wedi mynd yn rhy bell.

84
00:04:17,000 --> 00:04:20,000
Gan nad yw'r nifer yn yn yr amrywiaeth mewnbwn, byddwn yn dychwelyd -1

85
00:04:20,000 --> 00:04:24,000
i ddangos bod ni ddaethpwyd o hyd.

86
00:04:24,000 --> 00:04:26,000
>> Efallai eich bod wedi sylwi bod ar gyfer y algorithm i weithio,

87
00:04:26,000 --> 00:04:28,000
y rhestr o rifau wedi rhoi trefn arno.

88
00:04:28,000 --> 00:04:31,000
Mewn geiriau eraill, ni allwn ond dod o hyd i 144 gan ddefnyddio chwiliad deuaidd

89
00:04:31,000 --> 00:04:34,000
os yw'r holl rifau yn cael eu harchebu gan isaf i'r uchaf.

90
00:04:34,000 --> 00:04:38,000
Os nad yw hyn yn wir, ni fyddem yn gallu gwahardd hanner y niferoedd ar bob cam.

91
00:04:38,000 --> 00:04:40,000
Felly, rydym wedi 2 ddewis.

92
00:04:40,000 --> 00:04:43,000
Naill ai y gallwn gymryd rhestr heb eu didoli ac yn datrys y broblem cyn defnyddio chwiliad deuaidd,

93
00:04:43,000 --> 00:04:48,000
neu gallwn wneud yn siŵr fod y rhestr o rifau yn cael ei ddidoli wrth i ni ychwanegu rhifau ato.

94
00:04:48,000 --> 00:04:50,000
Felly, yn hytrach na didoli dim ond pan fydd yn rhaid i chwilio,

95
00:04:50,000 --> 00:04:53,000
beth am gadw rhestr datrys ar bob adeg?

96
00:04:53,000 --> 00:04:57,000
>> Un ffordd i gadw rhestr o rifau didoli ar yr un pryd caniatáu

97
00:04:57,000 --> 00:04:59,000
un i ychwanegu neu symud rhifau o'r rhestr hon

98
00:04:59,000 --> 00:05:02,000
yw drwy ddefnyddio rhywbeth o'r enw coeden chwiliad deuaidd.

99
00:05:02,000 --> 00:05:05,000
Mae deuaidd coeden chwilio yn strwythur data sydd 3 eiddo.

100
00:05:05,000 --> 00:05:09,000
Yn gyntaf, y Terfynau Chwilio chwith i unrhyw nod yn cynnwys werthoedd yn unig sydd yn llai na

101
00:05:09,000 --> 00:05:11,000
neu'n hafal i werth y nod yn.

102
00:05:11,000 --> 00:05:15,000
Yn ail, yr hawl Terfynau Chwilio o nod yn unig yn cynnwys gwerthoedd sy'n fwy na

103
00:05:15,000 --> 00:05:17,000
neu'n hafal i werth y nod yn.

104
00:05:17,000 --> 00:05:20,000
Ac, yn olaf, y subtrees chwith a dde yr holl nodau

105
00:05:20,000 --> 00:05:23,000
hefyd coed chwiliad deuaidd.

106
00:05:23,000 --> 00:05:26,000
Gadewch i ni edrych ar enghraifft gyda'r rhifau un a ddefnyddiwyd gennym yn gynharach.

107
00:05:26,000 --> 00:05:30,000
I'r rhai ohonoch nad ydynt erioed wedi gweld gwyddoniaeth gyfrifiadurol coeden o'r blaen,

108
00:05:30,000 --> 00:05:34,000
gadewch i mi ddechrau drwy ddweud wrthych fod cyfrifiadur coed gwyddoniaeth yn tyfu tuag at i lawr.

109
00:05:34,000 --> 00:05:36,000
Ie, yn wahanol i goed yr ydych yn gyfarwydd â,

110
00:05:36,000 --> 00:05:38,000
gwraidd gwyddoniaeth gyfrifiadurol goeden ar y brig,

111
00:05:38,000 --> 00:05:41,000
ac mae'r dail ar y gwaelod.

112
00:05:41,000 --> 00:05:45,000
Mae pob blwch bach a elwir yn nod, a'r nodau yn cael eu cysylltu â'i gilydd gan ymylon.

113
00:05:45,000 --> 00:05:48,000
Felly, wrth wraidd y goeden hon yn werth nod gyda'r gwerth 13,

114
00:05:48,000 --> 00:05:52,000
sydd â 2 nodau plant â'r gwerthoedd 5 a 34.

115
00:05:52,000 --> 00:05:57,000
Mae Terfynau Chwilio yw'r goeden sy'n cael ei ffurfio dim ond drwy edrych ar is-adran y goeden gyfan.

116
00:05:57,000 --> 00:06:03,000
>> Er enghraifft, y Terfynau Chwilio chwith y 3 nod yn y goeden a grëwyd gan y 0 nodau, 1, a 2.

117
00:06:03,000 --> 00:06:06,000
Felly, os ydym yn mynd yn ôl at y priodweddau chwiliad deuaidd coed,

118
00:06:06,000 --> 00:06:09,000
rydym yn gweld bod pob nod yn y goeden yn cydymffurfio â'r holl eiddo 3, sef,

119
00:06:09,000 --> 00:06:15,000
y Terfynau Chwilio chwith yn unig yn cynnwys gwerthoedd sy'n llai na neu'n hafal i werth y nod hwnnw;

120
00:06:15,000 --> 00:06:16,000
yr hawl Terfynau Chwilio pob nodau

121
00:06:16,000 --> 00:06:19,000
ond yn cynnwys gwerthoedd sy'n fwy na neu'n hafal i werth y nod; a

122
00:06:19,000 --> 00:06:25,000
subtrees chwith a'r dde yr holl nodau hefyd yn cael eu coed chwiliad deuaidd.

123
00:06:25,000 --> 00:06:28,000
Er bod y goeden yn edrych yn wahanol, mae hyn yn goeden ddeuol chwilio dilys

124
00:06:28,000 --> 00:06:30,000
am yr un set o rifau.

125
00:06:30,000 --> 00:06:32,000
Fel mater o ffaith, mae ffyrdd posibl llawer y gallwch greu

126
00:06:32,000 --> 00:06:35,000
coeden ddeuaidd chwilio ddilys o'r rhifau hyn.

127
00:06:35,000 --> 00:06:38,000
Wel, gadewch i ni fynd yn ôl i'r un cyntaf i ni greu.

128
00:06:38,000 --> 00:06:40,000
Felly, beth allwn ni ei wneud gyda'r coed?

129
00:06:40,000 --> 00:06:44,000
Wel, gallwn yn syml iawn dod o hyd i'r gwerthoedd isaf ac uchaf.

130
00:06:44,000 --> 00:06:46,000
Gall y gwerthoedd lleiaf ar gael drwy bob amser yn mynd i'r chwith

131
00:06:46,000 --> 00:06:48,000
nes nad oes nodau dim mwy i ymweld ag ef.

132
00:06:48,000 --> 00:06:53,000
I'r gwrthwyneb, i ddod o hyd i'r un mwyaf syml yn unig yn mynd i lawr i'r dde ar bob adeg.

133
00:06:54,000 --> 00:06:56,000
>> Dod o hyd i unrhyw rif arall nad yw'r isafswm neu'r uchafswm

134
00:06:56,000 --> 00:06:58,000
yr un mor hawdd.

135
00:06:58,000 --> 00:07:00,000
Dweud rydym yn chwilio am y rhif 89.

136
00:07:00,000 --> 00:07:03,000
Rydym yn syml weld beth yw gwerth pob nod a mynd i'r chwith neu i'r dde,

137
00:07:03,000 --> 00:07:06,000
yn dibynnu ar a yw gwerth y nod yn llai na neu'n fwy na

138
00:07:06,000 --> 00:07:08,000
un yr ydym yn chwilio amdano.

139
00:07:08,000 --> 00:07:11,000
Felly, gan ddechrau wrth wraidd 13, gwelwn fod 89 yn fwy,

140
00:07:11,000 --> 00:07:13,000
ac felly rydym yn mynd i'r dde.

141
00:07:13,000 --> 00:07:16,000
Yna rydym yn gweld y nod ar gyfer 34, ac unwaith eto rydym yn mynd i'r dde.

142
00:07:16,000 --> 00:07:20,000
89 yn dal yn fwy na 55, felly rydym yn parhau i fynd i'r dde.

143
00:07:20,000 --> 00:07:24,000
Yna byddwn yn dod o hyd yn nod gyda gwerth o 144 ac yn mynd i'r chwith.

144
00:07:24,000 --> 00:07:26,000
Lo ac wele, 89 yn iawn yno.

145
00:07:26,000 --> 00:07:31,000
>> Peth arall y gallwn ei wneud yw argraffu holl rifau drwy berfformio groesi inorder.

146
00:07:31,000 --> 00:07:35,000
Mae groesi inorder olygu i argraffu popeth allan yn y Terfynau Chwilio chwith

147
00:07:35,000 --> 00:07:37,000
ddilyn gan argraffu'r nod ei hun

148
00:07:37,000 --> 00:07:40,000
ac yn dilyn hynny drwy argraffu popeth allan yn yr hawl Terfynau Chwilio.

149
00:07:40,000 --> 00:07:43,000
Er enghraifft, gadewch i ni gymryd ein goeden ddeuol chwilio hoff

150
00:07:43,000 --> 00:07:46,000
ac yn argraffu'r rhifau yn eu trefn sortio.

151
00:07:46,000 --> 00:07:49,000
Rydym yn dechrau wrth wraidd o 13, ond cyn argraffu 13 mae'n rhaid i ni argraffu

152
00:07:49,000 --> 00:07:51,000
popeth yn y Terfynau Chwilio chwith.

153
00:07:51,000 --> 00:07:55,000
Felly, rydym yn mynd i 5. Rydym yn dal rhaid i ni fynd ddyfnach i lawr yn y goeden nes i ni ddod o hyd i'r nod chwith y rhan fwyaf,

154
00:07:55,000 --> 00:07:57,000
sydd yn sero.

155
00:07:57,000 --> 00:08:00,000
Ar ôl argraffu sero, rydym yn mynd yn ôl i fyny i'r 1 ac argraffu hynny.

156
00:08:00,000 --> 00:08:03,000
Yna rydym yn mynd i'r Terfynau Chwilio dde, sef 2, ac argraffu hynny.

157
00:08:03,000 --> 00:08:05,000
Nawr ein bod chi'n ei wneud gyda hynny Terfynau Chwilio,

158
00:08:05,000 --> 00:08:07,000
gallwn fynd yn ôl i fyny at y 3 a'i hargraffu.

159
00:08:07,000 --> 00:08:11,000
Parhaus yn ôl i fyny, rydym yn argraffu'r y 5 ac yna'r 8.

160
00:08:11,000 --> 00:08:13,000
Nawr ein bod wedi cwblhau'r cyfan adael Terfynau Chwilio,

161
00:08:13,000 --> 00:08:17,000
gallwn argraffu allan o'r 13 a dechrau gweithio ar y dde Terfynau Chwilio.

162
00:08:17,000 --> 00:08:21,000
Rydym hop i lawr i 34, ond cyn argraffu 34 mae'n rhaid i ni argraffu ei Terfynau Chwilio chwith.

163
00:08:21,000 --> 00:08:27,000
Felly, rydym yn argraffu 21; yna rydym yn mynd i'w argraffu 34 a ymweld â'i hawl Terfynau Chwilio.

164
00:08:27,000 --> 00:08:31,000
Ers 55 Nid oes gan Terfynau Chwilio chwith, rydym yn ei hargraffu ac yn parhau ar ei Terfynau Chwilio dde.

165
00:08:31,000 --> 00:08:36,000
144 Mae gan Terfynau Chwilio chwith, ac felly rydym yn argraffu'r 89, wedi'i ddilyn gan y 144,

166
00:08:36,000 --> 00:08:39,000
ac yn olaf y nod dde y rhan fwyaf o 233.

167
00:08:39,000 --> 00:08:44,000
Dyna ni; yr holl rhifau yn cael eu hargraffu mewn trefn o'r isaf i'r uchaf.

168
00:08:44,000 --> 00:08:47,000
>> Ychwanegu rhywbeth at y goeden yn gymharol ddi-boen yn ogystal.

169
00:08:47,000 --> 00:08:51,000
Mae pob mae'n rhaid i chi ei wneud yw gwneud yn siŵr ein bod yn dilyn 3 deuaidd eiddo chwilio coed

170
00:08:51,000 --> 00:08:53,000
ac yna rhowch y gwerth lle mae gofod.

171
00:08:53,000 --> 00:08:55,000
Lets 'ddeud rydym am i fewnosod gwerth 7.

172
00:08:55,000 --> 00:08:58,000
Ers 7 yn llai na 13, rydym yn mynd i'r chwith.

173
00:08:58,000 --> 00:09:01,000
Ond mae'n fwy na 5, felly rydym yn croesi i'r dde.

174
00:09:01,000 --> 00:09:04,000
Gan ei fod yn llai nag 8 ac 8 yn nod deilen, rydym yn ychwanegu 7 i blentyn chwith 8.

175
00:09:04,000 --> 00:09:09,000
Voila! Rydym wedi ychwanegu at ein rhif deuaidd coed chwilio.

176
00:09:09,000 --> 00:09:12,000
>> Os gallwn ychwanegu pethau, fe fyddai'n well yn gallu dileu pethau yn ogystal.

177
00:09:12,000 --> 00:09:14,000
Yn anffodus i ni, dileu yn ychydig yn fwy cymhleth -

178
00:09:14,000 --> 00:09:16,000
dim llawer, ond dim ond ychydig bach.

179
00:09:16,000 --> 00:09:18,000
Mae yna 3 senarios gwahanol y mae'n rhaid i ni ystyried

180
00:09:18,000 --> 00:09:21,000
wrth ddileu elfennau o goed chwiliad deuaidd.

181
00:09:21,000 --> 00:09:24,000
Yn gyntaf, mae'r achos hawsaf yw bod yr elfen yn nod deilen.

182
00:09:24,000 --> 00:09:27,000
Yn yr achos hwn, rydym yn syml ddileu a mynd ymlaen â'n busnes.

183
00:09:27,000 --> 00:09:30,000
Dweud ein bod am ddileu'r y 7 yr ydym newydd ei hychwanegu.

184
00:09:30,000 --> 00:09:34,000
Wel, rydym yn syml o hyd iddo, ei symud, a dyna ni.

185
00:09:35,000 --> 00:09:37,000
Mae'r achos nesaf yw os bydd y nod wedi dim ond 1 plentyn.

186
00:09:37,000 --> 00:09:40,000
Yma, gallwn ddileu'r nod, ond i ni yn gyntaf rhaid i ni sicrhau

187
00:09:40,000 --> 00:09:42,000
i gysylltu'r Terfynau Chwilio sydd ar ôl bellach riant o

188
00:09:42,000 --> 00:09:44,000
i riant y nod ydym yn dileu yn unig.

189
00:09:44,000 --> 00:09:47,000
Dweud ein bod am ddileu'r 3 o o'n goeden.

190
00:09:47,000 --> 00:09:50,000
Rydym yn cymryd yr elfen blentyn i'r nod a'i hatodi at riant y nod.

191
00:09:50,000 --> 00:09:54,000
Yn yr achos hwn, rydym yn awr yn cysylltu'r 1 i 5.

192
00:09:54,000 --> 00:09:57,000
Mae hyn yn gweithio heb broblem oherwydd ein bod yn gwybod, yn ôl i'r eiddo chwiliad deuaidd coed,

193
00:09:57,000 --> 00:10:01,000
bod popeth yn y Terfynau Chwilio chwith o 3 yn llai na 5.

194
00:10:01,000 --> 00:10:05,000
Nawr bod 3 yn Terfynau Chwilio yn cael ei gymryd gofal, gallwn ei ddileu.

195
00:10:05,000 --> 00:10:08,000
Mae'r achos drydydd ac yn olaf y mwyaf cymhleth.

196
00:10:08,000 --> 00:10:11,000
Mae hyn yn wir pan fydd y nod yr ydym am ei ddileu gan 2 o blant.

197
00:10:11,000 --> 00:10:15,000
Er mwyn gwneud hyn, rydym yn gyntaf rhaid i ni ddod o hyd i'r nod sydd â'r gwerth mwyaf nesaf,

198
00:10:15,000 --> 00:10:18,000
gyfnewid y ddau, ac yna dilëwch y nod dan sylw.

199
00:10:18,000 --> 00:10:22,000
Sylwch ar y nod sydd wedi ni all y gwerth mwyaf nesaf 2 o blant ei hun

200
00:10:22,000 --> 00:10:26,000
gan y byddai ei phlentyn ar y chwith fod yn ymgeisydd gwell ar gyfer y mwyaf nesaf.

201
00:10:26,000 --> 00:10:30,000
Felly, dileu nod gyda 2 o blant gyfystyr â gyfnewid o 2 nodau,

202
00:10:30,000 --> 00:10:33,000
ac yna dileu cael ei drin gan 1 o'r 2 rheolau uchod.

203
00:10:33,000 --> 00:10:37,000
Er enghraifft, gadewch i ni ddweud ein bod am ddileu'r, nod gwraidd 13.

204
00:10:37,000 --> 00:10:39,000
Y peth cyntaf a wnawn yw ein bod dod o hyd i'r gwerth mwyaf nesaf yn y goeden

205
00:10:39,000 --> 00:10:41,000
sydd, yn yr achos hwn, yn 21.

206
00:10:41,000 --> 00:10:46,000
Yna, byddwn yn cyfnewid y 2 nodau, gan wneud 13 a dail a 21 y nod grŵp canolog.

207
00:10:46,000 --> 00:10:49,000
Nawr gallwn yn syml dileu 13.

208
00:10:50,000 --> 00:10:53,000
>> Fel y cyfeiriodd yn gynharach, mae yna lawer o ffyrdd posibl i wneud coeden ddeuaidd chwilio dilys.

209
00:10:53,000 --> 00:10:56,000
Yn anffodus i ni, mae rhai yn waeth nag eraill.

210
00:10:56,000 --> 00:10:59,000
Er enghraifft, beth sy'n digwydd pan fyddwn yn adeiladu coeden chwiliad deuaidd

211
00:10:59,000 --> 00:11:01,000
o restr o rifau datrys?

212
00:11:01,000 --> 00:11:04,000
Mae pob rhif yn cael eu hychwanegu ychydig i'r dde ar bob cam.

213
00:11:04,000 --> 00:11:06,000
Pan rydym am i chwilio am rif,

214
00:11:06,000 --> 00:11:08,000
nid oes gennym ddewis ond dim ond i edrych ar yr hawl ar bob cam.

215
00:11:08,000 --> 00:11:11,000
Nid yw hyn yn well na chwiliad llinol o gwbl.

216
00:11:11,000 --> 00:11:13,000
Er na fyddwn yn ymdrin â nhw yma, mae yna eraill, yn fwy cymhleth,

217
00:11:13,000 --> 00:11:16,000
strwythurau data sy'n gwneud yn siŵr nad yw hyn yn digwydd.

218
00:11:16,000 --> 00:11:18,000
Fodd bynnag, un peth syml y gellir ei wneud i osgoi hyn yw

219
00:11:18,000 --> 00:11:21,000
i ychydig ar hap siffrwd y gwerthoedd mewnbwn.

220
00:11:21,000 --> 00:11:26,000
Mae'n annhebygol iawn y trwy hap a damwain ar hap rhestr cymysgu o rifau yn cael ei datrys.

221
00:11:26,000 --> 00:11:29,000
Os yw hyn yn wir, ni fyddai casinos yn aros mewn busnes yn hir.

222
00:11:29,000 --> 00:11:31,000
>> Dyna ni.

223
00:11:31,000 --> 00:11:34,000
Rydych nawr yn gwybod am chwilio deuaidd a choed chwiliad deuaidd.

224
00:11:34,000 --> 00:11:36,000
Rwy'n Patrick Schmid, ac mae hyn yn CS50.

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

226
00:11:38,000 --> 00:11:43,000
Un ffordd amlwg fyddai i sganio y rhestr o ... [Canu]

227
00:11:43,000 --> 00:11:46,000
... Nifer yr eitemau ... yep

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

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

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