1
00:00:00,000 --> 00:00:02,770
[Powered by Google Translate] [Kafli 7: öruggari]

2
00:00:02,770 --> 00:00:05,090
[Rob Bowden] [Harvard University]

3
00:00:05,090 --> 00:00:07,930
[Þetta er CS50] [CS50.TV]

4
00:00:07,930 --> 00:00:10,110
Allt í lagi. Svo eins og ég sagði í bréfinu mínu,

5
00:00:10,110 --> 00:00:14,060
þetta er að fara að vera tvöfaldur-tré-ákafur kafla.

6
00:00:14,060 --> 00:00:16,820
En það eru ekki svo margar spurningar.

7
00:00:16,820 --> 00:00:18,920
Þannig að við erum að fara að reyna að draga út hverja spurningu

8
00:00:18,920 --> 00:00:25,430
og fara í sársaukafullar smáatriðum allra bestu leiðir til að gera hlutina.

9
00:00:25,430 --> 00:00:31,200
Svo rétt í byrjun, fara við í gegnum teikningar sýni af tvöfaldur tré og efni.

10
00:00:31,200 --> 00:00:35,970
Svo hér, "Mundu að tvöfaldur tré er hnúður svipuð í tengda listanum,

11
00:00:35,970 --> 00:00:38,150
nema í stað þess að einn músina eru tveir: einn fyrir "barnið" vinstri

12
00:00:38,150 --> 00:00:41,950
og einn fyrir hægri barnsins. "

13
00:00:41,950 --> 00:00:45,630
Svo tvöfaldur tré er bara eins og tengda lista,

14
00:00:45,630 --> 00:00:47,910
nema strúktúrinn er að fara að hafa tvo punkta.

15
00:00:47,910 --> 00:00:51,390
Það er trinary tré, sem eru að fara að hafa þrjá punkta,

16
00:00:51,390 --> 00:00:56,540
eru N-áhrærir tré, sem bara hafa almenna músina

17
00:00:56,540 --> 00:01:00,320
sem þú hefur þá til malloc að vera nógu stórt til að hafa

18
00:01:00,320 --> 00:01:04,840
nóg ábendingum til allar mögulegar börn.

19
00:01:04,840 --> 00:01:08,200
Svo gerist tvöfaldur tré bara að hafa góða tala af tveimur.

20
00:01:08,200 --> 00:01:11,260
Ef þú vilt, getur þú gefa tengda listanum sem unary tré,

21
00:01:11,260 --> 00:01:15,360
en ég held ekki að einhver kallar það að.

22
00:01:15,360 --> 00:01:18,060
"Teiknaðu kassa-og-Örvar skýringarmynd af tvíundartrés hnút

23
00:01:18,060 --> 00:01:24,110
inniheldur uppáhalds númer nate er, 7, þar sem hvert barn bendillinn er null. "

24
00:01:24,110 --> 00:01:27,780
Svo iPad ham.

25
00:01:27,780 --> 00:01:30,280
>> Það er að fara að vera nokkuð einfalt.

26
00:01:30,280 --> 00:01:36,150
Við erum bara að fara að hafa hnút, ég teikna það sem ferningur.

27
00:01:36,150 --> 00:01:38,730
Og ég ætla að draga gildi hér.

28
00:01:38,730 --> 00:01:41,090
Þannig gildi mun fara í hér,

29
00:01:41,090 --> 00:01:44,770
og þá niður hér við munum hafa vinstri bendilinn til vinstri og hægri bendilinn til hægri.

30
00:01:44,770 --> 00:01:50,430
Og það er mjög mikið svo venju að kalla það vinstri og hægri, bendillinn nöfn.

31
00:01:50,430 --> 00:01:52,460
Báðir þessir eru að fara að vera null.

32
00:01:52,460 --> 00:01:57,870
Það verður bara að vera núll, og það verður bara að vera núll.

33
00:01:57,870 --> 00:02:03,630
Allt í lagi. Svo aftur hingað.

34
00:02:03,630 --> 00:02:05,700
"Með tengist lista, við höfðum aðeins að geyma músina

35
00:02:05,700 --> 00:02:09,639
að fyrsta hnút í skránni til að muna allt sem tengist lista, eða alla lista.

36
00:02:09,639 --> 00:02:11,650
Sömuleiðis með tré, höfum við bara að geyma músina

37
00:02:11,650 --> 00:02:13,420
á einum hnút til að muna allt tréð.

38
00:02:13,420 --> 00:02:15,980
Þetta hnútur er Calle á 'rót' í tré.

39
00:02:15,980 --> 00:02:18,320
Byggja á myndinni þinni úr áður eða draga nýjan

40
00:02:18,320 --> 00:02:21,690
þannig að þú ert með kassa-og-Örvar lýsing af a tvöfaldur tré

41
00:02:21,690 --> 00:02:25,730
með gildið 7, en 3 í vinstri,

42
00:02:25,730 --> 00:02:32,760
þá 9 til hægri, og svo 6 til hægri af 3. "

43
00:02:32,760 --> 00:02:34,810
Við skulum sjá hvort ég man allt sem í höfðinu á mér.

44
00:02:34,810 --> 00:02:37,670
Þannig að þetta er að fara að vera rót okkar upp hér.

45
00:02:37,670 --> 00:02:41,600
Við munum hafa sumir músina einhversstaðar, eitthvað sem við munum kalla rót,

46
00:02:41,600 --> 00:02:45,140
og það er að benda að þetta strákur.

47
00:02:45,140 --> 00:02:48,490
Nú til að gera nýjan hnút,

48
00:02:48,490 --> 00:02:52,870
Hvað höfum við, 3 til vinstri?

49
00:02:52,870 --> 00:02:57,140
Svo nýtt hnút með 3, og það bendir fyrst null.

50
00:02:57,140 --> 00:02:59,190
Ég ætla bara að setja N.

51
00:02:59,190 --> 00:03:02,250
Nú viljum við gera að fara til vinstri á 7.

52
00:03:02,250 --> 00:03:06,840
Þannig að við að breyta þessu bendi til nú benda á þennan gaur.

53
00:03:06,840 --> 00:03:12,420
Og við gerum það sama. Við viljum 9 hérna

54
00:03:12,420 --> 00:03:14,620
sem upphaflega bara segir null.

55
00:03:14,620 --> 00:03:19,600
Við erum að fara að breyta þessu músina, benda til 9,

56
00:03:19,600 --> 00:03:23,310
og nú viljum við að setja 6 til hægri af 3.

57
00:03:23,310 --> 00:03:32,170
Svo það er að fara til - gera 6.

58
00:03:32,170 --> 00:03:34,310
Og þessi strákur mun benda þar.

59
00:03:34,310 --> 00:03:38,320
Allt í lagi. Svo það er allt það biður okkur um að gera.

60
00:03:38,320 --> 00:03:42,770
>> Nú skulum fara yfir nokkur hugtök.

61
00:03:42,770 --> 00:03:46,690
Við töluðum nú þegar um hversu rót trésins er efst mest hnút í trénu.

62
00:03:46,690 --> 00:03:54,720
Sá sem inniheldur 7. Hnúður á the botn af trénu kallast blöðin.

63
00:03:54,720 --> 00:04:01,240
Sérhver hnútur sem bara hefur null eins og börn hans eru a leaf.

64
00:04:01,240 --> 00:04:03,680
Svo það er hægt, ef tvíundartré okkar er bara einn hnút,

65
00:04:03,680 --> 00:04:10,130
að tré er lauf, og það er það.

66
00:04:10,130 --> 00:04:12,060
"The 'hæð' í tré er fjöldi hops sem þú þarft að gera

67
00:04:12,060 --> 00:04:16,620
að fá frá the toppur til blaða. "

68
00:04:16,620 --> 00:04:18,640
Við munum fá inn í annað, munurinn

69
00:04:18,640 --> 00:04:21,940
milli jafnvægi og ójafnvægi tvöfaldur tré,

70
00:04:21,940 --> 00:04:29,470
en nú er heildar hæð þessu tré

71
00:04:29,470 --> 00:04:34,520
Ég myndi segja 3, en ef þú telur fjölda hops

72
00:04:34,520 --> 00:04:39,710
þú þarft að gera til að fá að 9, þá er það í raun aðeins í hæð 2.

73
00:04:39,710 --> 00:04:43,340
Núna er þetta ójafnvægi tvöfaldur tré,

74
00:04:43,340 --> 00:04:49,840
en við munum tala um jafnvægi þegar það fær að vera viðeigandi.

75
00:04:49,840 --> 00:04:52,040
Svo nú að við getum talað um hnúta í tré í skilmálum

76
00:04:52,040 --> 00:04:54,700
miðað til annarra hnúta í trénu.

77
00:04:54,700 --> 00:04:59,730
Svo nú höfum við foreldrar, börn, systkini, feður, og niðjar.

78
00:04:59,730 --> 00:05:05,650
Þeir eru ansi skynsemi, hvað þeir meina.

79
00:05:05,650 --> 00:05:09,610
Ef við spyrjum - foreldra þess.

80
00:05:09,610 --> 00:05:12,830
Svo er það foreldri 3?

81
00:05:12,830 --> 00:05:16,090
[Nemendur] 7. >> Já. Foreldri er bara að fara að vera það sem bendir til þín.

82
00:05:16,090 --> 00:05:20,510
Þá það eru börn 7?

83
00:05:20,510 --> 00:05:23,860
[Nemendur] 3 og 9. >> Já.

84
00:05:23,860 --> 00:05:26,460
Takið eftir að "börn" bókstaflega þýðir börn,

85
00:05:26,460 --> 00:05:31,010
svo 6 myndi ekki gilda, því það er eins og barnabarnið.

86
00:05:31,010 --> 00:05:35,540
En ef við förum afkomendur, svo það eru afkomendur 7?

87
00:05:35,540 --> 00:05:37,500
[Nemendur] 3, 6 og 9. >> Já.

88
00:05:37,500 --> 00:05:42,330
Synir rót hnút er að fara að vera allt í trénu,

89
00:05:42,330 --> 00:05:47,950
nema kannski rót hnút sjálft, ef þú vilt ekki að íhuga að afkomandi.

90
00:05:47,950 --> 00:05:50,750
Og að lokum, feður, svo það er hið gagnstæða átt.

91
00:05:50,750 --> 00:05:55,740
Svo það eru forfeður 6?

92
00:05:55,740 --> 00:05:58,920
[Nemendur] 3 og 7. >> Já. 9 er ekki innifalinn.

93
00:05:58,920 --> 00:06:02,520
Það er bara bein ætterni baka í rót

94
00:06:02,520 --> 00:06:13,230
er að fara að vera feður yðar.

95
00:06:13,230 --> 00:06:16,300
>> "Við segjum að tvöfaldur tré er" skipað "ef fyrir hvern hnút í tré,

96
00:06:16,300 --> 00:06:19,530
öllum niðjum sínum á vinstri hafa minna gildi

97
00:06:19,530 --> 00:06:22,890
og öll þau á hægri hafa meiri gildi.

98
00:06:22,890 --> 00:06:27,060
Til dæmis, er tré ofan pantað en það er ekki aðeins mögulegt pantað fyrirkomulag. "

99
00:06:27,060 --> 00:06:30,180
Áður en við komum að því,

100
00:06:30,180 --> 00:06:36,420
að panta tvöfaldur tré er einnig þekktur eins og a tvöfaldur leita tré.

101
00:06:36,420 --> 00:06:38,660
Hér verður að vera að kalla það pantaði tvöfaldur tré,

102
00:06:38,660 --> 00:06:41,850
en ég hef aldrei heyrt það kallað að panta tvöfaldur tré áður,

103
00:06:41,850 --> 00:06:46,650
og á spurningakeppni við erum miklu líklegri til að setja tvöfaldur leita tré.

104
00:06:46,650 --> 00:06:49,250
Þeir eru eitt og hið sama,

105
00:06:49,250 --> 00:06:54,580
og það er mikilvægt að þú þekkja greinarmun á tré tvöfaldur og tvöfaldur leita tré.

106
00:06:54,580 --> 00:06:58,830
A tvöfaldur tré er bara tré, sem bendir til tvennt.

107
00:06:58,830 --> 00:07:02,120
Hver hnútur bendir til tvennt.

108
00:07:02,120 --> 00:07:06,310
Það er engin rök um gildi sem það bendir á.

109
00:07:06,310 --> 00:07:11,370
Svo eins og hérna, þar sem það er tvöfaldur leita tré,

110
00:07:11,370 --> 00:07:14,030
við vitum að ef við förum eftir af 7,

111
00:07:14,030 --> 00:07:16,670
þá allt af þeim gildum sem við getum hugsanlega náð

112
00:07:16,670 --> 00:07:19,310
með því að fara til vinstri á 7 að vera minna en 7.

113
00:07:19,310 --> 00:07:24,070
Takið eftir að öll gildi minna en 7 eru 3 og 6.

114
00:07:24,070 --> 00:07:26,040
Þeir eru allir til vinstri á 7.

115
00:07:26,040 --> 00:07:29,020
Ef við förum til hægri 7, allt þarf að vera meira en 7,

116
00:07:29,020 --> 00:07:33,220
svo er 9 til hægri 7, svo við erum góð.

117
00:07:33,220 --> 00:07:36,150
Þetta er ekki málið fyrir tvíundartrés,

118
00:07:36,150 --> 00:07:40,020
fyrir venjulega tvöfaldur tré við getum bara 3 efst, 7 til vinstri,

119
00:07:40,020 --> 00:07:47,630
9 til vinstri 7, það er engin röðun gildi neinu tagi.

120
00:07:47,630 --> 00:07:56,140
Nú ætlum við í raun ekki að gera þetta því það er leiðinlegur og óþarfa,

121
00:07:56,140 --> 00:07:59,400
en "reyna að draga eins marga panta tré sem hægt er að hugsa um

122
00:07:59,400 --> 00:08:01,900
nota númer 7, 3, 9 og 6.

123
00:08:01,900 --> 00:08:06,800
Hversu margar mismunandi fyrirkomulag er þarna? Hver er hæð hvers og eins? "

124
00:08:06,800 --> 00:08:10,480
>> Við munum gera nokkrar, en helsta hugmynd er,

125
00:08:10,480 --> 00:08:16,530
þetta er á engan hátt einstök framsetning tvíundartrés inniheldur þessi gildi.

126
00:08:16,530 --> 00:08:22,760
Allt sem við þurfum er einhver tvöfaldur tré, sem inniheldur 7, 3, 6, og 9.

127
00:08:22,760 --> 00:08:25,960
Önnur möguleg gildi einn væri rót er 3,

128
00:08:25,960 --> 00:08:30,260
fara til vinstri og það er 6, fara til vinstri og það er 7,

129
00:08:30,260 --> 00:08:32,730
fara til vinstri og það er 9.

130
00:08:32,730 --> 00:08:36,169
Það er fullkomlega gild tvöfaldur leita tré.

131
00:08:36,169 --> 00:08:39,570
Það er ekki mjög gagnlegt, vegna þess að það er bara eins og tengda lista

132
00:08:39,570 --> 00:08:43,750
og allar þessar ábendingar eru bara null.

133
00:08:43,750 --> 00:08:48,900
En það er gild tré. Já?

