1
00:00:07,050 --> 00:00:09,630
[Powered by Google Translate] Si do të përfaqësojë të gjithë anëtarët e familjes tuaj në një kompjuter?

2
00:00:10,790 --> 00:00:12,390
Ne thjesht mund të përdorni një listë,

3
00:00:12,390 --> 00:00:14,400
por ka një hierarki të qartë këtu.

4
00:00:14,400 --> 00:00:17,110
>> Le të thonë se ne jemi duke filluar me gjyshen tuaj të madhe-, Alice.

5
00:00:17,110 --> 00:00:19,030
Ajo ka 2 djem, Bob

6
00:00:19,030 --> 00:00:21,310
dhe gjyshi juaj, Charlie.

7
00:00:21,310 --> 00:00:23,190
Charlie ka 3 fëmijë,

8
00:00:23,190 --> 00:00:26,730
xhaxhai juaj, Dave, halla juaj, Eva, dhe babai yt, Fred.

9
00:00:26,730 --> 00:00:28,750
Ju jeni fëmijë i vetëm Fred s.

10
00:00:28,750 --> 00:00:30,950
>> Pse do të organizimit anëtarët e familjes tuaj në këtë mënyrë

11
00:00:30,950 --> 00:00:34,010
të jetë më mirë se përfaqësimi listë e thjeshtë?

12
00:00:34,010 --> 00:00:36,630
Një arsye është se kjo strukturë hierarkike,

13
00:00:36,630 --> 00:00:39,660
quajtur një 'pemë', përmban informacione më shumë se një listë të thjeshtë.

14
00:00:40,540 --> 00:00:43,520
Ne e dimë marrëdhëniet familjare ndërmjet të gjithë

15
00:00:43,520 --> 00:00:45,440
vetëm me shqyrtimin e pemë.

16
00:00:45,440 --> 00:00:47,250
Gjithashtu, ajo mund të përshpejtojë

17
00:00:47,250 --> 00:00:50,010
look-up kohë të jashtëzakonshme, nëse të dhënat pemë është e renditura.

18
00:00:50,010 --> 00:00:53,850
>> Ne nuk mund të përfitojnë nga se këtu, por ne do të shohim një shembull të kësaj së shpejti.

19
00:00:53,850 --> 00:00:56,150
Çdo person është i përfaqësuar nga një nyje në pemë.

20
00:00:56,680 --> 00:00:58,370
Nyje nyje mund të ketë fëmijë

21
00:00:58,370 --> 00:01:00,350
si dhe një nyje mëmë.

22
00:01:00,350 --> 00:01:02,390
Këto janë kushtet teknike,

23
00:01:02,390 --> 00:01:05,220
edhe kur duke përdorur pemë për gjëra përveç familjeve.

24
00:01:05,220 --> 00:01:07,940
Nyja Alice ka 2 fëmijë dhe jo prindërit,

25
00:01:07,940 --> 00:01:11,500
ndërsa nyja Charlie ka 3 fëmijë dhe 1 prind.

26
00:01:11,500 --> 00:01:14,330
>> Një nyjë është një fletë që nuk kanë ndonjë fëmijë

27
00:01:14,330 --> 00:01:16,410
në skajin e jashtme e pema.

28
00:01:16,410 --> 00:01:18,520
Nyja larti e pemës, nyja rrënjë,

29
00:01:18,520 --> 00:01:20,240
nuk ka prind.

30
00:01:20,240 --> 00:01:23,170
>> Një pemë binare është një lloj specifik i pemës,

31
00:01:23,170 --> 00:01:26,720
në të cilën çdo nyje ka, më së shumti, 2 fëmijë.

32
00:01:26,720 --> 00:01:30,490
Këtu është struct e një nyje e një pemë binare në C.

33
00:01:31,560 --> 00:01:34,530
Çdo nyje ka disa të dhëna që lidhen me të

34
00:01:34,530 --> 00:01:36,520
dhe 2 pointers në nyjet e tjera.

35
00:01:36,520 --> 00:01:38,110
>> Në pemën tonë familjare,

36
00:01:38,110 --> 00:01:40,900
të dhënat që lidhen ishte emri i secilit person.

37
00:01:40,900 --> 00:01:43,850
Këtu ajo është një int, edhe pse ajo mund të jetë çdo gjë.

38
00:01:44,510 --> 00:01:46,200
Siç rezulton,

39
00:01:46,200 --> 00:01:48,990
një pemë binare nuk do të jetë një përfaqësim të mirë për një familje,

