1
00:00:07,050 --> 00:00:09,630
[Powered by Google Translate] Hvernig myndir þú tákna alla fjölskyldu þína í tölvu?

2
00:00:10,790 --> 00:00:12,390
Við gætum einfaldlega nota lista,

3
00:00:12,390 --> 00:00:14,400
en það er ljóst stigveldi hér.

4
00:00:14,400 --> 00:00:17,110
>> Við skulum segja að við erum farin með langamma þín, Alice.

5
00:00:17,110 --> 00:00:19,030
Hún er með 2 syni, Bob

6
00:00:19,030 --> 00:00:21,310
og afi þinn, Charlie.

7
00:00:21,310 --> 00:00:23,190
Charlie á 3 börn,

8
00:00:23,190 --> 00:00:26,730
frændi þinn, Dave, frænka þín, Eva, og faðir þinn, Fred.

9
00:00:26,730 --> 00:00:28,750
Þú ert bara barn Fred.

10
00:00:28,750 --> 00:00:30,950
>> Hvers vegna vildi að skipuleggja fjölskyldu á þennan hátt

11
00:00:30,950 --> 00:00:34,010
vera betri en einföldum lista framsetning?

12
00:00:34,010 --> 00:00:36,630
Ein ástæðan er að þetta valdakerfi,

13
00:00:36,630 --> 00:00:39,660
kallað "tré, inniheldur fleiri upplýsingar en einföldum lista.

14
00:00:40,540 --> 00:00:43,520
Við þekkjum familial tengsl milli allra

15
00:00:43,520 --> 00:00:45,440
bara með því að skoða tré.

16
00:00:45,440 --> 00:00:47,250
Einnig getur það hraðað

17
00:00:47,250 --> 00:00:50,010
líta upp tími ógurlega, ef tré gögn er flokkað.

18
00:00:50,010 --> 00:00:53,850
>> Við getum ekki tekið sér það hér, en við munum sjá dæmi um þetta fljótlega.

19
00:00:53,850 --> 00:00:56,150
Hver maður er táknuð með hnút á trénu.

20
00:00:56,680 --> 00:00:58,370
Hnútar geta hafa barnið hnúður

21
00:00:58,370 --> 00:01:00,350
ásamt foreldri hnút.

22
00:01:00,350 --> 00:01:02,390
Þetta eru tæknileg hugtök,

23
00:01:02,390 --> 00:01:05,220
jafnvel þegar tré fyrir hluti auk fjölskyldna.

24
00:01:05,220 --> 00:01:07,940
Tengipunktur Alice hefur 2 börn og enga foreldra,

25
00:01:07,940 --> 00:01:11,500
meðan hnút Charlie hefur 3 börn og 1 foreldri.

26
00:01:11,500 --> 00:01:14,330
>> A blaða hnút er eitt sem er ekki börn

27
00:01:14,330 --> 00:01:16,410
að utan brún tré.

28
00:01:16,410 --> 00:01:18,520
Hæstur hnút í tré, rót hnút,

29
00:01:18,520 --> 00:01:20,240
hefur ekkert foreldri.

30
00:01:20,240 --> 00:01:23,170
>> A tvöfaldur tré er ákveðin tegund af tré,

31
00:01:23,170 --> 00:01:26,720
þar sem hver hnútur hefur í mesta lagi 2 börn.

32
00:01:26,720 --> 00:01:30,490
Hér er struct í hnút tvíundartrés í C.

33
00:01:31,560 --> 00:01:34,530
Sérhver hnútur hefur nokkur gögn í tengslum við það

34
00:01:34,530 --> 00:01:36,520
og 2 ábendingum til annarra hnúta.

35
00:01:36,520 --> 00:01:38,110
>> Í tré fjölskyldu okkar,

36
00:01:38,110 --> 00:01:40,900
í tengslum við þessa upplýsingar var nafn hvers manns.

37
00:01:40,900 --> 00:01:43,850
Hér er það int, þótt það gæti verið nokkuð.

38
00:01:44,510 --> 00:01:46,200
Eins og það kemur í ljós,

39
00:01:46,200 --> 00:01:48,990
tvöfaldur tré myndi ekki vera góð framsetning fyrir fjölskyldu,