134
00:08:48,900 --> 00:08:51,310
[Nemandi] Ekki gildin verða að vera meiri á hægri?

135
00:08:51,310 --> 00:08:56,700
Eða er þetta -? >> Þetta sem ég ætlaði að fara í hina áttina.

136
00:08:56,700 --> 00:09:00,960
Það er líka - já, við skulum skipta því.

137
00:09:00,960 --> 00:09:07,770
9, 7, 6, 3. Góður fengur.

138
00:09:07,770 --> 00:09:11,730
Það hefur samt að hlýða hvað tré tvöfaldur leit er að gera.

139
00:09:11,730 --> 00:09:15,650
Svo allt til vinstri verður að vera minna en hverjum hnút.

140
00:09:15,650 --> 00:09:23,180
Við gætum bara fara, segja, þetta 6 og setja það hér.

141
00:09:23,180 --> 00:09:26,880
Nei, við getum það ekki. Hvers vegna að halda ég að gera það?

142
00:09:26,880 --> 00:09:35,350
Við skulum gera - hér er 6 Hér er 7, 6 stig 3.

143
00:09:35,350 --> 00:09:39,290
Þetta er enn í gildi tvöfaldur leita tré.

144
00:09:39,290 --> 00:09:49,260
Hvað er rangt ef ég - við skulum sjá hvort ég get komið upp með samkomulagi.

145
00:09:49,260 --> 00:09:52,280
Já, allt í lagi. Svo hvað er rangt við þetta tré?

146
00:09:52,280 --> 00:10:08,920
Ég held að ég hef nú þegar gefið þér vísbendingu um að það sé eitthvað athugavert við það.

147
00:10:08,920 --> 00:10:14,430
Hvers vegna að halda ég að gera það?

148
00:10:14,430 --> 00:10:18,510
Allt í lagi. Þetta lítur sanngjarnt.

149
00:10:18,510 --> 00:10:22,590
Ef við horfum á hvern hnút, eins og 7, síðan til vinstri á 7 er a 3.

150
00:10:22,590 --> 00:10:24,960
Svo við höfum 3, hlutur til hægri 3 er 6.

151
00:10:24,960 --> 00:10:27,750
Og ef þú horfir á 6, hlutur til hægri 6 er 9.

152
00:10:27,750 --> 00:10:30,910
Svo hvers vegna er þetta ekki gild tvöfaldur leita tré?

153
00:10:30,910 --> 00:10:36,330
[Nemendur] 9 er enn til vinstri á 7. >> Já.

154
00:10:36,330 --> 00:10:43,710
Það verður að vera satt að öll gildi sem þú getur hugsanlega ná því að fara til vinstri á 7 er minna en 7.

155
00:10:43,710 --> 00:10:49,120
Ef við förum eftir af 7, fáum við til 3 og við getum enn fengið til 6,

156
00:10:49,120 --> 00:10:52,520
getum við samt fá að 9, en eftir að hafa farið minna en 7,

157
00:10:52,520 --> 00:10:55,070
við ættum ekki að vera fær um að fá að tala sem er stærri en 7.

158
00:10:55,070 --> 00:10:59,830
Svo er þetta ekki gild tvöfaldur leita tré.

159
00:10:59,830 --> 00:11:02,330
>> Bróðir minn var reyndar viðtal spurningu

160
00:11:02,330 --> 00:11:07,760
það var í rauninni þetta, bara númerið upp eitthvað til að sannreyna

161
00:11:07,760 --> 00:11:10,500
hvort tréð er tvöfaldur leita tré,

162
00:11:10,500 --> 00:11:13,580
og svo það fyrsta sem hann gerði var bara að athuga

163
00:11:13,580 --> 00:11:17,020
ef vinstri og hægri séu réttar, og þá iterate niður.

164
00:11:17,020 --> 00:11:19,700
En þú getur ekki bara að gera það, þú þarft að fylgjast með

165
00:11:19,700 --> 00:11:22,550
af því að nú þegar ég hef farið til vinstri 7,

166
00:11:22,550 --> 00:11:26,340
allt í þessu subtree verður að vera minna en 7.

167
00:11:26,340 --> 00:11:28,430
Rétt reiknirit þarf að halda utan

168
00:11:28,430 --> 00:11:35,970
af mörk sem gildi geta hugsanlega falla inn

169
00:11:35,970 --> 00:11:38,360
Við munum ekki fara í gegnum þá alla.

170
00:11:38,360 --> 00:11:41,630
Það er a ágætur endurkomu tengslum,

171
00:11:41,630 --> 00:11:44,810
þó að við höfum ekki fengið að þeim, eða við munum ekki komast að þeim,

172
00:11:44,810 --> 00:11:47,030
skilgreina hversu margir í raun eru.

173
00:11:47,030 --> 00:11:53,180
Þannig að það eru 14 af þeim.

174
00:11:53,180 --> 00:11:56,020
Hugmyndin um hvernig þú vilt gera það er stærðfræðilega eins,

175
00:11:56,020 --> 00:11:59,770
þú getur valið hvaða einn einn að vera rót hnút,

176
00:11:59,770 --> 00:12:03,160
og svo ef ég velja 7 að rót hnút,

177
00:12:03,160 --> 00:12:08,150
þá eru, segja, nokkrar tölur sem hægt er að fara að vera vinstri hnútur minn,

178
00:12:08,150 --> 00:12:10,440
og það eru nokkrar tölur sem hægt er að réttur hnútur minn,

179
00:12:10,440 --> 00:12:15,090
en ef ég hef n heildarfjölda, þá upphæð sem hægt er að fara til vinstri

180
00:12:15,090 --> 00:12:18,820
plús upphæð sem getur farið til hægri er n - 1.

181
00:12:18,820 --> 00:12:26,130
Svo á eftir eru tölur, þeir verða að vera fær um að fara annað hvort til vinstri eða hægri.

182
00:12:26,130 --> 00:12:31,580
Það virðist erfitt að ef ég setti 3 fyrsta þá allt að fara til vinstri,

183
00:12:31,580 --> 00:12:35,080
en ef ég setti 7, þá er nokkur atriði sem hægt fara í vinstri og sumt getur farið til hægri.

184
00:12:35,080 --> 00:12:39,570
Og '3 fyrst ég ætlaði allt getur farið til hægri.

185
00:12:39,570 --> 00:12:42,350
Það er í raun, hefur þú bara að hugsa um það eins og,

186
00:12:42,350 --> 00:12:47,980
hversu margt getur farið á næsta stig af trénu.

187
00:12:47,980 --> 00:12:50,420
Og það kemur út að vera 14, eða þú getur teiknað þau öll,

188
00:12:50,420 --> 00:12:54,650
og þá munt þú fá 14.

189
00:12:54,650 --> 00:13:01,120
>> Fara aftur hingað,

190
00:13:01,120 --> 00:13:03,510
"Skipað tvöfaldur tré er flott vegna þess að við getum leitað í þeim

191
00:13:03,510 --> 00:13:06,910
á mjög svipaðan hátt og leita yfir raðað fylki.

192
00:13:06,910 --> 00:13:10,120
Til að gera það, byrjum við á rót og vinna okkur niður tré

193
00:13:10,120 --> 00:13:13,440
að leyfi, stöðva gildi hver hnútur gegn gildi sem við erum að leita að.

194
00:13:13,440 --> 00:13:15,810
Ef gildi núverandi Hnútur er minna en gildið sem við erum að leita að,

195
00:13:15,810 --> 00:13:18,050
þú ferð næst til hægri barn hnúturinn er.

196
00:13:18,050 --> 00:13:20,030
Annars, þú ferð vinstra barn hnúturinn er.

197
00:13:20,030 --> 00:13:22,800
Á einhverjum tímapunkti munt þú annaðhvort að finna gildi sem þú ert að leita að, eða þú munt hlaupa inn í núll,

198
00:13:22,800 --> 00:13:28,520
gefur til kynna að gildi er ekki í tré. "

199
00:13:28,520 --> 00:13:32,450
Ég þarf að gera annað uppkast the tré sem við höfðum áður, sem mun taka annað.

200
00:13:32,450 --> 00:13:38,280
En við viljum að líta upp hvort 6, 10, og 1 er í trénu.

201
00:13:38,280 --> 00:13:49,180
Og hvað það var, 7, 9, 3, 6. Allt í lagi.

202
00:13:49,180 --> 00:13:52,730
Tölurnar sem þú vilt að líta upp, viljum við horfa upp 6.

203
00:13:52,730 --> 00:13:55,440
Hvernig er þetta reiknirit vinna?

204
00:13:55,440 --> 00:14:03,040
Jæja, höfum við einnig nokkur rót músina til tré okkar.

205
00:14:03,040 --> 00:14:12,460
Og við myndum fara að rót og segja, er þetta gildi jafnt gildi við erum að leita að?

206
00:14:12,460 --> 00:14:15,000
Þannig að við erum að leita að 6, þannig að það er ekki jafn.

207
00:14:15,000 --> 00:14:20,140
Þannig höldum við áfram, og nú segjum við, allt í lagi, svo er 6 minna en 7.

208
00:14:20,140 --> 00:14:23,940
Er það að við viljum fara til vinstri, eða viljum við fara til hægri?

209
00:14:23,940 --> 00:14:27,340
[Nemandi] Vinstri. >> Já.

210
00:14:27,340 --> 00:14:33,340
Það er verulega auðveldara, allt sem þú þarft að gera er að draga eina mögulega hnút í tré

211
00:14:33,340 --> 00:14:37,760
og þá áttina - í stað þess að reyna að hugsa í hausnum,

212
00:14:37,760 --> 00:14:40,020
allt í lagi, ef það er minna, get ég farið til vinstri eða fara rétt,

213
00:14:40,020 --> 00:14:43,030
bara að horfa á þessa mynd, það er mjög ljóst að ég þarf að fara til vinstri

214
00:14:43,030 --> 00:14:47,700
ef hnútur er meiri en gildi sem ég er að leita að.

215
00:14:47,700 --> 00:14:52,600
Svo þú ferð til vinstri, núna er ég á 3.

216
00:14:52,600 --> 00:14:57,770
Ég vil - 3 er minna en gildið sem ég er að leita að, sem er 6.

217
00:14:57,770 --> 00:15:03,420
Svo förum við til hægri, og nú er ég á endanum á 6,

218
00:15:03,420 --> 00:15:07,380
sem er gildi sem ég er að leita að, svo ég aftur satt.

219
00:15:07,380 --> 00:15:15,760
Næsta virði ég ætla að leita að er 10.

220
00:15:15,760 --> 00:15:23,230
Allt í lagi. Svo 10, nú er að fara að - skera burt það - fara að fylgja rót.

221
00:15:23,230 --> 00:15:27,670
Nú, 10 er að fara að vera meira en 7, svo ég vil að líta til hægri.

222
00:15:27,670 --> 00:15:31,660
Ég ætla að koma hérna, 10 er að fara að vera meiri en 9,

223
00:15:31,660 --> 00:15:34,520
þannig að ég ætla að fara til að vilja líta til hægri.

224
00:15:34,520 --> 00:15:42,100
Ég kem hérna, en hérna er ég í null.

225
00:15:42,100 --> 00:15:44,170
Hvað á ég að gera ef ég högg null?

226
00:15:44,170 --> 00:15:47,440
[Nemandi] return false? >> Já. Ég vissi ekki að finna 10.

227
00:15:47,440 --> 00:15:49,800
1 er að fara til vera a nánast eins mál,

228
00:15:49,800 --> 00:15:51,950
nema það er bara að fara að vera hreifi, í stað þess að leita

229
00:15:51,950 --> 00:15:56,540
niður hægra megin, ég er að fara að horfa niður á vinstri hlið.

230
00:15:56,540 --> 00:16:00,430
>> Nú ég held að við í raun fá að kóða.

231
00:16:00,430 --> 00:16:04,070
Hér er þar - opna CS50 tæki og sigla leið þína þar,

232
00:16:04,070 --> 00:16:07,010
en þú getur líka bara gert það í rúm.

233
00:16:07,010 --> 00:16:09,170
Það er líklega tilvalið að gera það í bili,

234
00:16:09,170 --> 00:16:13,760
vegna þess að við getum unnið í rúm.

235
00:16:13,760 --> 00:16:19,170
"Fyrst við þurfum nýja tegund skilgreiningu fyrir tvíundartrés hnút innihalda int gildi.

236
00:16:19,170 --> 00:16:21,400
Notkun boilerplate typedef neðan,

237
00:16:21,400 --> 00:16:24,510
búa til nýja tegund skilgreiningu fyrir hnút í tvíundartrés.

238
00:16:24,510 --> 00:16:27,930
Ef þú færð fastur. . . "Bla, bla, bla. Lagi.

239
00:16:27,930 --> 00:16:30,380
Svo skulum setja boilerplate hér,

240
00:16:30,380 --> 00:16:41,630
typedef struct hnút, og hnút. Já, allt í lagi.

241
00:16:41,630 --> 00:16:44,270
Svo það eru reitir sem við erum að fara að vilja í hnút okkar?

242
00:16:44,270 --> 00:16:46,520
[Nemandi] Int og þá tvo ábendingum?

243
00:16:46,520 --> 00:16:49,700
>> Int gildi, tveir ábendingum? Hvernig skrifa ég punkta?

244
00:16:49,700 --> 00:16:58,440
[Nemandi] strúktúr. >> Ég ætti að súmma inn Já, svo strúktúr hnút * vinstri,

245
00:16:58,440 --> 00:17:01,320
og strúktúr hnút * rétt.

246
00:17:01,320 --> 00:17:03,460
Og muna umræðu frá síðasta tíma,

247
00:17:03,460 --> 00:17:15,290
að þetta gerir ekkert vit, það gerir ekkert vit,

248
00:17:15,290 --> 00:17:18,270
þetta gerir ekkert vit.

249
00:17:18,270 --> 00:17:25,000
Þú þarft allt það til að skilgreina þetta endurkvæma strúktúr.

250
00:17:25,000 --> 00:17:27,970
Jæja, svo það er það tré okkar er að fara að líta út.

251
00:17:27,970 --> 00:17:37,670
Ef við fengum trinary tré, þá hnúturinn getur litið út B1, B2, strúktúrinn hnút * B3,

252
00:17:37,670 --> 00:17:43,470
þar sem B er útibú - í raun, ég hef meira heyrt það vinstri, miðja, hægri, en hvað.

253
00:17:43,470 --> 00:17:55,610
Við umönnun aðeins um tvöfaldur, svo til hægri, vinstri.

254
00:17:55,610 --> 00:17:59,110
"Nú lýsa alþjóðlegt hnút * breytu fyrir rót af trénu."

255
00:17:59,110 --> 00:18:01,510
Þannig að við erum ekki að fara að gera það.

256
00:18:01,510 --> 00:18:08,950
Til að gera hlutina aðeins erfiðari og fleiri almenn,

257
00:18:08,950 --> 00:18:11,570
við munum ekki hafa alþjóðlegt hnút breytu.

258
00:18:11,570 --> 00:18:16,710
Þess í stað í helstu munum lýsa öllum okkar hnút hluti,

259
00:18:16,710 --> 00:18:20,500
og það þýðir að neðan, þegar við byrjum að keyra

260
00:18:20,500 --> 00:18:23,130
Inniheldur virka okkar og setja virka okkar,