40
00:01:48,990 --> 00:01:51,960
që njerëzit shpesh kanë më shumë se 2 fëmijë.

41
00:01:51,960 --> 00:01:53,510
>> Një kërkim binar pemë

42
00:01:53,510 --> 00:01:56,380
është një e veçantë, lloji i urdhëroi pemë binare

43
00:01:56,380 --> 00:01:58,090
që na lejon të shikojmë në vlerat shpejt.

44
00:01:58,740 --> 00:02:00,050
Ju mund të keni vënë re

45
00:02:00,050 --> 00:02:02,010
se çdo nyje nën rrënjët e një pemë

46
00:02:02,010 --> 00:02:04,620
është rrënja e pemës tjetër, i quajtur një 'subtree.'

47
00:02:04,960 --> 00:02:07,090
Këtu, rrënja e pemës është 6,

48
00:02:07,090 --> 00:02:09,860
dhe fëmijë saj, 2, është rrënja e një subtree.

49
00:02:09,860 --> 00:02:11,870
>> Në një pemë binare e kërkimit

50
00:02:11,870 --> 00:02:15,790
të gjitha vlerat e një nyje e drejtë subtree

51
00:02:15,790 --> 00:02:18,690
janë më të mëdha se vlera nyjen së. Këtu: 6.

52
00:02:18,690 --> 00:02:22,640
E pra, vlerat në subtree majtë një nyje e

53
00:02:24,540 --> 00:02:26,890
janë më pak se vlera nyjen së.

54
00:02:26,890 --> 00:02:28,620
Nëse ne kemi nevojë për të trajtuar vlerat kopjuar,

55
00:02:28,620 --> 00:02:31,760
Ne mund të ndryshojë ose të atyre me një pabarazi të lirshme,

56
00:02:31,760 --> 00:02:34,410
që do të thotë vlera identike mund të bjerë as në të majtë apo të djathtë,

57
00:02:34,410 --> 00:02:37,400
për aq kohë sa ne jemi konsistente në lidhje me të gjithë.

58
00:02:37,400 --> 00:02:39,620
Kjo pemë është një pemë binare kërko

59
00:02:39,620 --> 00:02:41,540
për shkak se ajo ndjek këto rregulla.

60
00:02:42,320 --> 00:02:46,020
>> Kjo është se si do të dukej në qoftë se ne u kthye të gjitha nyjet në structs C.

61
00:02:46,880 --> 00:02:48,410
Vini re se në qoftë se një fëmijë është zhdukur,

62
00:02:48,410 --> 00:02:50,340
tregues është i pavlefshëm.

63
00:02:50,340 --> 00:02:53,270
Si nuk kemi të kontrolloni për të parë nëse është i 7 në pemë?

64
00:02:53,270 --> 00:02:55,020
Ne të fillojë në rrënjë.

65
00:02:55,020 --> 00:02:58,690
Shtatë është më e madhe se 6, kështu që nëse kjo është në pemë, ajo duhet të jetë në të djathtë.

66
00:02:59,680 --> 00:03:03,650
Pastaj, ajo është më pak se 8, kështu që ajo duhet të lihet.

67
00:03:03,650 --> 00:03:06,210
Këtu, ne kemi gjetur 7.

68
00:03:06,210 --> 00:03:08,160
Tani, ne do të kontrolloni për 5.

69
00:03:08,160 --> 00:03:11,500
Pesë është më pak se 6, kështu që ajo duhet të jetë në të majtë.

70
00:03:11,500 --> 00:03:13,460
Pesë është më e madhe se 2,

71
00:03:13,460 --> 00:03:15,010
kështu që ajo duhet të jetë e drejtë,

72
00:03:15,010 --> 00:03:18,100
dhe kjo është edhe më e madhe se 4, kështu që ajo duhet të jetë e drejtë përsëri.

73
00:03:18,100 --> 00:03:20,300
Megjithatë, nuk ka fëmijë këtu.

74
00:03:20,300 --> 00:03:22,000
Tregues është i pavlefshëm.

75
00:03:22,000 --> 00:03:24,270
Kjo do të thotë se 5 nuk është në pemë tonë.

76
00:03:24,270 --> 00:03:27,250
>> Ne mund të kërkoni në pemë binare me kodin e mëposhtëm:

77
00:03:28,430 --> 00:03:31,140
Në çdo nyje, ne kontrolloni për të parë nëse ne kemi gjetur

78
00:03:31,140 --> 00:03:33,020
vlera ne jemi duke kërkuar për të.

79
00:03:33,020 --> 00:03:35,740
Nëse ne nuk e gjeni atë, ne të përcaktuar nëse ajo duhet të jetë