40
00:01:48,990 --> 00:01:51,960
þar sem fólk hefur oft fleiri en 2 börn.

41
00:01:51,960 --> 00:01:53,510
>> Leit tvöfaldur tré

42
00:01:53,510 --> 00:01:56,380
er sérstök, pantaði tegund af tré tvöfaldur

43
00:01:56,380 --> 00:01:58,090
sem gerir okkur kleift að líta á gildi fljótlega.

44
00:01:58,740 --> 00:02:00,050
Þú gætir hafa tekið eftir

45
00:02:00,050 --> 00:02:02,010
að sérhver hnútur undir rót á tré

46
00:02:02,010 --> 00:02:04,620
er rót annars tré, sem kallast "subtree."

47
00:02:04,960 --> 00:02:07,090
Hér er rót af trénu er 6,

48
00:02:07,090 --> 00:02:09,860
og barnið hennar, 2, er rót a subtree.

49
00:02:09,860 --> 00:02:11,870
>> Í tvöfaldur leita tré

50
00:02:11,870 --> 00:02:15,790
öll gildin í hnút er rétt subtree

51
00:02:15,790 --> 00:02:18,690
eru meiri en verðmæti hnút á. Hér: 6.

52
00:02:18,690 --> 00:02:22,640
Jæja, gildin í vinstri subtree hnúturinn er

53
00:02:24,540 --> 00:02:26,890
er minna en verðmæti hnút á.

54
00:02:26,890 --> 00:02:28,620
Ef við þurfum að takast á afrit gildi,

55
00:02:28,620 --> 00:02:31,760
við getum breytt annaðhvort þeirra að missa misrétti,

56
00:02:31,760 --> 00:02:34,410
þýðir sömu gildi geta fallið annaðhvort vinstri eða hægri,

57
00:02:34,410 --> 00:02:37,400
svo lengi sem við erum í samræmi um það allan tímann.

58
00:02:37,400 --> 00:02:39,620
Þetta tré er tvöfaldur leita tré

59
00:02:39,620 --> 00:02:41,540
vegna þess að það fylgir þessum reglum.

60
00:02:42,320 --> 00:02:46,020
>> Þetta er hvernig það myndi líta út ef við snúið alla hnúta í C structs.

61
00:02:46,880 --> 00:02:48,410
Takið eftir að ef barnið vantar,

62
00:02:48,410 --> 00:02:50,340
bendillinn er null.

63
00:02:50,340 --> 00:02:53,270
Hvernig athuga við að sjá hvort 7 er í trénu?

64
00:02:53,270 --> 00:02:55,020
Við byrjum á rót.

65
00:02:55,020 --> 00:02:58,690
Seven er meiri en 6, þannig að ef það er í trénu, þarf það að vera til hægri.

66
00:02:59,680 --> 00:03:03,650
Þá er það minna en 8, svo það verður að vera vinstri.

67
00:03:03,650 --> 00:03:06,210
Hér höfum við fundið 7.

68
00:03:06,210 --> 00:03:08,160
Nú munum við athuga 5.

69
00:03:08,160 --> 00:03:11,500
Fimm er minna en 6, svo það verður að vera til vinstri.

70
00:03:11,500 --> 00:03:13,460
Fimm er meiri en 2,

71
00:03:13,460 --> 00:03:15,010
svo það verður að vera rétt,

72
00:03:15,010 --> 00:03:18,100
og það er líka meiri en 4, þannig að það verður að vera rétt aftur.

73
00:03:18,100 --> 00:03:20,300
Hins vegar er ekkert barn hér.

74
00:03:20,300 --> 00:03:22,000
Bendillinn er null.

75
00:03:22,000 --> 00:03:24,270
Þetta þýðir að 5 er ekki í tré okkar.

76
00:03:24,270 --> 00:03:27,250
>> Við getum leitað í tvöfaldur tré með eftirfarandi kóða:

77
00:03:28,430 --> 00:03:31,140
Á hverjum hnút, athuga við að sjá hvort við höfum fundið

78
00:03:31,140 --> 00:03:33,020
gildi sem við erum að leita að.

79
00:03:33,020 --> 00:03:35,740
Ef við finn það ekki, ákveðum við hvort það ætti að vera