261
00:18:23,130 --> 00:18:27,410
í stað þess að finna okkar virka bara að nota þessa alþjóðlegu hnút breytu,

262
00:18:27,410 --> 00:18:34,280
við erum að fara að hafa það að taka sem rök trénu, sem við viljum það til að vinna.

263
00:18:34,280 --> 00:18:36,650
Having alþjóðlegt breytu átti að gera hlutina auðveldari.

264
00:18:36,650 --> 00:18:42,310
Við ætlum að gera hlutina erfiðari.

265
00:18:42,310 --> 00:18:51,210
Nú taka eina mínútu eða svo bara að gera þetta svoleiðis,

266
00:18:51,210 --> 00:18:57,690
þar inni á helstu sem þú vilt búa til þetta tré, og það er allt sem þú vilt gera.

267
00:18:57,690 --> 00:19:04,530
Prófaðu og reisa þetta tré í helstu virka.

268
00:19:42,760 --> 00:19:47,610
>> Allt í lagi. Svo þú þarft ekki einu sinni að hafa reist tré alla leið enn.

269
00:19:47,610 --> 00:19:49,840
En einhver hefur eitthvað sem ég gæti draga upp

270
00:19:49,840 --> 00:20:03,130
til að sýna hvernig maður gæti byrjað að byggja slíkt tré?

271
00:20:03,130 --> 00:20:08,080
[Nemandi] Einhver er að lemja, að reyna að komast út.

272
00:20:08,080 --> 00:20:13,100
[Bowden] Hver ánægð með byggingu tré þeirra?

273
00:20:13,100 --> 00:20:15,520
[Nemandi] Jú. Það er ekki gert. >> Það er allt í lagi. Við getum bara að klára -

274
00:20:15,520 --> 00:20:26,860
ó, þú getur vistað það? Húrra.

275
00:20:26,860 --> 00:20:32,020
Svo hér höfum við - ó, ég skera örlítið af.

276
00:20:32,020 --> 00:20:34,770
Er ég aðdregna í?

277
00:20:34,770 --> 00:20:37,730
Þysja inn, fletta út. >> Ég er með spurningu. >> Já?

278
00:20:37,730 --> 00:20:44,410
[Nemandi] Þegar þú skilgreinir struct, eru hlutir eins og frumstilla við neitt?

279
00:20:44,410 --> 00:20:47,160
[Bowden] Nei >> lagi. Svo þú þyrftir að frumstilla -

280
00:20:47,160 --> 00:20:50,450
[Bowden] Nei Þegar þú skilgreinir, eða þegar þú lýsa strúktúr,

281
00:20:50,450 --> 00:20:55,600
það er ekki frumstilla við vanræksla, það er bara eins og ef þú lýsa heiltala.

282
00:20:55,600 --> 00:20:59,020
Það er nákvæmlega það sama. Það er eins og hvert einstökum sviðum hennar

283
00:20:59,020 --> 00:21:04,460
geta haft sorp gildi í það. >> Og það er hægt að skilgreina - eða að lýsa yfir strúktúr

284
00:21:04,460 --> 00:21:07,740
á þann hátt að það er frumstilla þá?

285
00:21:07,740 --> 00:21:13,200
[Bowden] Já. Svo, smákaka frumstilling setningafræði

286
00:21:13,200 --> 00:21:18,660
er að fara að líta út eins og -

287
00:21:18,660 --> 00:21:22,200
Það er tvær leiðir sem við getum gert þetta. Ég held að við ættum að þýða það

288
00:21:22,200 --> 00:21:25,840
til að tryggja Clang einnig gerir þetta.

289
00:21:25,840 --> 00:21:28,510
Röð rök sem koma í strúktúr,

290
00:21:28,510 --> 00:21:32,170
þú setur sem röð rök innan þessara hrokkið axlabönd.

291
00:21:32,170 --> 00:21:35,690
Svo ef þú vilt að frumstilla hana 9 og fór að null og þá rétt að vera núll,

292
00:21:35,690 --> 00:21:41,570
það væri 9, null, null.

293
00:21:41,570 --> 00:21:47,890
Hinn kosturinn er, og ritstjóri er ekki eins og þetta setningafræði,

294
00:21:47,890 --> 00:21:50,300
og það telur Ég vil nýja blokk,

295
00:21:50,300 --> 00:22:01,800
en hinn kosturinn er eitthvað eins og -

296
00:22:01,800 --> 00:22:04,190
hér, ég setti hana á nýja línu.

297
00:22:04,190 --> 00:22:09,140
Þú getur skýrt sagt, gleyma ég nákvæmlega setningafræði.

298
00:22:09,140 --> 00:22:13,110
Svo þú getur sérstaklega takast á við þær með nafni og segi,

299
00:22:13,110 --> 00:22:21,570
. C, eða. Gildi = 9,. Vinstri = NULL.

300
00:22:21,570 --> 00:22:24,540
Ég giska á þessi þörf til vera kommum.

301
00:22:24,540 --> 00:22:29,110
. Rétt = NULL, þannig að þetta vegur þú ert ekki

302
00:22:29,110 --> 00:22:33,780
raunverulega þörf til vita röð struct,

303
00:22:33,780 --> 00:22:36,650
og þegar þú ert að lesa þetta, það er miklu skýrari

304
00:22:36,650 --> 00:22:41,920
um hvaða gildi er verið að frumstilla til.

305
00:22:41,920 --> 00:22:44,080
>> Þetta gerist að vera einn af þeim hlutum sem -

306
00:22:44,080 --> 00:22:49,100
svo, að mestu leyti, C + + er superset C.

307
00:22:49,100 --> 00:22:54,160
Hægt er að taka C kóða, færa það yfir í C ​​+ +, og það ætti að safna saman.

308
00:22:54,160 --> 00:22:59,570
Þetta er eitt af því sem C + + styður ekki, svo að fólk hættir ekki að gera það.

309
00:22:59,570 --> 00:23:01,850
Ég veit ekki hvort það er eina ástæðan að fólk hafa tilhneigingu til að gera það,

310
00:23:01,850 --> 00:23:10,540
en raunin þar sem ég þurfti að nota það þarf að vinna með C + + og svo ég gæti ekki notað þetta.

311
00:23:10,540 --> 00:23:14,000
Annað dæmi um eitthvað sem er ekki að vinna með C + + er

312
00:23:14,000 --> 00:23:16,940
hvernig malloc skilar "void *," tæknilega,

313
00:23:16,940 --> 00:23:20,200
en þú getur bara segja char * x = malloc hvað,

314
00:23:20,200 --> 00:23:22,840
og það verður sjálfkrafa varpað á char *.

315
00:23:22,840 --> 00:23:25,450
Að sjálfvirk kastað gerist ekki í C + +.

316
00:23:25,450 --> 00:23:28,150
Það myndi ekki þýða, og þú vildi sérstaklega þarf að segja

317
00:23:28,150 --> 00:23:34,510
char *, malloc, hvað, að greiða það til a char *.

318
00:23:34,510 --> 00:23:37,270
Það eru ekki margir hlutir sem C og C + + ósammála um,

319
00:23:37,270 --> 00:23:40,620
en þeir eru tveir.

320
00:23:40,620 --> 00:23:43,120
Svo munum við fara með þessum setningafræði.

321
00:23:43,120 --> 00:23:46,150
En jafnvel þótt við vildum ekki fara með þeim setningafræði,

322
00:23:46,150 --> 00:23:49,470
hvað er - gæti verið athugavert við þetta?

323
00:23:49,470 --> 00:23:52,170
[Nemandi] Ég þarf ekki að dereference það? >> Já.

324
00:23:52,170 --> 00:23:55,110
Mundu að örin hafi óbeina dereference,

325
00:23:55,110 --> 00:23:58,230
og svo þegar við erum bara að takast á við a struct,

326
00:23:58,230 --> 00:24:04,300
við viljum nota. að fá á sviði inni í strúktúr.

327
00:24:04,300 --> 00:24:07,200
Og eina skiptið sem við notum ör er þegar við viljum gera -

328
00:24:07,200 --> 00:24:13,450
Jæja, ör jafngildir -

329
00:24:13,450 --> 00:24:17,020
það er það sem það hefði átt ef ég nota ör.

330
00:24:17,020 --> 00:24:24,600
Allt ör þýðir er, dereference þetta, núna er ég á struct, og ég get á þessu sviði.

331
00:24:24,600 --> 00:24:28,040
Annaðhvort fá sviði beint eða dereference og fá sviði -

332
00:24:28,040 --> 00:24:30,380
Ég held að þetta ætti að vera gildi.

333
00:24:30,380 --> 00:24:33,910
En hér er ég að fást við bara strúktúr, ekki músina til strúktúr,

334
00:24:33,910 --> 00:24:38,780
og svo ég get ekki notað á örina.

335
00:24:38,780 --> 00:24:47,510
En þessi tegund af hlutur sem við getum gert fyrir alla hnúta.

336
00:24:47,510 --> 00:24:55,790
Guð minn góður.

337
00:24:55,790 --> 00:25:09,540
Þetta er 6, 7, og 3.

338
00:25:09,540 --> 00:25:16,470
Þá getum við sett upp útibú í trénu okkar, getum við fengið 7 -

339
00:25:16,470 --> 00:25:21,650
við getum haft, vinstri þess að benda á 3.

340
00:25:21,650 --> 00:25:25,130
Svo hvernig gera við það?

341
00:25:25,130 --> 00:25:29,320
[Nemendur, óskiljanlegur] >> Já. Heimilisfang node3,

342
00:25:29,320 --> 00:25:34,170
og ef þú did ekki hafa netfang, þá er það bara ekki saman.

343
00:25:34,170 --> 00:25:38,190
En mundu að þetta eru ábendingar til næstu tengipunkta.

344
00:25:38,190 --> 00:25:44,930
Rétt að benda á að 9,

345
00:25:44,930 --> 00:25:53,330
og 3 ætti að benda á rétt í 6.

346
00:25:53,330 --> 00:25:58,480
Ég held að þetta sé allur setja. Allar athugasemdir eða spurningar?

347
00:25:58,480 --> 00:26:02,060
[Námsmaður, óskiljanlegur] Rót er að fara að vera 7.

348
00:26:02,060 --> 00:26:08,210
Við getum bara sagt hnút * PTR =

349
00:26:08,210 --> 00:26:14,160
eða rót, = & node7.

350
00:26:14,160 --> 00:26:20,730
>> Að því er varðar okkar, við erum að fara að takast á við setja inn,

351
00:26:20,730 --> 00:26:25,490
þannig að við erum að fara til að vilja skrifa aðgerð til að setja inn í þennan tvíundartrés

352
00:26:25,490 --> 00:26:34,230
og settu er óhjákvæmilega að fara að hringja malloc að búa til nýjan hnút á þessu tré.

353
00:26:34,230 --> 00:26:36,590
Svo hlutirnir eru að fara að fá sóðalegur með því að sumir hnúður

354
00:26:36,590 --> 00:26:38,590
eru nú á mánudaginn

355
00:26:38,590 --> 00:26:43,680
og aðrir hnútar eru að fara að enda upp á hrúga þegar við setja þá.

356
00:26:43,680 --> 00:26:47,640
Þetta er fullkomlega gild, en eina ástæðan

357
00:26:47,640 --> 00:26:49,600
við erum fær um að gera þetta á mánudaginn

358
00:26:49,600 --> 00:26:51,840
er vegna þess að það er svo háttuð dæmi sem við þekkjum

359
00:26:51,840 --> 00:26:56,360
trénu er ætlað að vera smíðuð 7, 3, 6, 9.

360
00:26:56,360 --> 00:27:02,970
Ef við ekki hafa það, þá myndum við ekki þurfa að malloc í fyrsta sæti.

361
00:27:02,970 --> 00:27:06,160
Eins og við munum sjá svolítið seinna, ættum við að vera malloc'ing.

362
00:27:06,160 --> 00:27:08,570
Núna er það fullkomlega eðlilegt að setja á mánudaginn,

363
00:27:08,570 --> 00:27:14,750
en við skulum breyta þessu til malloc framkvæmd.

364
00:27:14,750 --> 00:27:17,160
Svo hvert þeirra er nú að fara að vera eitthvað eins og

365
00:27:17,160 --> 00:27:24,240
hnút * node9 = malloc (sizeof (hnút)).

366
00:27:24,240 --> 00:27:28,040
Og nú erum við að fara að gera stöðva okkar.

367
00:27:28,040 --> 00:27:34,010
if (node9 == NULL) - ég vildi ekki að -

368
00:27:34,010 --> 00:27:40,950
skila 1, og þá getum við gert node9-> því nú er það bendi,

369
00:27:40,950 --> 00:27:45,300
gildi = 6, node9-> vinstri = NULL,

370
00:27:45,300 --> 00:27:48,930
node9-> hægri = NULL,

371
00:27:48,930 --> 00:27:51,410
og við erum að fara að gera það fyrir hvert af þessum hnúður.

372
00:27:51,410 --> 00:27:57,490
Þannig að í stað, skulum setja það inni í sér virka.

373
00:27:57,490 --> 00:28:00,620
Við skulum kalla það hnút * build_node,

374
00:28:00,620 --> 00:28:09,050
og þetta er nokkuð svipað og API sem við veitum til Huffman kóðun.

375
00:28:09,050 --> 00:28:12,730
Við gefa þér upphafsstillingarlisti virka fyrir tré

376
00:28:12,730 --> 00:28:20,520
og deconstructor "virka" fyrir þá tré og það sama fyrir skógum.

377
00:28:20,520 --> 00:28:22,570
>> Svo hér erum við að fara að hafa upphafsstillingarlisti virka

378
00:28:22,570 --> 00:28:25,170
bara byggja hnút fyrir okkur.

379
00:28:25,170 --> 00:28:29,320
Og það er að fara að líta nokkurn veginn nákvæmlega eins og þetta.

380
00:28:29,320 --> 00:28:32,230
Og ég er enn að fara að vera löt og ekki breyta heiti breytu,

381
00:28:32,230 --> 00:28:34,380
jafnvel þótt node9 gerir ekkert vit lengur.

382
00:28:34,380 --> 00:28:38,610
Oh, held ég gildi node9 ætti ekki að hafa verið 6.

383
00:28:38,610 --> 00:28:42,800
Nú getum við aftur node9.

384
00:28:42,800 --> 00:28:49,550
Og hér erum við að fara aftur null.

385
00:28:49,550 --> 00:28:52,690
Allir sammála um að byggja-a-hnút virka?

386
00:28:52,690 --> 00:28:59,780
Svo nú getum við bara kalla það að byggja hvaða hnút með tilteknu gildi og null ábendingum.

387
00:28:59,780 --> 00:29:09,750
Nú getum við kalla það, getum við gert hnút * node9 = build_node (9).

388
00:29:09,750 --> 00:29:25,810
Og við skulum gera. . .

389
00:29:25,810 --> 00:29:33,980
6, 3, 7, 6, 3, 7.

390
00:29:33,980 --> 00:29:39,330
Og nú viljum við setja upp sömu ábendingar,

391
00:29:39,330 --> 00:29:42,470
nema nú allt er þegar í skilmálar af ábendingum

392
00:29:42,470 --> 00:29:48,480
þannig að ekki lengur þörf heimilisfang.