80
00:03:35,740 --> 00:03:38,990
në dhe të majtë apo të djathtë të kontrolloni se subtree.

81
00:03:38,990 --> 00:03:41,160
Kjo lak do të vazhdojë poshtë pemë

82
00:03:41,160 --> 00:03:44,190
derisa nuk ka asnjë nyjë fëmijë në të dyja të majtë apo të djathtë.

83
00:03:45,190 --> 00:03:48,600
>> Mos harroni se 5 nuk ishte në pemë.

84
00:03:48,600 --> 00:03:50,460
Si nuk kemi futur atë?

85
00:03:50,460 --> 00:03:52,370
Procesi duket e ngjashme për të kërkuar.

86
00:03:52,370 --> 00:03:54,830
Ne iterate poshtë pemë duke filluar nga 6,

87
00:03:54,830 --> 00:03:57,040
e majta në të 2,

88
00:03:57,040 --> 00:03:59,140
drejtën për 4,

89
00:03:59,140 --> 00:04:02,500
dhe të drejtën përsëri, por 4 nuk ka fëmijë në këtë anë.

90
00:04:02,500 --> 00:04:06,090
Kjo do të jetë pozita e re për 5,

91
00:04:06,090 --> 00:04:08,500
dhe ajo do të fillojë me pa fëmijë.

92
00:04:09,020 --> 00:04:12,220
>> Sa shpejt janë operacione në një pemë binare e kërkimit?

93
00:04:12,220 --> 00:04:15,410
Mos harroni se Bigohnotation kërkon të sigurojë një lidhur sipërme.

94
00:04:15,410 --> 00:04:17,390
Në rastin më të keq,

95
00:04:17,390 --> 00:04:19,480
pema jonë mund të jetë thjesht një listë e lidhur

96
00:04:19,480 --> 00:04:22,220
thotë se futje, fshirje, dhe kërko

97
00:04:22,220 --> 00:04:25,380
mund të marrë kohë proporcional me numrin e nyjeve në pemë.

98
00:04:25,380 --> 00:04:27,380
Kjo është O (n).

99
00:04:27,380 --> 00:04:30,690
>> Për shembull, në vijim është një vlefshëm kërkimit binar pemë.

100
00:04:31,850 --> 00:04:34,020
Megjithatë, nëse ne përpiqemi të gjejmë 9,

101
00:04:34,020 --> 00:04:36,760
ne duhet të kaloj çdo nyje.

102
00:04:36,760 --> 00:04:39,120
Ajo nuk është më e mirë se një listë e lidhur.

103
00:04:39,120 --> 00:04:41,410
Teorikisht, ne do të duan çdo nyje

104
00:04:41,410 --> 00:04:44,120
e pemë binare e kërkimit tonë që të ketë 2 fëmijë.

105
00:04:44,120 --> 00:04:46,370
Në këtë mënyrë, futje, fshirje dhe kërko

106
00:04:46,370 --> 00:04:50,190
do të marrë, në më të keq, O (log n) kohë.

107
00:04:50,190 --> 00:04:52,470
Pema e para mund të jetë më e balancuar,

108
00:04:52,470 --> 00:04:54,140
si kjo.

109
00:04:54,140 --> 00:04:57,980
Tani, duke kërkuar deri ndonjë vlerë merr, më së shumti, 3 hapa.

110
00:04:57,980 --> 00:04:59,460
Kjo pemë është i balancuar,

111
00:04:59,460 --> 00:05:01,190
do të thotë se është ka një thellësi minimale

112
00:05:01,190 --> 00:05:03,680
në lidhje me numrin e nyjeve.

113
00:05:03,680 --> 00:05:06,300
>> Duke kërkuar për një vlerë në një pemë binare e kërkimit të ekuilibruar

114
00:05:06,300 --> 00:05:09,540
është i ngjashëm me kërkimin binar në një grup të renditura.

115
00:05:09,540 --> 00:05:12,290
Në fakt, në qoftë se ne nuk kemi nevojë për të futur apo fshij artikuj,

116
00:05:12,290 --> 00:05:15,150
ata sillen pikërisht të njëjtën mënyrë.

117
00:05:15,150 --> 00:05:17,600
Megjithatë, një strukturë pemë është më e mirë

118
00:05:17,600 --> 00:05:19,530
për insertions trajtimin dhe fshirjeve

119
00:05:20,360 --> 00:05:22,670
>> Emri im është Bannus Van der Kloot.

120
00:05:22,670 --> 00:05:24,030
Kjo është CS50.