80
00:03:35,740 --> 00:03:38,990
á vinstri eða hægri og athuga hvort subtree.

81
00:03:38,990 --> 00:03:41,160
Þessi lykkja heldur áfram niður tréð

82
00:03:41,160 --> 00:03:44,190
þangað til það er ekkert barn hnút annaðhvort vinstri eða hægri.

83
00:03:45,190 --> 00:03:48,600
>> Mundu að 5 var ekki í tré.

84
00:03:48,600 --> 00:03:50,460
Hvernig setja við það?

85
00:03:50,460 --> 00:03:52,370
Ferlið líkist leita.

86
00:03:52,370 --> 00:03:54,830
Við iterate niður tréð byrjar 6,

87
00:03:54,830 --> 00:03:57,040
vinstri til 2,

88
00:03:57,040 --> 00:03:59,140
rétt til 4,

89
00:03:59,140 --> 00:04:02,500
og aftur til hægri, en 4 er ekki barn á þessu megin.

90
00:04:02,500 --> 00:04:06,090
Þetta verður ný staða fyrir 5,

91
00:04:06,090 --> 00:04:08,500
og það byrjar með engin börn.

92
00:04:09,020 --> 00:04:12,220
>> Hversu hratt er rekstur á tvöfaldur leita tré?

93
00:04:12,220 --> 00:04:15,410
Mundu að Bigohnotation leitast við að veita að efri.

94
00:04:15,410 --> 00:04:17,390
Í versta tilfelli,

95
00:04:17,390 --> 00:04:19,480
tré okkar gæti einfaldlega verið tengda listanum

96
00:04:19,480 --> 00:04:22,220
þýðir að innsetningu, eyðingu, og leita

97
00:04:22,220 --> 00:04:25,380
gæti tekið tíma hlutfalli við fjölda hnúta í trénu.

98
00:04:25,380 --> 00:04:27,380
Þetta er O (n).

99
00:04:27,380 --> 00:04:30,690
>> Til dæmis er eftirfarandi er gild tvöfaldur leita tré.

100
00:04:31,850 --> 00:04:34,020
Hins vegar, ef við reynum að finna 9,

101
00:04:34,020 --> 00:04:36,760
við verðum að fara yfir hverjum hnút.

102
00:04:36,760 --> 00:04:39,120
Það er ekkert betra en tengda listanum.

103
00:04:39,120 --> 00:04:41,410
Helst myndum við vilja hverjum hnút

104
00:04:41,410 --> 00:04:44,120
af tvöfaldur leita tré okkar að hafa 2 börn.

105
00:04:44,120 --> 00:04:46,370
This vegur, innsetningu, eyðingu og leita

106
00:04:46,370 --> 00:04:50,190
myndi taka, í versta falli, O (log n) tíma.

107
00:04:50,190 --> 00:04:52,470
The tré undan gæti verið jafnvægi,

108
00:04:52,470 --> 00:04:54,140
eins og þetta.

109
00:04:54,140 --> 00:04:57,980
Nú, að horfa upp hvaða gildi tekur í mesta lagi 3 skref.

110
00:04:57,980 --> 00:04:59,460
Þetta tré er í jafnvægi,

111
00:04:59,460 --> 00:05:01,190
merking sem hefur lágmarks dýpt

112
00:05:01,190 --> 00:05:03,680
miðað við fjölda hnúta.

113
00:05:03,680 --> 00:05:06,300
>> Útlit fyrir gildi í jafnvægi tvöfaldur leita tré

114
00:05:06,300 --> 00:05:09,540
er svipað og tvöfaldur leit á raðað fylki.

115
00:05:09,540 --> 00:05:12,290
Í staðreynd, ef við þurfum ekki að setja inn eða eyða hlutum,

116
00:05:12,290 --> 00:05:15,150
þeir haga sér nákvæmlega á sama hátt.

117
00:05:15,150 --> 00:05:17,600
En tré uppbygging er betri

118
00:05:17,600 --> 00:05:19,530
til ísetningar meðhöndlun og úrfellingum

119
00:05:20,360 --> 00:05:22,670
>> Ég heiti Bannus Van der Kloot.

120
00:05:22,670 --> 00:05:24,030
Þetta er CS50.