393
00:29:48,480 --> 00:29:56,300
Allt í lagi. Svo er það síðasta sem ég vil gera?

394
00:29:56,300 --> 00:30:03,850
Það er villa-stöðva sem ég ætla ekki að gera.

395
00:30:03,850 --> 00:30:06,800
Hvað er byggja hnút aftur?

396
00:30:06,800 --> 00:30:11,660
[Námsmaður, óskiljanlegur] >> Já. Ef malloc tókst, verður það aftur null.

397
00:30:11,660 --> 00:30:16,460
Þannig að ég ætla að lazily setja hana niður hér í stað þess að gera skilyrði fyrir hvert.

398
00:30:16,460 --> 00:30:22,320
Ef (node9 == NULL, eða - jafnvel einfaldari,

399
00:30:22,320 --> 00:30:28,020
þetta jafngildir að bara ef ekki node9.

400
00:30:28,020 --> 00:30:38,310
Svo ef ekki node9 eða ekki node6 eða ekki node3 eða ekki node7, skila 1.

401
00:30:38,310 --> 00:30:42,850
Kannski ættum við að prenta malloc mistókst, eða eitthvað.

402
00:30:42,850 --> 00:30:46,680
[Nemandi] er ósatt jafnt null eins og heilbrigður?

403
00:30:46,680 --> 00:30:51,290
[Bowden] Allir núll gildi er falskur.

404
00:30:51,290 --> 00:30:53,920
Svo er núll núll gildi.

405
00:30:53,920 --> 00:30:56,780
Zero er núll gildi. False er núll gildi.

406
00:30:56,780 --> 00:31:02,130
Allir - nánast aðeins 2 núll gildi eru null og núll,

407
00:31:02,130 --> 00:31:07,900
falskur er bara kjötkássa skilgreint sem núll.

408
00:31:07,900 --> 00:31:13,030
Það gildir einnig ef við gerum lýsa alþjóðlegt breytu.

409
00:31:13,030 --> 00:31:17,890
Ef við gerðum með hnút * rót upp hér,

410
00:31:17,890 --> 00:31:24,150
þá - The ágætur hlutur óður í alþjóðlegum breytur er að þeir hafa alltaf byrjunar gildi.

411
00:31:24,150 --> 00:31:27,500
Það er ekki satt að virka, hvernig inni hér,

412
00:31:27,500 --> 00:31:34,870
Ef við höfum, eins og hnút * eða hnút x.

413
00:31:34,870 --> 00:31:37,380
Við höfum ekki hugmynd um hvað x.value, x.whatever,

414
00:31:37,380 --> 00:31:40,700
eða við gætum prentað þá og þeir gætu verið handahófskennt.

415
00:31:40,700 --> 00:31:44,980
Það er ekki satt að alþjóðlegum breytur.

416
00:31:44,980 --> 00:31:47,450
Svo hnút rót eða hnút x.

417
00:31:47,450 --> 00:31:53,410
Sjálfgefið allt sem er alþjóðlegt, ef ekki beinlínis frumstilla að einhverju gildi,

418
00:31:53,410 --> 00:31:57,390
hefur núll gildi sem gildi þess.

419
00:31:57,390 --> 00:32:01,150
Svo hér, hnút * rót, eigum við ekki beinlínis frumstilla hana neitt,

420
00:32:01,150 --> 00:32:06,350
svo sjálfgefið gildi hennar verður núll, sem er núll gildi ábendingum.

421
00:32:06,350 --> 00:32:11,870
Sjálfgefið gildi x er að fara að þýða að x.value er núll,

422
00:32:11,870 --> 00:32:14,260
x.left er núll, og x.right er null.

423
00:32:14,260 --> 00:32:21,070
Svo þar sem það er struct, öllum sviðum strúktúr verður núll gildi.

424
00:32:21,070 --> 00:32:24,410
Við þurfum ekki að nota það hér, þó.

425
00:32:24,410 --> 00:32:27,320
[Námsmaður] The structs eru öðruvísi en aðrar breytur, og aðrar breytur eru

426
00:32:27,320 --> 00:32:31,400
sorp gildi, þetta eru núll?

427
00:32:31,400 --> 00:32:36,220
[Bowden] Aðrir gildi líka. Svo í x, x verður að vera núll.

428
00:32:36,220 --> 00:32:40,070
Ef það er á alþjóðlegum umfangi, það hefur óákveðinn greinir í ensku byrjunar-gildi. >> Lagi.

429
00:32:40,070 --> 00:32:48,950
[Bowden] Annaðhvort upphaflega gildið sem þú gafst henni eða núll.

430
00:32:48,950 --> 00:32:53,260
Ég held að það sér um þetta allt.

431
00:32:53,260 --> 00:32:58,390
>> Allt í lagi. Svo spyr næsta hluta af þeirri spurningu,

432
00:32:58,390 --> 00:33:01,260
"Nú erum við að skrifa fall sem kallast inniheldur

433
00:33:01,260 --> 00:33:04,930
með frumgerð af bool inniheldur int gildi. "

434
00:33:04,930 --> 00:33:08,340
Við erum ekki að fara að gera bool inniheldur int gildi.

435
00:33:08,340 --> 00:33:15,110
Frumgerð okkar er að fara að líta út eins og

436
00:33:15,110 --> 00:33:22,380
bool inniheldur (int gildi.

437
00:33:22,380 --> 00:33:24,490
Og þá erum við líka að fara að gefa það á tréð

438
00:33:24,490 --> 00:33:28,870
að það ætti að stöðva til að sjá hvort það hefur þessi gildi.

439
00:33:28,870 --> 00:33:38,290
Svo hnút * tré). Allt í lagi.

440
00:33:38,290 --> 00:33:44,440
Og þá getum við kalla það með eitthvað eins og,

441
00:33:44,440 --> 00:33:46,090
Kannski við munum vilja printf eða eitthvað.

442
00:33:46,090 --> 00:33:51,040
Inniheldur 6, rót okkar.

443
00:33:51,040 --> 00:33:54,300
Það ætti að fara aftur einn eða sanna,

444
00:33:54,300 --> 00:33:59,390
en inniheldur 5 rót ætti return false.

445
00:33:59,390 --> 00:34:02,690
Svo taka a second til að framkvæma þetta.

446
00:34:02,690 --> 00:34:06,780
Þú getur gert það annað hvort iteratively eða undirmöppum.

447
00:34:06,780 --> 00:34:09,739
The ágætur hlutur óður í the vegur sem við höfum sett það upp að

448
00:34:09,739 --> 00:34:12,300
það lánar sig til endurkvæma lausn okkar miklu auðveldara

449
00:34:12,300 --> 00:34:14,719
en á heimsvísu-breyta leið gerði.

450
00:34:14,719 --> 00:34:19,750
Vegna þess að ef við höfum bara innihalda int gildi, þá höfum við enga leið recursing niður subtrees.

451
00:34:19,750 --> 00:34:24,130
Við yrðum að hafa sérstakan hjálpar fall sem recurses niður subtrees fyrir okkur.

452
00:34:24,130 --> 00:34:29,610
En þar sem við höfum breytt það að taka tré sem rök,

453
00:34:29,610 --> 00:34:32,760
sem hún hefði alltaf verið í fyrsta sæti,

454
00:34:32,760 --> 00:34:35,710
nú getum við Kafa fleiri auðveldlega.

455
00:34:35,710 --> 00:34:38,960
Svo endurtekningu eða endurkvæma, munum við fara yfir bæði,

456
00:34:38,960 --> 00:34:46,139
en við munum sjá að endurkvæma endar að vera mjög auðvelt.

457
00:34:59,140 --> 00:35:02,480
Allt í lagi. Hefur einhver hafa eitthvað við að vinna með?

458
00:35:02,480 --> 00:35:12,000
>> [Nemandi] Ég hef fengið endurtekningu lausn. >> Allt í lagi, endurtekningu.

459
00:35:12,000 --> 00:35:16,030
Jæja, þetta lítur vel út.

460
00:35:16,030 --> 00:35:18,920
Svo, langar að ganga okkur í gegnum það?

461
00:35:18,920 --> 00:35:25,780
[Nemandi] Jú. Svo ég setja afleysingamanneskja breytu til að fá fyrsta hnút í tré.

462
00:35:25,780 --> 00:35:28,330
Og svo ég looped bara í gegnum meðan afleysingamanneskja ekki jafn null,

463
00:35:28,330 --> 00:35:31,700
svo á meðan enn var í trénu, held ég.

464
00:35:31,700 --> 00:35:35,710
Og ef gildið er jafnt gildi sem afleysingamanneskja bendir til,

465
00:35:35,710 --> 00:35:37,640
þá skilar það sem gildi.

466
00:35:37,640 --> 00:35:40,210
Annars stöðva það ef það er á hægri eða vinstri hlið.

467
00:35:40,210 --> 00:35:43,400
Ef þú færð einhvern tíma aðstæður þar sem það er ekkert meira tré,

468
00:35:43,400 --> 00:35:47,330
þá skilar það - það hættir lykkjunnar og skilar falskur.

469
00:35:47,330 --> 00:35:52,190
[Bowden] lagi. Svo virðist sem góður.

470
00:35:52,190 --> 00:35:58,470
Einhver hefur einhverjar athugasemdir um neitt?

471
00:35:58,470 --> 00:36:02,400
Ég hef ekki rétt athugasemdir yfirleitt.

472
00:36:02,400 --> 00:36:11,020
The einn hlutur sem við getum gert er þetta strákur.

473
00:36:11,020 --> 00:36:21,660
Oh, það er að fara að fara smá millisítt.

474
00:36:21,660 --> 00:36:33,460
Ég laga það upp. Allt í lagi.

475
00:36:33,460 --> 00:36:37,150
>> Allir ættu að muna hvernig ternary virkar.

476
00:36:37,150 --> 00:36:38,610
Það hefur ákveðið Skyndipróf verið í fortíðinni

477
00:36:38,610 --> 00:36:41,170
að gefa þér valkost með ternary rekstraraðila,

478
00:36:41,170 --> 00:36:45,750
og segja, þýða það, að gera eitthvað sem ekki nota ternary.

479
00:36:45,750 --> 00:36:49,140
Svo er þetta mjög algeng tilfelli af þegar ég vildi hugsa að nota ternary,

480
00:36:49,140 --> 00:36:54,610
þar sem ef einhver skilyrði sett breytu í eitthvað,

481
00:36:54,610 --> 00:36:58,580
annars sett þessi sömu breytu í eitthvað annað.

482
00:36:58,580 --> 00:37:03,390
Það er eitthvað sem mjög oft er hægt að breyta í þessa tegund af hlutur

483
00:37:03,390 --> 00:37:14,420
þar setja þá breytu í þetta - eða, ja, er þetta satt? Þá er þetta, annars þetta.

484
00:37:14,420 --> 00:37:18,550
[Námsmaður] Sú fyrsta er ef satt, ekki satt?

485
00:37:18,550 --> 00:37:25,570
[Bowden] Já. The vegur ÉG lesa alltaf það er afleysingamanneskja jafngildir verðmæti meiri en gildi afleysingamanneskja,

486
00:37:25,570 --> 00:37:30,680
þá er þetta, annars þetta. Það er að spyrja spurningu.

487
00:37:30,680 --> 00:37:35,200
Er það meira? Þá gera það fyrsta. Annars gera annað hlutur.

488
00:37:35,200 --> 00:37:41,670
Ég næstum alltaf - í ristli, bara ég - í höfðinu á mér, las ég eins og annað.

489
00:37:41,670 --> 00:37:47,180
>> Hefur einhver hafa a endurkvæma lausn?

490
00:37:47,180 --> 00:37:49,670
Allt í lagi. Þetta sem við erum að fara að - það gæti nú þegar verið mikil,

491
00:37:49,670 --> 00:37:53,990
en við erum að fara að gera hana betri jafnvel.

492
00:37:53,990 --> 00:37:58,720
Þetta er laglegur mikill the sami nákvæmur hugmynd.

493
00:37:58,720 --> 00:38:03,060
Það er bara vel, viltu útskýra?

494
00:38:03,060 --> 00:38:08,340
[Nemandi] Jú. Þannig að við erum að tryggja að tréð er ekki núll fyrst

495
00:38:08,340 --> 00:38:13,380
því ef tréð er núll þá er að fara að fara aftur rangt vegna þess að við höfum ekki fundið það.

496
00:38:13,380 --> 00:38:19,200
Og ef það er enn tré, förum við inn - við athuga fyrst hvort gildið er núverandi hnút.

497
00:38:19,200 --> 00:38:23,740
Return satt ef það er, og ef við ekki Kafa til vinstri eða hægri.

498
00:38:23,740 --> 00:38:25,970
Hefur þessi hljóð við? >> Mm-Hmm. (Samningurinn)

499
00:38:25,970 --> 00:38:33,880
Svo eftir að þetta er næstum - byggingarlega mjög svipuð endurtekningu lausn.

500
00:38:33,880 --> 00:38:38,200
Það er bara að í stað þess recursing, við höfðum meðan lykkja.

501
00:38:38,200 --> 00:38:40,840
Og stöð raunin hér þar tré ekki jafn null

502
00:38:40,840 --> 00:38:44,850
var ástand þar sem við braust út úr while lykkju.

503
00:38:44,850 --> 00:38:50,200
Þeir eru mjög svipuð. En við erum að fara að taka þetta einu skrefi lengra.

504
00:38:50,200 --> 00:38:54,190
Nú gerum við það sama hér.

505
00:38:54,190 --> 00:38:57,680
Takið eftir að við erum að skila sama í báðum þessum línum,

506
00:38:57,680 --> 00:39:00,220
nema eitt rifrildi er öðruvísi.

507
00:39:00,220 --> 00:39:07,950
Þannig að við erum að fara að gera það í ternary.

508
00:39:07,950 --> 00:39:13,790
Ég lenti valkostur eitthvað, og það gerði tákn. Allt í lagi.

509
00:39:13,790 --> 00:39:21,720
Þannig að við erum að fara að fara aftur inniheldur það.

510
00:39:21,720 --> 00:39:28,030
Þetta er farin að vera margar línur, Jæja, aðdregna í og ​​það er.

511
00:39:28,030 --> 00:39:31,060
Venjulega, sem stylistic hlutur, ég held ekki að margir

512
00:39:31,060 --> 00:39:38,640
setja pláss eftir ör, en ég held að ef þú ert samkvæmur, það er í lagi.

513
00:39:38,640 --> 00:39:44,320
Ef gildið er minna en gildi tré, viljum við að Kafa í vinstri glugganum,

514
00:39:44,320 --> 00:39:53,890
annað sem við viljum Kafa hægri tré.

515
00:39:53,890 --> 00:39:58,610
Svo var það skref ein að gera þetta líta minni.

516
00:39:58,610 --> 00:40:02,660
Skref tvö að gera þetta líta minni -

517
00:40:02,660 --> 00:40:09,150
við getum aðskilið þetta margar línur.

518
00:40:09,150 --> 00:40:16,500
Allt í lagi. Skref tvö að gera það líta út minni er hér,

519
00:40:16,500 --> 00:40:25,860
svo jafngildir skilagildi tré gildi, eða inniheldur hvað sem er.

520
00:40:25,860 --> 00:40:28,340
>> Þetta er mikilvægur hlutur.

521
00:40:28,340 --> 00:40:30,860
Ég er ekki viss um að ef hann sagði það beinlínis í bekknum,

522
00:40:30,860 --> 00:40:34,740
en það er kallað skammhlaup mat.

523
00:40:34,740 --> 00:40:41,060
Hugmyndin hér er gildi == tré gildi.

524
00:40:41,060 --> 00:40:49,960
Ef það er satt, þá er það satt, og við viljum að "eða" að með hvað sem er hérna.

525
00:40:49,960 --> 00:40:52,520
Svo án þess jafnvel að hugsa um hvað er hérna,

526
00:40:52,520 --> 00:40:55,070
það er allt tjáning fara að koma aftur?

527
00:40:55,070 --> 00:40:59,430
[Nemandi] True? >> Já, því satt um neitt,

528
00:40:59,430 --> 00:41:04,990
or'd - eða satt or'd með nokkuð er endilega satt.

529
00:41:04,990 --> 00:41:08,150
Svo um leið og við sjáum aftur gildi = tré gildi,

530
00:41:08,150 --> 00:41:10,140
við erum bara að fara að fara aftur satt.

531
00:41:10,140 --> 00:41:15,710
Ekki einu sinni að fara að Kafa frekari inniheldur niður línu.

532
00:41:15,710 --> 00:41:20,980
Við getum tekið þetta skrefinu lengra.

533
00:41:20,980 --> 00:41:29,490
Return tré ekki jafn null og allt þetta.

534
00:41:29,490 --> 00:41:32,650
Það gerði það einn-lína virka.

535
00:41:32,650 --> 00:41:36,790
Þetta er einnig dæmi um stutt-hringrás mat.

536
00:41:36,790 --> 00:41:40,680
En nú er það sama hugmynd -

537
00:41:40,680 --> 00:41:47,320
stað - þannig að ef tré er ekki jafn null - eða, ja,

538
00:41:47,320 --> 00:41:49,580
ef tré er jafn null, sem er slæmt mál,

539
00:41:49,580 --> 00:41:54,790
ef tré jafn null, þá fyrsta skilyrðið er að fara að vera falskur.

540
00:41:54,790 --> 00:42:00,550
Svo rangar anded við neitt er að fara að vera það?

541
00:42:00,550 --> 00:42:04,640
[Nemandi] False. >> Já. Þetta er hinn helmingurinn af skammhlaupi mat,

542
00:42:04,640 --> 00:42:10,710
þar sem ef tré er ekki jafn null, þá erum við ekki að fara að jafnvel fara -

543
00:42:10,710 --> 00:42:14,930
eða ef tréð er jafnan null, þá erum við ekki að fara að gera gildi == tré gildi.

544
00:42:14,930 --> 00:42:17,010
Við erum bara að fara strax aftur ósatt.

545
00:42:17,010 --> 00:42:20,970
Sem er mikilvægt, því ef það gerði ekki skammhlaup meta,

546
00:42:20,970 --> 00:42:25,860
þá ef tré er jafn null, Þetta annað ástand er að fara að seg kenna,

547
00:42:25,860 --> 00:42:32,510
því tré-> gildi er dereferencing null.

548
00:42:32,510 --> 00:42:40,490
Svo er það það. Getur þetta - vakt einu sinni yfir.

549
00:42:40,490 --> 00:42:44,840
Þetta er mjög algeng hlutur líka, ekki gera þetta eina línu með þetta,

550
00:42:44,840 --> 00:42:49,000
en það er sameiginlegur hlutur í aðstæður, kannski ekki hérna,

551
00:42:49,000 --> 00:42:59,380
en ef (tré! = NULL, og tré-> gildi == gildi), að gera hvað sem er.

552
00:42:59,380 --> 00:43:01,560
Þetta er mjög algengt ástand, þar sem í stað þess að þurfa

553
00:43:01,560 --> 00:43:06,770
að brjóta í tvennt IFS, þar sem eins er tréð null?

554
00:43:06,770 --> 00:43:11,780
Jæja, það er ekki núll, þannig er nú tré gildi jafnt gildi? Gera þetta.

555
00:43:11,780 --> 00:43:17,300
Þess í stað, þetta ástand, þetta mun aldrei seg sök

556
00:43:17,300 --> 00:43:21,220
vegna þess að það mun brjótast út ef þetta gerist á að vera núll.

557
00:43:21,220 --> 00:43:24,000
Jæja, ég held ef tré er alveg ógilt músina, það geta enn seg kenna,

558
00:43:24,000 --> 00:43:26,620
en það er ekki hægt að seg sök ef tré er null.

559
00:43:26,620 --> 00:43:32,900
Ef það væri null, myndi það brjótast út áður en þú dereferenced alltaf bendilinn í fyrsta sæti.

560
00:43:32,900 --> 00:43:35,000
[Nemandi] þetta er kallað latur mat?

561
00:43:35,000 --> 00:43:40,770
>> [Bowden] Lazy mat er sérstakt mál.

562
00:43:40,770 --> 00:43:49,880
Lazy mat er meira eins og þú biður um gildi,

563
00:43:49,880 --> 00:43:54,270
þú beðið um að reikna út gildi, eins konar, en þú þarft ekki strax.

564
00:43:54,270 --> 00:43:59,040
Svo þar sem þú þarft í raun það, það er ekki metið.

565
00:43:59,040 --> 00:44:03,920
Þetta er ekki nákvæmlega það sama, en í Huffman pset,

566
00:44:03,920 --> 00:44:06,520
það segir að við "lazily" skrifa.

567
00:44:06,520 --> 00:44:08,670
Ástæðan sem við gerum sem er vegna þess að við erum í raun verndað skrifa -

568
00:44:08,670 --> 00:44:11,820
við viljum ekki að skrifa einstaka bita í einu,

569
00:44:11,820 --> 00:44:15,450
eða einstök bæti í einu, viljum við í staðinn að fá klumpur af bæti.

570
00:44:15,450 --> 00:44:19,270
Svo þegar við höfum klumpur af bytes, þá munum við skrifa það út.

571
00:44:19,270 --> 00:44:22,640
Jafnvel þó að þú biður hann að skrifa - og fwrite og fread gera sömu tegund af hlutur.

572
00:44:22,640 --> 00:44:26,260
Þeir biðminni lesa þín og skrifar.

573
00:44:26,260 --> 00:44:31,610
Jafnvel þó að þú biður hann um að skrifa strax, það verður sennilega ekki.

574
00:44:31,610 --> 00:44:34,540
Og þú getur ekki verið viss um að hlutirnir eru að fara að skrifa

575
00:44:34,540 --> 00:44:37,540
þar til þú kalla hfclose eða hvað sem það er,

576
00:44:37,540 --> 00:44:39,620
sem síðan segir, allt í lagi, ég er að loka skrá minn,

577
00:44:39,620 --> 00:44:43,450
sem þýðir að ég myndi betur skrifa allt sem ég hef ekki skrifað enn.

578
00:44:43,450 --> 00:44:45,770
Það hefur ekki þurft að skrifa allt út

579
00:44:45,770 --> 00:44:49,010
þar sem þú ert að loka skrá, og þá þarf að.

580
00:44:49,010 --> 00:44:56,220
Svo er það bara hvað latur - það bíður þar til það er að gerast.

581
00:44:56,220 --> 00:44:59,990
Þetta - að taka 51 og þú munt fara í það nánar,

582
00:44:59,990 --> 00:45:05,470
því OCaml og allt í 51, allt er endurkvæmni.

583
00:45:05,470 --> 00:45:08,890
Það eru ekki endurtekningu lausnir, í grundvallaratriðum.

584
00:45:08,890 --> 00:45:11,550
Allt er endurkvæmni og latur mat

585
00:45:11,550 --> 00:45:14,790
er að fara að vera mikilvægt fyrir a einhver fjöldi af aðstæðum

586
00:45:14,790 --> 00:45:19,920
þar, ef þú hefur ekki lazily meta, sem myndi þýða -

587
00:45:19,920 --> 00:45:24,760
Dæmið er læki, sem eru óendanlega lengi.

588
00:45:24,760 --> 00:45:30,990
Í orði, getur þú hugsa um náttúrlegra talna sem straum af 1-2-3-4-5-6-7,

589
00:45:30,990 --> 00:45:33,090
Svo lazily mat hlutir eru í lagi.

590
00:45:33,090 --> 00:45:37,210
Ef ég segi ég vil tíunda númer, þá get ég meta allt að tíunda fjölda.

591
00:45:37,210 --> 00:45:40,300
Ef ég vil hundraðasta númer, þá get ég metið upp á hundraðasta númer.

592
00:45:40,300 --> 00:45:46,290
Án latur mat, þá er það að fara að reyna að meta allar tölur strax.

593
00:45:46,290 --> 00:45:50,000
Þú ert að meta óendanlega margar tölur, og það er bara ekki hægt.

594
00:45:50,000 --> 00:45:52,080
Þannig að það eru fullt af aðstæðum þar latur mat

595
00:45:52,080 --> 00:45:57,840
er bara nauðsynlegt til að fá hlutina til að virka.

596
00:45:57,840 --> 00:46:05,260
>> Nú viljum við að skrifa Setja sem setja er að fara að vera

597
00:46:05,260 --> 00:46:08,430
álíka breytast í skilgreiningu þess.

598
00:46:08,430 --> 00:46:10,470
Svo núna er það bool setja (int gildi).

599
00:46:10,470 --> 00:46:23,850
Við erum að fara að breyta því til bool setja inn (int gildi, hnútur * tré).

600
00:46:23,850 --> 00:46:29,120
Við erum í raun að fara að breyta því aftur í smá, munum við sjá hvers vegna.

601
00:46:29,120 --> 00:46:32,210
Og við skulum færa build_node, bara til að Heck það,

602
00:46:32,210 --> 00:46:36,730
yfir setja svo við þurfum ekki að skrifa virka frumgerð.

603
00:46:36,730 --> 00:46:42,450
Sem er vísbending um að þú ert að fara að nota build_node í insert.

604
00:46:42,450 --> 00:46:49,590
Allt í lagi. Taktu eina mínútu fyrir það.

605
00:46:49,590 --> 00:46:52,130
Ég held að ég bjargaði endurskoðun ef þú vilt draga úr því,

606
00:46:52,130 --> 00:47:00,240
eða, að minnsta kosti, ég gerði núna.

607
00:47:00,240 --> 00:47:04,190
Ég vildi smá hlé til að hugsa um rökfræði insert,

608
00:47:04,190 --> 00:47:08,750
ef þú getur ekki hugsað um það.

609
00:47:08,750 --> 00:47:12,860
Í grundvallaratriðum, verður þú bara alltaf að setja á laufum.

610
00:47:12,860 --> 00:47:18,640
Eins, ef ég setja 1, þá er ég óhjákvæmilega að fara að setja 1 -

611
00:47:18,640 --> 00:47:21,820
Ég breytt í svart - Ég skal vera að setja 1 hérna.

612
00:47:21,820 --> 00:47:28,070
Eða ef ég set inn 4, vil ég að setja 4 hérna.

613
00:47:28,070 --> 00:47:32,180
Svo er sama hvað þú gerir, þú ert að fara að setja á laufblaði.

614
00:47:32,180 --> 00:47:36,130
Allt sem þú þarft að gera er að iterate niður tré þar til þú fá til the hnút

615
00:47:36,130 --> 00:47:40,890
sem ætti að vera foreldri hnúturinn er, foreldri nýju hnút á,

616
00:47:40,890 --> 00:47:44,560
og breyta vinstri eða hægri bendilinn þess, eftir því hvort

617
00:47:44,560 --> 00:47:47,060
það er meiri en eða minna en núverandi hnút.

618
00:47:47,060 --> 00:47:51,180
Breyting sem bendi til að benda á nýja hnút þinn.

619
00:47:51,180 --> 00:48:05,490
Svo iterate niður tré, gera blaða benda til nýjan hnút.

620
00:48:05,490 --> 00:48:09,810
Einnig hugsa um hvers vegna það bannar tegund af ástandinu áður,

621
00:48:09,810 --> 00:48:17,990
þar sem ég smíða tvöfaldur tré þar sem það var rétt

622
00:48:17,990 --> 00:48:19,920
Ef þú lítur aðeins á einum hnút,

623
00:48:19,920 --> 00:48:24,830
en 9 var vinstra megin við 7 ef þú iterated niður alla leið.

624
00:48:24,830 --> 00:48:29,770
Svo það er ómögulegt í þessari atburðarás, þar sem -

625
00:48:29,770 --> 00:48:32,530
hugsa um að setja 9 eða eitthvað, á mjög fyrsta hnút,

626
00:48:32,530 --> 00:48:35,350
Ég ætla að sjá 7 og ég ætla bara að fara að fara til hægri.

627
00:48:35,350 --> 00:48:38,490
Svo það er sama hvað ég geri, ef ég setja með því að fara í blaða,

628
00:48:38,490 --> 00:48:40,790
og í blöðum með viðeigandi reiknirit,

629
00:48:40,790 --> 00:48:43,130
það er að fara að vera ómögulegt fyrir mig að setja 9 vinstra megin við 7

630
00:48:43,130 --> 00:48:48,250
því um leið og ég lenti 7 Ég ætla að fara til hægri.

631
00:48:59,740 --> 00:49:02,070
Hefur einhver hafa eitthvað til að byrja með?

632
00:49:02,070 --> 00:49:05,480
[Nemandi] ég. >> Jú.

633
00:49:05,480 --> 00:49:09,200
[Námsmaður, óskiljanlegur]

634
00:49:09,200 --> 00:49:14,390
[Önnur nemandi, óskiljanlegur]

635
00:49:14,390 --> 00:49:18,330
[Bowden] Það er vel þegið. Allt í lagi. Viltu útskýra?

636
00:49:18,330 --> 00:49:20,690
>> [Nemandi] Þar sem við vitum að við vorum að setja

637
00:49:20,690 --> 00:49:24,060
nýja hnúta í lok af trénu,

638
00:49:24,060 --> 00:49:28,070
Ég looped gegnum tré iteratively

639
00:49:28,070 --> 00:49:31,360
þangað til ég fékk að hnút sem benti til null.

640
00:49:31,360 --> 00:49:34,220
Og þá ákvað ég að setja það annaðhvort á hægri eða vinstri hlið

641
00:49:34,220 --> 00:49:37,420
nota þetta rétt breytu, það sagði mér hvar á að setja það.

642
00:49:37,420 --> 00:49:41,850
Og þá, í ​​raun, ég gerði bara það síðasta -

643
00:49:41,850 --> 00:49:47,520
að hnútur afleysingamanneskja benda á nýja hnút sem það var að búa til,

644
00:49:47,520 --> 00:49:50,770
annaðhvort vinstra megin eða hægra megin, allt eftir því hvaða gildi rétt var.

645
00:49:50,770 --> 00:49:56,530
Að lokum setti ég nýja hnút gildi gildi rannsóknaraðferðir sínar.

646
00:49:56,530 --> 00:49:59,550
[Bowden] Jæja, svo ég sjá eitt atriði hér.

647
00:49:59,550 --> 00:50:02,050
Þetta er eins og 95% af the vegur þar.

648
00:50:02,050 --> 00:50:07,550
Eina málið sem ég sé vel, hefur einhver annar séð mál?

649
00:50:07,550 --> 00:50:18,400
Hvað er aðstæður þar sem þeir brjótast út úr henni?

650
00:50:18,400 --> 00:50:22,100
[Nemandi] Ef hitastig er núll? >> Já. Svo hvernig þú brýtur út úr lykkja ef hitastig er null.

651
00:50:22,100 --> 00:50:30,220
En hvað á ég að gera hérna?

652
00:50:30,220 --> 00:50:35,410
Ég dereference afleysingamanneskja, sem er óhjákvæmilega null.

653
00:50:35,410 --> 00:50:39,840
Svo er annar hlutur sem þú þarft að gera ekki bara að halda utan fyrr en hitastig er núll,

654
00:50:39,840 --> 00:50:45,590
þú vilt halda utan um foreldri á öllum tímum.

655
00:50:45,590 --> 00:50:52,190
Við viljum líka hnút * foreldri, held ég að við getum haldið að við null í fyrstu.

656
00:50:52,190 --> 00:50:55,480
Þetta er að fara að hafa skrítinn hegðun í rót af trénu,

657
00:50:55,480 --> 00:50:59,210
en við munum komast að því.

658
00:50:59,210 --> 00:51:03,950
Ef gildið er stærra en það sem þá afleysingamanneskja = hitastig rétt.

659
00:51:03,950 --> 00:51:07,910
En áður en við gerum það, foreldri = afleysingamanneskja.

660
00:51:07,910 --> 00:51:14,500
Eða eru foreldrar fara alltaf jafn afleysingamanneskja? Er það málið?

661
00:51:14,500 --> 00:51:19,560
Ef hitastig er ekki núll, þá ætla ég að fara niður, það er sama hvað,

662
00:51:19,560 --> 00:51:24,030
í hnút sem afleysingamanneskja er foreldri.

663
00:51:24,030 --> 00:51:27,500
Svo foreldri er að fara að vera hitastig, og þá skal ég fara afleysingamanneskja niður.

664
00:51:27,500 --> 00:51:32,410
Nú er afleysingamanneskja null, en foreldri bendir á foreldri það sem er null.

665
00:51:32,410 --> 00:51:39,110
Svo hérna, ég vil ekki að setja rétt er 1.

666
00:51:39,110 --> 00:51:41,300
Svo flutti ég til hægri, þannig að ef rétt = 1,

667
00:51:41,300 --> 00:51:45,130
og ég giska á að þú vilt einnig að gera -

668
00:51:45,130 --> 00:51:48,530
Ef þú flytur til vinstri, þú vilja til setja rétt jöfn 0.

669
00:51:48,530 --> 00:51:55,950
Eða annars ef þú færir alltaf til hægri.

670
00:51:55,950 --> 00:51:58,590
Svo rétt = 0. Ef hægri = 1,

671
00:51:58,590 --> 00:52:04,260
nú viljum við gera foreldri rétt músina newnode,

672
00:52:04,260 --> 00:52:08,520
annað sem við viljum gera foreldri vinstri músina newnode.

673
00:52:08,520 --> 00:52:16,850
Spurningar um það?

674
00:52:16,850 --> 00:52:24,880
Allt í lagi. Svo er þetta eins og við - ja, reyndar, í stað þess að gera þetta,

675
00:52:24,880 --> 00:52:29,630
við ráð helmingur að nota build_node.

676
00:52:29,630 --> 00:52:40,450
Og þá ef newnode jafngildir null, return false.

677
00:52:40,450 --> 00:52:44,170
Það er það. Nú, þetta er það sem við ráð fyrir að þú gerir.

678
00:52:44,170 --> 00:52:47,690
>> Þetta er það sem starfsfólk lausnir.

679
00:52:47,690 --> 00:52:52,360
Ég er ósammála með þetta sem "rétta" leið til að fara um það

680
00:52:52,360 --> 00:52:57,820
en þetta er fullkomlega í lagi og það mun vinna.

681
00:52:57,820 --> 00:53:02,840
Eitt sem er svolítið undarlegt núna er

682
00:53:02,840 --> 00:53:08,310
ef tré byrjar eins null, fara við í núll tré.

683
00:53:08,310 --> 00:53:12,650
Ég giska á það fer eftir því hvernig þú skilgreinir hegðun liggur í núll tré.

684
00:53:12,650 --> 00:53:15,490
Ég myndi held að ef það líður yfir í núll tré,

685
00:53:15,490 --> 00:53:17,520
þá setja gildi í núll tré

686
00:53:17,520 --> 00:53:23,030
ætti bara að fara aftur upp í tré þar sem aðeins gildi að einn hnút.

687
00:53:23,030 --> 00:53:25,830
Ekki fólk sammála því? Þú gætir, ef þú vildir,

688
00:53:25,830 --> 00:53:28,050
Ef þú fara í núll tré

689
00:53:28,050 --> 00:53:31,320
og þú vilt að setja gildi inn í það, aftur rangt.

690
00:53:31,320 --> 00:53:33,830
Það er komið að þér að skilgreina það.

691
00:53:33,830 --> 00:53:38,320
Til að gera það fyrsta sem ég sagði og þá -

692
00:53:38,320 --> 00:53:40,720
Jæja, þú ert að fara að eiga erfitt með að gera það, vegna þess að

693
00:53:40,720 --> 00:53:44,090
það væri auðveldara ef við hefðum á heimsvísu bendi til þings,

694
00:53:44,090 --> 00:53:48,570
en við ekki, þannig að ef tré er núll, það er ekkert sem við getum gert það.

695
00:53:48,570 --> 00:53:50,960
Við getum bara aftur rangar.

696
00:53:50,960 --> 00:53:52,840
Þannig að ég ætla að breyta Setja.

697
00:53:52,840 --> 00:53:56,540
Við tæknilega gæti bara breyta hérna,

698
00:53:56,540 --> 00:53:58,400
hvernig það er iterating yfir hlutum,

699
00:53:58,400 --> 00:54:04,530
en ég ætla að breyta setja inn til að taka hnúturinn ** tré.

700
00:54:04,530 --> 00:54:07,510
Double ábendingar.

701
00:54:07,510 --> 00:54:09,710
Hvað þýðir þetta?

702
00:54:09,710 --> 00:54:12,330
Í stað þess að takast á við ábendingum til hnúður,

703
00:54:12,330 --> 00:54:16,690
það sem ég ætla að notfæra sé þetta bendi.

704
00:54:16,690 --> 00:54:18,790
Ég ætla að hagræða þessu músina.

705
00:54:18,790 --> 00:54:21,770
Ég ætla að notfæra ábendingum beint.

706
00:54:21,770 --> 00:54:25,760
Þetta er skynsamlegt þar, hugsa um niður -

707
00:54:25,760 --> 00:54:33,340
Jæja, núna Þetta bendir til að null.

708
00:54:33,340 --> 00:54:38,130
Það sem ég vil gera er að vinna þetta bendi til að benda á að ekki null.

709
00:54:38,130 --> 00:54:40,970
Ég vil það að benda á nýja hnút minn.

710
00:54:40,970 --> 00:54:44,870
Ef bara halda utan um ábendingar til að ábendingum mínum,

711
00:54:44,870 --> 00:54:47,840
svo ég þarf ekki að halda utan um foreldri músina.

712
00:54:47,840 --> 00:54:52,640
Ég get bara fylgst með til að sjá hvort bendillinn er að benda að núll,

713
00:54:52,640 --> 00:54:54,580
og ef bendillinn er að benda að núll,

714
00:54:54,580 --> 00:54:57,370
breyta því að benda á hnútinn sem ég vil.

715
00:54:57,370 --> 00:55:00,070
Og ég get breytt því þar sem ég er með músina á músina.

716
00:55:00,070 --> 00:55:02,040
Við skulum sjá þetta núna.

717
00:55:02,040 --> 00:55:05,470
Þú getur í raun gert það endurkvæmt nokkuð auðveldlega.

718
00:55:05,470 --> 00:55:08,080
Viljum við gera það?

719
00:55:08,080 --> 00:55:10,980
Já, gerum við.

720
00:55:10,980 --> 00:55:16,790
>> Við skulum sjá það endurkvæmt.

721
00:55:16,790 --> 00:55:24,070
Fyrst, hvað er undirstaða okkar tilviki að fara að vera?

722
00:55:24,070 --> 00:55:29,140
Næstum alltaf stöð mál okkar, en í raun, það er góður af erfiður.

723
00:55:29,140 --> 00:55:34,370
Fyrstur hlutur fyrstur, ef (tré == NULL)

724
00:55:34,370 --> 00:55:37,550
Ég held að við erum bara að fara að fara aftur ósatt.

725
00:55:37,550 --> 00:55:40,460
Þetta er ólíkt tré að vera null.

726
00:55:40,460 --> 00:55:44,510
Þetta er bendi á rót músina þína vera null

727
00:55:44,510 --> 00:55:48,360
sem þýðir að rót bendillinn þinn er ekki til.

728
00:55:48,360 --> 00:55:52,390
Svo hérna, ef ég

729
00:55:52,390 --> 00:55:55,760
hnút * - við skulum bara endurnýta þetta.

730
00:55:55,760 --> 00:55:58,960
Hnútur * rót = NULL,

731
00:55:58,960 --> 00:56:00,730
og þá ætla ég að hringja í Insert með því að gera eitthvað eins og,

732
00:56:00,730 --> 00:56:04,540
setja 4 í & rót.

733
00:56:04,540 --> 00:56:06,560
Svo og rót, ef rót er hnútur *

734
00:56:06,560 --> 00:56:11,170
þá og rót er að fara til vera a hnút **.

735
00:56:11,170 --> 00:56:15,120
Þetta gildir. Í þessu tilfelli, tré, allt hér,

736
00:56:15,120 --> 00:56:20,120
tré er ekki núll - eða setja.

737
00:56:20,120 --> 00:56:24,630
Hér. Tree er ekki núll, * tré er núll, sem er fínt

738
00:56:24,630 --> 00:56:26,680
því ef * tré er núll, þá get ég vinna það

739
00:56:26,680 --> 00:56:29,210
að nú benda á það sem ég vil það til að benda á.

740
00:56:29,210 --> 00:56:34,750
En ef tré er núll, sem þýðir að ég kom bara niður og sagði null.

741
00:56:34,750 --> 00:56:42,710
Það er ekki skynsamleg. Ég get ekki gert neitt með það.

742
00:56:42,710 --> 00:56:45,540
Ef tré er núll, return false.

743
00:56:45,540 --> 00:56:48,220
Svo ég sagði í rauninni þegar það alvöru stöð ef okkar er.

744
00:56:48,220 --> 00:56:50,580
Og hvað er að fara að vera?

745
00:56:50,580 --> 00:56:55,030
[Námsmaður, óskiljanlegur]

746
00:56:55,030 --> 00:57:00,000
[Bowden] Já. Svo ef (* tré == NULL).

747
00:57:00,000 --> 00:57:04,520
Þetta varðar málið hérna

748
00:57:04,520 --> 00:57:09,640
þar sem ef rautt músina mín er bendillinn ég áherslu á,

749
00:57:09,640 --> 00:57:12,960
svo eins og ég áherslu á þetta bendi, nú er ég áherslu á þessa músina.

750
00:57:12,960 --> 00:57:15,150
Nú er ég áherslu á þessa músina.

751
00:57:15,150 --> 00:57:18,160
Svo ef rautt músina mín, sem er hnút ** mínir

752
00:57:18,160 --> 00:57:22,880
er alltaf - ef *, rauður bendillinn minn er alltaf núll,

753
00:57:22,880 --> 00:57:28,470
sem þýðir að ég er að ræða þar sem ég er með áherslu á músina sem vísar -

754
00:57:28,470 --> 00:57:32,530
þetta er bendillinn sem tilheyrir blöðum.

755
00:57:32,530 --> 00:57:41,090
Ég vil breyta þessu bendi til að benda á nýja hnút minn.

756
00:57:41,090 --> 00:57:45,230
Komdu hérna.

757
00:57:45,230 --> 00:57:56,490
Newnode minn mun bara vera hnút * n = build_node (gildi)

758
00:57:56,490 --> 00:58:07,300
þá n, ef n = null, return false.

759
00:58:07,300 --> 00:58:12,600
Annars viljum við breyta því sem bendillinn er nú að benda á að

760
00:58:12,600 --> 00:58:17,830
að nú benda á nýlega byggð hnút okkar.

761
00:58:17,830 --> 00:58:20,280
Við getum í raun gert það hér.

762
00:58:20,280 --> 00:58:30,660
Í stað þess að segja n segja við * Tré = ef * tré.

763
00:58:30,660 --> 00:58:35,450
Allir skilja það? Að með því að takast á við ábendingum á ábendingum,

764
00:58:35,450 --> 00:58:40,750
við getum breytt null ábendingum til að benda á það sem við viljum þá til að benda á.

765
00:58:40,750 --> 00:58:42,820
Það er undirstaða okkar tilviki.

766
00:58:42,820 --> 00:58:45,740
>> Nú endurkomu okkar eða endurkvæmni okkar,

767
00:58:45,740 --> 00:58:51,430
er að fara að vera mjög svipuð öllum öðrum recursions við höfum verið að gera.

768
00:58:51,430 --> 00:58:55,830
Við erum að fara til að vilja setja gildi,

769
00:58:55,830 --> 00:58:59,040
og nú ætla ég að nota ternary aftur, en það er ástand okkar að fara að vera?

770
00:58:59,040 --> 00:59:05,180
Hvað er það sem við erum að leita að til að ákveða hvort við viljum fara til vinstri eða hægri?

771
00:59:05,180 --> 00:59:07,760
Við skulum gera það í sérstökum skrefum.

772
00:59:07,760 --> 00:59:18,850
Ef (gildi <) hvað?

773
00:59:18,850 --> 00:59:23,200
[Nemandi] gildi tréð er?

774
00:59:23,200 --> 00:59:27,490
[Bowden] Svo muna að ég er nú -

775
00:59:27,490 --> 00:59:31,260
[Nemendur, óskiljanlegur]

776
00:59:31,260 --> 00:59:34,140
[Bowden] Já, svo hérna, við skulum segja að þetta græna ör

777
00:59:34,140 --> 00:59:39,050
er dæmi um hvað tré eins og er, er bendi á þessa músina.

778
00:59:39,050 --> 00:59:46,610
Svo þýðir að ég bendi á músina til 3.

779
00:59:46,610 --> 00:59:48,800
The dereference hljómaði tvisvar vel.

780
00:59:48,800 --> 00:59:51,010
Hvað geri ég - hvernig geri ég það?

781
00:59:51,010 --> 00:59:53,210
[Nemandi] Dereference einu sinni, og þá gera ör þannig?

782
00:59:53,210 --> 00:59:58,420
[Bowden] Svo (* tré) er dereference einu sinni, -> gildi

783
00:59:58,420 --> 01:00:05,960
er að fara að gefa mér gildi hnút sem ég er óbeint bendir til.

784
01:00:05,960 --> 01:00:11,980
Svo ég get líka skrifað það ** tree.value ef þú vilt það.

785
01:00:11,980 --> 01:00:18,490
Annaðhvort virkar.

786
01:00:18,490 --> 01:00:26,190
Ef sú er raunin, þá vil ég kalla settu með gildi.

787
01:00:26,190 --> 01:00:32,590
Og hvað er uppfærð hnút minn ** að fara að vera?

788
01:00:32,590 --> 01:00:39,440
Mig langar til að fara til vinstri, svo ** tree.left er að fara að vera vinstri minn.

789
01:00:39,440 --> 01:00:41,900
Og ég vil bendilinn að þessi hlutur

790
01:00:41,900 --> 01:00:44,930
þannig að ef vinstri endar að vera null músina,

791
01:00:44,930 --> 01:00:48,360
Ég get breytt því að benda á nýja hnút minn.

792
01:00:48,360 --> 01:00:51,460
>> Og hitt málið getur verið mjög svipuð.

793
01:00:51,460 --> 01:00:55,600
Við skulum í raun gera það ternary minn núna.

794
01:00:55,600 --> 01:01:04,480
Settu gildi ef gildi <(** tré). Gildi.

795
01:01:04,480 --> 01:01:11,040
Þá viljum við að uppfæra ** okkar til vinstri,

796
01:01:11,040 --> 01:01:17,030
annað sem við viljum uppfæra ** okkar til hægri.

797
01:01:17,030 --> 01:01:22,540
[Nemandi] Er að fá bendi á músina?

798
01:01:22,540 --> 01:01:30,940
[Bowden] Mundu að - ** tree.right er hnútur stjarna.

799
01:01:30,940 --> 01:01:35,040
[Námsmaður, óskiljanlegur] >> Já.

800
01:01:35,040 --> 01:01:41,140
** Tree.right er svona músina eða eitthvað.

801
01:01:41,140 --> 01:01:45,140
Svo með því að taka bendi á það, sem gefur mér það sem ég vil

802
01:01:45,140 --> 01:01:50,090
á músina til að strákur.

803
01:01:50,090 --> 01:01:54,260
[Nemandi] gætum við farið aftur hvers vegna við erum að nota tvær ábendingar?

804
01:01:54,260 --> 01:01:58,220
[Bowden] Já. Svo - Nei, þú getur, og að lausn fyrir

805
01:01:58,220 --> 01:02:04,540
var leið til að gera það án þess að gera tvo punkta.

806
01:02:04,540 --> 01:02:08,740
Þú þarft að vera fær um að skilja að nota tvær ábendingar,

807
01:02:08,740 --> 01:02:11,660
og þetta er hreinni lausn.

808
01:02:11,660 --> 01:02:16,090
Einnig, eftir því, hvað gerist ef tré minn -

809
01:02:16,090 --> 01:02:24,480
hvað gerist ef rót minn var null? Hvað gerist ef ég geri þetta mál hérna?

810
01:02:24,480 --> 01:02:30,540
Svo hnút * rót = NULL, setja 4 í & rót.

811
01:02:30,540 --> 01:02:35,110
Hvað er rót að fara að vera eftir þetta?

812
01:02:35,110 --> 01:02:37,470
[Námsmaður, óskiljanlegur] >> Já.

813
01:02:37,470 --> 01:02:41,710
Root gildi er að fara að vera 4.

814
01:02:41,710 --> 01:02:45,510
Rót vinstri er að fara að vera núll, rót rétt er að fara að vera null.

815
01:02:45,510 --> 01:02:49,490
Í tilfelli þar sem við vildum ekki fara rót eftir heimilisfangi,

816
01:02:49,490 --> 01:02:52,490
við gátum ekki breyta rót.

817
01:02:52,490 --> 01:02:56,020
Í tilviki þar sem tré - sem rót var null,

818
01:02:56,020 --> 01:02:58,410
við þurftum bara að skila falskur. Það er ekkert sem við gætum gert.

819
01:02:58,410 --> 01:03:01,520
Við getum ekki sett í hnút í tómt tré.

820
01:03:01,520 --> 01:03:06,810
En nú getum við, við tökum bara tómt tré í einn hnút tré.

821
01:03:06,810 --> 01:03:13,400
Sem er yfirleitt áætlað þannig að það er ætlast til að vinna.

822
01:03:13,400 --> 01:03:21,610
>> Jafnframt er verulega styttri en

823
01:03:21,610 --> 01:03:26,240
einnig að halda utan um foreldri, og svo þú iterate niður alla leið.

824
01:03:26,240 --> 01:03:30,140
Nú hef ég foreldri mitt, og ég hef bara foreldri rétt músina mína til hvað sem er.

825
01:03:30,140 --> 01:03:35,640
Staðinn, ef við gerðum þetta iteratively, myndi það vera sama hugmyndin með while lykkju.

826
01:03:35,640 --> 01:03:38,100
En í stað þess að þurfa að takast á við músina foreldra mína,

827
01:03:38,100 --> 01:03:40,600
stað núverandi bendill minn væri hlutur

828
01:03:40,600 --> 01:03:43,790
sem ég er beint að breyta til að benda á nýja hnút minn.

829
01:03:43,790 --> 01:03:46,090
Ég þarf ekki að takast á við hvort sem það er að benda til vinstri.

830
01:03:46,090 --> 01:03:48,810
Ég þarf ekki að takast á við hvort sem það er að benda til hægri.

831
01:03:48,810 --> 01:04:00,860
Það er bara hvað þetta bendillinn er, ég ætla að setja það til að benda á nýja hnút minn.

832
01:04:00,860 --> 01:04:05,740
Allir skilja hvernig það virkar?

833
01:04:05,740 --> 01:04:09,460
Ef ekki hvers vegna viljum við gera það með þessum hætti,

834
01:04:09,460 --> 01:04:14,920
en að minnsta kosti að þetta virkar sem lausn?

835
01:04:14,920 --> 01:04:17,110
[Nemandi] Hvar aftur við satt?

836
01:04:17,110 --> 01:04:21,550
[Bowden] Það er líklega hérna.

837
01:04:21,550 --> 01:04:26,690
Ef við setja rétt það aftur að veruleika.

838
01:04:26,690 --> 01:04:32,010
Annars, hérna erum við að fara að vilja til að fara aftur hvað sem setja inn aftur.

839
01:04:32,010 --> 01:04:35,950
>> Og hvað er sérstakt við þennan endurkvæma virka?

840
01:04:35,950 --> 01:04:43,010
Það er hali endurkvæma, svo lengi sem við safna saman með einhverjum hagræðingu,

841
01:04:43,010 --> 01:04:48,060
það mun viðurkenna það og þú munt aldrei fá stafla flæða frá þessu,

842
01:04:48,060 --> 01:04:53,230
jafnvel ef tré okkar hefur hæð um 10.000 eða 10 milljónir króna.

843
01:04:53,230 --> 01:04:55,630
[Námsmaður, óskiljanlegur]

844
01:04:55,630 --> 01:05:00,310
[Bowden] Ég held að það gerir það í Dash - eða hvað hagræðing stigi

845
01:05:00,310 --> 01:05:03,820
þarf fyrir hali endurkvæmni að vera viðurkennd.

846
01:05:03,820 --> 01:05:09,350
Ég held að það viðurkennir - GCC og Clang

847
01:05:09,350 --> 01:05:12,610
einnig hafa mismunandi merkingu fyrir stigum hagræðingu þeirra.

848
01:05:12,610 --> 01:05:17,870
Mig langar að segja að það er DashO 2, fyrir víst að það mun viðurkenna hali endurkvæmni.

849
01:05:17,870 --> 01:05:27,880
En við - þú gætir byggja eins Fibonocci dæmi eða eitthvað.

850
01:05:27,880 --> 01:05:30,030
Það er ekki auðvelt að prófa þetta, því það er erfitt að reisa

851
01:05:30,030 --> 01:05:32,600
tvöfaldur tré sem er svo stór.

852
01:05:32,600 --> 01:05:37,140
En já, ég held að það DashO 2, sem

853
01:05:37,140 --> 01:05:40,580
Ef þú saman við DashO 2, mun það leita endurkvæmni hali

854
01:05:40,580 --> 01:05:54,030
og bjartsýni það út.

855
01:05:54,030 --> 01:05:58,190
Förum aftur til - setja er bókstaflega síðasta sem það þarf.

856
01:05:58,190 --> 01:06:04,900
Við skulum fara aftur til innskotsins hérna

857
01:06:04,900 --> 01:06:07,840
þar sem við erum að fara að gera sömu hugmynd.

858
01:06:07,840 --> 01:06:14,340
Það verður samt að hafa galli að geta ekki alveg séð

859
01:06:14,340 --> 01:06:17,940
þegar rót sjálft er núll, eða síðasta færsla er núll,

860
01:06:17,940 --> 01:06:20,060
en í stað þess að takast á við foreldra bendi,

861
01:06:20,060 --> 01:06:27,430
við skulum nota sömu rökfræði halda ábendingum á ábendingum.

862
01:06:27,430 --> 01:06:35,580
Ef hér við halda hnút okkar ** nú,

863
01:06:35,580 --> 01:06:37,860
og við þurfum ekki að halda utan um rétt lengur,

864
01:06:37,860 --> 01:06:47,190
en hnútur ** nú = & tré.

865
01:06:47,190 --> 01:06:54,800
Og nú meðan lykkja okkar er að fara að vera á meðan * nú ekki jafn null.

866
01:06:54,800 --> 01:07:00,270
Ekki þarf að halda utan um foreldra lengur.

867
01:07:00,270 --> 01:07:04,180
Ekki þarf að halda utan um vinstri og hægri.

868
01:07:04,180 --> 01:07:10,190
Og ég kalla það afleysingamanneskja, vegna þess að við erum nú þegar að nota afleysingamanneskja.

869
01:07:10,190 --> 01:07:17,200
Allt í lagi. Svo ef (gildi> * Temp)

870
01:07:17,200 --> 01:07:24,010
þá & (* afleysingamanneskja) -> hægri

871
01:07:24,010 --> 01:07:29,250
annars Temp = & (* afleysingamanneskja) -> vinstri.

872
01:07:29,250 --> 01:07:32,730
Og nú, á þessum tímapunkti, eftir þessa while lykkju,

873
01:07:32,730 --> 01:07:36,380
Ég geri bara þetta vegna þess að kannski er auðveldara að hugsa um iteratively en endurkvæmt,

874
01:07:36,380 --> 01:07:39,010
en eftir þessa while lykkju,

875
01:07:39,010 --> 01:07:43,820
* Hitastig er bendillinn við viljum breyta.

876
01:07:43,820 --> 01:07:48,960
>> Áður en við höfðum foreldri, og við vildum að breyta annað hvort foreldri vinstri eða foreldri rétt,

877
01:07:48,960 --> 01:07:51,310
en ef við viljum breyta foreldri rétt,

878
01:07:51,310 --> 01:07:54,550
þá er * afleysingamanneskja foreldri rétt, og við getum breytt því beint.

879
01:07:54,550 --> 01:08:05,860
Svo hérna getum við gert * afleysingamanneskja = newnode, og það er það.

880
01:08:05,860 --> 01:08:09,540
Svo fyrirvara, allt sem við gerðum í þessu var að taka út línur af kóða.

881
01:08:09,540 --> 01:08:14,770
Til þess að halda utan um foreldri í allt sem er til viðbótar átaki.

882
01:08:14,770 --> 01:08:18,689
Hér, ef við höldum bara utan um músina á músina,

883
01:08:18,689 --> 01:08:22,990
og jafnvel ef við vildum fá losa af öllum þessum hrokkið axlabönd nú,

884
01:08:22,990 --> 01:08:27,170
gera það líta styttri.

885
01:08:27,170 --> 01:08:32,529
Þetta er nú það nákvæmlega sama lausnin,

886
01:08:32,529 --> 01:08:38,210
en færri línur af kóða.

887
01:08:38,210 --> 01:08:41,229
Þegar þú byrjar að viðurkenna þetta sem gild lausn,

888
01:08:41,229 --> 01:08:43,529
það er líka auðveldara að ástæðu um en eins og, allt í lagi,

889
01:08:43,529 --> 01:08:45,779
af hverju hef ég þessa fána á int rétt?

890
01:08:45,779 --> 01:08:49,290
Hvað þýðir það? Oh, það er merkir að

891
01:08:49,290 --> 01:08:51,370
í hvert skipti sem ég fer til hægri, þarf ég að setja það,

892
01:08:51,370 --> 01:08:53,819
annars ef ég fer eftir sem ég þarf að setja það á núll.

893
01:08:53,819 --> 01:09:04,060
Hér hef ég ekki að ástæða um það, það er bara auðveldara að hugsa um.

894
01:09:04,060 --> 01:09:06,710
Spurningar?

895
01:09:06,710 --> 01:09:16,290
[Námsmaður, óskiljanlegur] >> Já.

896
01:09:16,290 --> 01:09:23,359
Jæja, svo í síðasta hluti -

897
01:09:23,359 --> 01:09:28,080
Ég giska á einn fljótleg og auðveld aðgerð sem við getum gert er,

898
01:09:28,080 --> 01:09:34,910
let's - saman, ég giska á, að reyna að skrifa inniheldur virka

899
01:09:34,910 --> 01:09:38,899
sem er ekki sama hvort það er tvöfaldur leita tré.

900
01:09:38,899 --> 01:09:43,770
Þetta inniheldur virka ætti að skila satt

901
01:09:43,770 --> 01:09:58,330
Ef einhvers staðar í þessu almenna tvöfaldur tré er gildi sem við erum að leita að.

902
01:09:58,330 --> 01:10:02,520
Svo skulum fyrst gera það endurkvæmt og þá munum við gera það iteratively.

903
01:10:02,520 --> 01:10:07,300
Við getum í raun bara að gera það saman, vegna þess að þetta er að fara að vera mjög stutt.

904
01:10:07,300 --> 01:10:11,510
>> Hvað er undirstaða mál mitt að fara að vera?

905
01:10:11,510 --> 01:10:13,890
[Námsmaður, óskiljanlegur]

906
01:10:13,890 --> 01:10:18,230
[Bowden] Þannig að ef (tré == NULL), hvað þá?

907
01:10:18,230 --> 01:10:22,740
[Nemandi] return false.

908
01:10:22,740 --> 01:10:26,160
[Bowden] Annars, vel, ég þarf ekki annað.

909
01:10:26,160 --> 01:10:30,250
Ef væri önnur stöð mál mitt.

910
01:10:30,250 --> 01:10:32,450
[Námsmaður] tré gildi? >> Já.

911
01:10:32,450 --> 01:10:36,430
Svo ef (tré-> gildi == gildi.

912
01:10:36,430 --> 01:10:39,920
Takið eftir að við erum aftur í hnút *, ekki hnút ** s?

913
01:10:39,920 --> 01:10:42,990
Contains mun aldrei þurfa að nota hnút **,

914
01:10:42,990 --> 01:10:45,480
þar sem við erum ekki að breyta ábendingum.

915
01:10:45,480 --> 01:10:50,540
Við erum bara að fara yfir þá.

916
01:10:50,540 --> 01:10:53,830
Ef það gerist, þá viljum við að aftur satt.

917
01:10:53,830 --> 01:10:58,270
Annars viljum við fara yfir börnunum.

918
01:10:58,270 --> 01:11:02,620
Þannig að við getum ekki rökrætt um það hvort allt til vinstri er minna

919
01:11:02,620 --> 01:11:05,390
og allt til hægri er meiri.

920
01:11:05,390 --> 01:11:09,590
Svo er það skilyrði okkar að fara að vera hér - eða, hvað ætlum við að gera?

921
01:11:09,590 --> 01:11:11,840
[Námsmaður, óskiljanlegur] >> Já.

922
01:11:11,840 --> 01:11:17,400
Return inniheldur (gildi, tré-> vinstri)

923
01:11:17,400 --> 01:11:26,860
eða inniheldur (gildi, tré-> hægri). Og það er það.

924
01:11:26,860 --> 01:11:29,080
Og eftir því að það er einhver skammhlaup mat,

925
01:11:29,080 --> 01:11:32,520
þar sem ef við gerast til að finna gildi í vinstri glugganum,

926
01:11:32,520 --> 01:11:36,820
Við þurfum aldrei að líta á réttum tré.

927
01:11:36,820 --> 01:11:40,430
Það er allt virka.

928
01:11:40,430 --> 01:11:43,690
Nú skulum gera það iteratively,

929
01:11:43,690 --> 01:11:48,060
sem er að fara að vera minna gaman.

930
01:11:48,060 --> 01:11:54,750
Við tökum venjulega upphaf hnút * gjald = tré.

931
01:11:54,750 --> 01:12:03,250
Meðan (nú! = NULL).

932
01:12:03,250 --> 01:12:08,600
Fljótt að fara að sjá vandann.

933
01:12:08,600 --> 01:12:12,250
Ef nú - hér, ef við brjóta alltaf út af þessu,

934
01:12:12,250 --> 01:12:16,020
þá höfum við keyrt út af hlutum til að líta á, svo aftur rangt.

935
01:12:16,020 --> 01:12:24,810
Ef (nú-> gildi == gildi), aftur við.

936
01:12:24,810 --> 01:12:32,910
Svo nú erum við á stað -

937
01:12:32,910 --> 01:12:36,250
við vitum ekki hvort við viljum fara til vinstri eða hægri.

938
01:12:36,250 --> 01:12:44,590
Svo geðþótta, við skulum bara fara til vinstri.

939
01:12:44,590 --> 01:12:47,910
Ég hef greinilega keyrt inn í mál þar sem ég hef alveg yfirgefin allt -

940
01:12:47,910 --> 01:12:50,760
Ég mun bara alltaf stöðva á vinstri hlið af tré.

941
01:12:50,760 --> 01:12:56,050
Ég mun aldrei athuga eitthvað sem er rétt barn neitt.

942
01:12:56,050 --> 01:13:00,910
Hvernig laga ég þetta?

943
01:13:00,910 --> 01:13:05,260
[Nemandi] Þú þarft að halda utan um vinstri og hægri í stafla.

944
01:13:05,260 --> 01:13:13,710
[Bowden] Já. Svo skulum gera það

945
01:13:13,710 --> 01:13:32,360
struct lista, hnút * N, og þá hnút ** næst?

946
01:13:32,360 --> 01:13:40,240
Ég held að það virkar fínt.

947
01:13:40,240 --> 01:13:45,940
Við viljum fara yfir til vinstri, eða let's - upp hér.

948
01:13:45,940 --> 01:13:54,350
Struct lista lista =, verður það að byrja

949
01:13:54,350 --> 01:13:58,170
út á þessu strúktúrinn lista.

950
01:13:58,170 --> 01:14:04,040
* List = NULL. Svo er að fara að vera tengd lista okkar

951
01:14:04,040 --> 01:14:08,430
á subtrees sem við höfum sleppt yfir.

952
01:14:08,430 --> 01:14:13,800
Við ætlum að fara yfir til vinstri nú,

953
01:14:13,800 --> 01:14:17,870
en þar sem við þurfum óhjákvæmilega að koma aftur til hægri,

954
01:14:17,870 --> 01:14:26,140
Við ætlum að halda hægra megin inni í lista strúktúrinn okkar.

955
01:14:26,140 --> 01:14:32,620
Síðan munum við hafa new_list eða strúktúr,

956
01:14:32,620 --> 01:14:41,080
struct lista *, new_list = malloc (sizeof (listi)).

957
01:14:41,080 --> 01:14:44,920
Ég ætla að hunsa villa-stöðva það, en þú ættir að athuga að sjá null ef það er.

958
01:14:44,920 --> 01:14:50,540
New_list hnúturinn það er að fara að benda á -

959
01:14:50,540 --> 01:14:56,890
ó, það er ástæða þess að ég vildi það upp hér. Það er að fara að benda á annan strúktúrinn lista.

960
01:14:56,890 --> 01:15:02,380
Það er bara hvernig tengist listum vinna.

961
01:15:02,380 --> 01:15:04,810
Þetta er það sama sem int tengd lista

962
01:15:04,810 --> 01:15:06,960
nema að við erum bara að skipta int með hnút *.

963
01:15:06,960 --> 01:15:11,040
Það er nákvæmlega það sama.

964
01:15:11,040 --> 01:15:15,100
Svo new_list, verðmæti hnút new_list okkar,

965
01:15:15,100 --> 01:15:19,120
er að fara að vera nú-> hægri.

966
01:15:19,120 --> 01:15:24,280
Verðmæti okkar new_list-> Næsta er að fara að vera frumleg lista okkar,

967
01:15:24,280 --> 01:15:30,760
og þá ætlum við að uppfæra lista okkar til að benda á new_list.

968
01:15:30,760 --> 01:15:33,650
>> Nú þurfum við einhverskonar leið draga hluti,

969
01:15:33,650 --> 01:15:37,020
eins og við höfum traversed allt vinstri subtree.

970
01:15:37,020 --> 01:15:40,480
Nú þurfum við að draga efni út af því,

971
01:15:40,480 --> 01:15:43,850
eins og nú er núll, við viljum ekki bara aftur ósatt.

972
01:15:43,850 --> 01:15:50,370
Við viljum nú draga út á nýja listann okkar.

973
01:15:50,370 --> 01:15:53,690
A þægilegri leið til að gera þetta - ja, reyndar, það er margar leiðir til að gera þetta.

974
01:15:53,690 --> 01:15:56,680
Einhver með uppástungu?

975
01:15:56,680 --> 01:15:58,790
Þar sem ég ætti að gera þetta eða hvernig ég ætti að gera þetta?

976
01:15:58,790 --> 01:16:08,010
Við höfum aðeins nokkrar mínútur, en einhverjar uppástungur?

977
01:16:08,010 --> 01:16:14,750
Í stað þess - ein leið, í stað þess að ástand okkar að vera á meðan,

978
01:16:14,750 --> 01:16:17,090
það sem við erum nú að leita að er ekki núll,

979
01:16:17,090 --> 01:16:22,340
stað þess að við erum að fara að halda áfram að fara fram lista okkar sjálft er null.

980
01:16:22,340 --> 01:16:25,680
Svo ef lista okkar endar að vera núll,

981
01:16:25,680 --> 01:16:30,680
þá höfum við keyrt út af hlutum til að leita að, til að leita á.

982
01:16:30,680 --> 01:16:39,860
En það þýðir að það fyrsta sem á listanum okkar er bara að fara til vera the fyrstur hnút.

983
01:16:39,860 --> 01:16:49,730
The mjög fyrstur hlutur verður - við þurfum ekki lengur að sjá það.

984
01:16:49,730 --> 01:16:58,710
Svo lista-> N verður tré okkar.

985
01:16:58,710 --> 01:17:02,860
lista-> Næsta er að fara að vera null.

986
01:17:02,860 --> 01:17:07,580
Og nú þegar er ekki jafn null.

987
01:17:07,580 --> 01:17:11,610
Nú er að fara að draga eitthvað úr listanum okkar.

988
01:17:11,610 --> 01:17:13,500
Svo nú er að fara að jafna lista-> N.

989
01:17:13,500 --> 01:17:20,850
Og þá er að fara að jafna lista-> N, eða lista-> Næsta.

990
01:17:20,850 --> 01:17:23,480
Þannig jafngildir ef nú gildi gildi.

991
01:17:23,480 --> 01:17:28,790
Nú getum við bætt jafnt hægri músina og vinstri bendilinn okkar

992
01:17:28,790 --> 01:17:32,900
svo lengi sem þeir eru ekki null.

993
01:17:32,900 --> 01:17:36,390
Hérna, ég held við ættum að hafa gert það í fyrsta sæti.

994
01:17:36,390 --> 01:17:44,080
Ef (nú-> hægri! = NULL)

995
01:17:44,080 --> 01:17:56,380
þá erum við að fara að setja þessi hnút í listanum okkar.

996
01:17:56,380 --> 01:17:59,290
Ef (nú-> vinstri), þetta er a lítill hluti af auka vinnu, en það er allt í lagi.

997
01:17:59,290 --> 01:18:02,690
Ef (nú-> vinstri! = NULL),

998
01:18:02,690 --> 01:18:14,310
og við erum að fara að setja vinstri í tengda listanum okkar,

999
01:18:14,310 --> 01:18:19,700
og það ætti að vera það.

1000
01:18:19,700 --> 01:18:22,670
Við iterate - svo lengi sem við höfum eitthvað á listanum okkar,

1001
01:18:22,670 --> 01:18:26,640
við höfum annan hnút til að líta á.

1002
01:18:26,640 --> 01:18:28,920
Svo við lítum á þeim hnút,

1003
01:18:28,920 --> 01:18:31,390
við fram lista okkar til the næstur einn.

1004
01:18:31,390 --> 01:18:34,060
Ef þessi hnútur er gildi sem við erum að leita að, getum við aftur satt.

1005
01:18:34,060 --> 01:18:37,640
Annars setja bæði okkar vinstri og hægri subtrees,

1006
01:18:37,640 --> 01:18:40,510
svo lengi sem þeir eru ekki null, í listanum okkar

1007
01:18:40,510 --> 01:18:43,120
þannig að við förum óhjákvæmilega yfir þeim.

1008
01:18:43,120 --> 01:18:45,160
Svo ef þeir voru ekki null,

1009
01:18:45,160 --> 01:18:47,950
Ef rót músina okkar benti á tvennt,

1010
01:18:47,950 --> 01:18:51,670
þá fyrst við tókum eitthvað út svo listinn okkar endar að vera null.

1011
01:18:51,670 --> 01:18:56,890
Og þá erum við að setja tvo hluti aftur í, svo nú er listi okkar stærð 2.

1012
01:18:56,890 --> 01:19:00,030
Þá ætlum við að lykkja aftur upp og við erum bara að fara að draga,

1013
01:19:00,030 --> 01:19:04,250
segjum, vinstri músina yfir hnút rót okkar.

1014
01:19:04,250 --> 01:19:07,730
Og það verður bara að halda að gerast, við munum á endanum lykkja yfir öllu.

1015
01:19:07,730 --> 01:19:11,280
>> Takið eftir að þetta var verulega flóknara

1016
01:19:11,280 --> 01:19:14,160
í endurkvæma lausn.

1017
01:19:14,160 --> 01:19:17,260
Og ég hef sagt mörgum sinnum

1018
01:19:17,260 --> 01:19:25,120
að endurkvæma lausn hefur yfirleitt margt sameiginlegt með endurtekningu lausn.

1019
01:19:25,120 --> 01:19:30,820
Hér er þetta nákvæmlega það sem endurkvæma lausn er að gera.

1020
01:19:30,820 --> 01:19:36,740
Eina breytingin er að í stað þess óbeint með á mánudaginn, forritið mánudaginn,

1021
01:19:36,740 --> 01:19:40,840
sem leið að halda utan um hvaða hnúður sem þú þarft samt að fara,

1022
01:19:40,840 --> 01:19:45,430
nú þú þarft að sérstaklega nota tengda listanum.

1023
01:19:45,430 --> 01:19:49,070
Í báðum tilvikum eru að halda utan um hvaða hnút enn þarf að vera heimsótt.

1024
01:19:49,070 --> 01:19:51,790
Í endurkvæma tilviki það er bara auðveldara vegna þess að stafla

1025
01:19:51,790 --> 01:19:57,100
er sett fyrir þig eins og the program stakkur.

1026
01:19:57,100 --> 01:19:59,550
Takið eftir að þetta tengist lista, það er stakkur.

1027
01:19:59,550 --> 01:20:01,580
Whatever við settum bara á mánudaginn

1028
01:20:01,580 --> 01:20:09,960
er strax það sem við erum að fara að rífa af stafla í heimsókn næst.

1029
01:20:09,960 --> 01:20:14,380
Við erum út af tími, en einhverjar spurningar?

1030
01:20:14,380 --> 01:20:23,530
[Námsmaður, óskiljanlegur]

1031
01:20:23,530 --> 01:20:27,790
[Bowden] Já. Svo ef við höfum tengt lista okkar,

1032
01:20:27,790 --> 01:20:30,150
nú er að fara að benda á þetta strákur,

1033
01:20:30,150 --> 01:20:34,690
og nú erum við bara að fara tengda listanum okkar til að einblína á þetta gaur.

1034
01:20:34,690 --> 01:20:44,200
Við erum að fara yfir á tengda lista í þeirri línu.

1035
01:20:44,200 --> 01:20:51,200
Og svo ég held að við ættum að losa tengda listanum okkar og efni

1036
01:20:51,200 --> 01:20:53,880
einu sinni en aftur satt eða ósatt, þurfum við að

1037
01:20:53,880 --> 01:20:57,360
iterate yfir tengda listanum okkar og alltaf hérna, held ég,

1038
01:20:57,360 --> 01:21:03,900
ef við nú rétt er ekki jöfn, bæta við það, svo nú viljum við að losa

1039
01:21:03,900 --> 01:21:09,600
nú vegna þess að vel var við gleymum alveg um listann? Já.

1040
01:21:09,600 --> 01:21:12,880
Svo það er það sem við viljum gera hér.

1041
01:21:12,880 --> 01:21:16,730
Hvar er bendillinn?

1042
01:21:16,730 --> 01:21:23,320
Nú var þá - við viljum að strúktúrinn lista * 10 jafngildir lista næst.

1043
01:21:23,320 --> 01:21:29,240
Free listi, listi = Temp.

1044
01:21:29,240 --> 01:21:32,820
Og í þeim tilvikum þegar við aftur satt, þurfum við að iterate

1045
01:21:32,820 --> 01:21:37,050
yfir afganginn af tengda listanum okkar fría hluti.

1046
01:21:37,050 --> 01:21:39,700
The ágætur hlutur óður í the endurkvæma lausn er frjáls hluti

1047
01:21:39,700 --> 01:21:44,930
þýðir bara pabbi factorings burt stafla sem mun gerast fyrir þig.

1048
01:21:44,930 --> 01:21:50,720
Þannig að við höfum farið frá einhverju sem er eins og 3 línur af harður-til-hugsa-um kóða

1049
01:21:50,720 --> 01:21:57,520
eitthvað sem er verulega margir fleiri harður-til-hugsa-um línum af kóða.

1050
01:21:57,520 --> 01:22:00,620
Allir fleiri spurningar?

1051
01:22:00,620 --> 01:22:08,760
Allt í lagi. Við erum góð. Bless!

1052
01:22:08,760 --> 01:22:11,760
[CS50.TV]