1
00:00:07,050 --> 00:00:09,630
[Powered by Google Translate] Hvordan vil du repræsentere alle dine familiemedlemmer i en computer?

2
00:00:10,790 --> 00:00:12,390
Vi kunne blot bruge en liste,

3
00:00:12,390 --> 00:00:14,400
men der er et klart hierarki her.

4
00:00:14,400 --> 00:00:17,110
>> Lad os sige, at vi er begyndt med din oldemor, Alice.

5
00:00:17,110 --> 00:00:19,030
Hun har 2 sønner, Bob

6
00:00:19,030 --> 00:00:21,310
og din bedstefar, Charlie.

7
00:00:21,310 --> 00:00:23,190
Charlie har 3 børn,

8
00:00:23,190 --> 00:00:26,730
Deres onkel, Dave, din tante, Eva, og din far, Fred.

9
00:00:26,730 --> 00:00:28,750
Du er Fred eneste barn.

10
00:00:28,750 --> 00:00:30,950
>> Hvorfor skulle organisere dine familiemedlemmer på denne måde

11
00:00:30,950 --> 00:00:34,010
være bedre end den simple liste repræsentation?

12
00:00:34,010 --> 00:00:36,630
En grund er, at denne hierarkisk struktur,

13
00:00:36,630 --> 00:00:39,660
kaldes en 'træ', indeholder mere information end en simpel liste.

14
00:00:40,540 --> 00:00:43,520
Vi kender slægtskab mellem alle

15
00:00:43,520 --> 00:00:45,440
blot ved at undersøge træet.

16
00:00:45,440 --> 00:00:47,250
Det kan også fremskynde

17
00:00:47,250 --> 00:00:50,010
look-up tid gevaldigt, hvis træet data er sorteret.

18
00:00:50,010 --> 00:00:53,850
>> Vi kan ikke drage fordel af det her, men vi vil se et eksempel på dette snart.

19
00:00:53,850 --> 00:00:56,150
Hver person er repræsenteret ved et knudepunkt i træet.

20
00:00:56,680 --> 00:00:58,370
Nodes kan have barn noder

21
00:00:58,370 --> 00:01:00,350
samt en forælder node.

22
00:01:00,350 --> 00:01:02,390
Disse er de tekniske udtryk,

23
00:01:02,390 --> 00:01:05,220
selv ved brug af træer for ting udover familier.

24
00:01:05,220 --> 00:01:07,940
Alices knudepunkt har 2 børn og ingen forældre,

25
00:01:07,940 --> 00:01:11,500
mens Charlie knudepunkt har 3 børn og 1 forælder.

26
00:01:11,500 --> 00:01:14,330
>> Et blad node er en, der ikke har nogen børn

27
00:01:14,330 --> 00:01:16,410
på den udvendige kant af træet.

28
00:01:16,410 --> 00:01:18,520
Den øverste node i træet, roden node,

29
00:01:18,520 --> 00:01:20,240
har ingen forælder.

30
00:01:20,240 --> 00:01:23,170
>> Et binært træ er en specifik type af træ,

31
00:01:23,170 --> 00:01:26,720
hvor hver knude har, højst 2 børn.

32
00:01:26,720 --> 00:01:30,490
Her er struct af et knudepunkt i et binært træ i C.

33
00:01:31,560 --> 00:01:34,530
Hvert knudepunkt har nogle data i forbindelse med det

34
00:01:34,530 --> 00:01:36,520
og 2 henvisninger til andre knudepunkter.

35
00:01:36,520 --> 00:01:38,110
>> I vores stamtræ,

36
00:01:38,110 --> 00:01:40,900
de tilhørende data var hver persons navn.

37
00:01:40,900 --> 00:01:43,850
Her er det en int, selvom det kunne være hvad som helst.

38
00:01:44,510 --> 00:01:46,200
Da det viser sig,

39
00:01:46,200 --> 00:01:48,990
et binært træ vil ikke være en god repræsentation for en familie,

40
00:01:48,990 --> 00:01:51,960
da folk ofte har mere end 2 børn.

41
00:01:51,960 --> 00:01:53,510
>> En binær søgning tree

42
00:01:53,510 --> 00:01:56,380
er en særlig, ordnet type binært træ

43
00:01:56,380 --> 00:01:58,090
der giver os mulighed for at se på værdierne hurtigt.

44
00:01:58,740 --> 00:02:00,050
Du har måske lagt mærke til

45
00:02:00,050 --> 00:02:02,010
at hver node under roden af ​​et træ

46
00:02:02,010 --> 00:02:04,620
er roden af ​​et andet træ, en såkaldt »undertræ. '

47
00:02:04,960 --> 00:02:07,090
Her roden af ​​træet er 6,

48
00:02:07,090 --> 00:02:09,860
og dens barn, 2, er roden til et undertræ.

49
00:02:09,860 --> 00:02:11,870
>> I en binær søgning træ

50
00:02:11,870 --> 00:02:15,790
alle værdier af en knude er ret undertræ

51
00:02:15,790 --> 00:02:18,690
er større end knudepunktets værdi. Her: 6.

52
00:02:18,690 --> 00:02:22,640
Nå, værdierne i et knudepunkt venstre undertræ

53
00:02:24,540 --> 00:02:26,890
er mindre end knudepunktets værdi.

54
00:02:26,890 --> 00:02:28,620
Hvis vi er nødt til at håndtere dublerede værdier,

55
00:02:28,620 --> 00:02:31,760
vi kan ændre enten af ​​dem til en løs ulighed,

56
00:02:31,760 --> 00:02:34,410
betyder identiske værdier kan falde enten på venstre eller højre,

57
00:02:34,410 --> 00:02:37,400
så længe vi er konsekvente over det hele.

58
00:02:37,400 --> 00:02:39,620
Dette træ er et binært søgetræ

59
00:02:39,620 --> 00:02:41,540
fordi det følger disse regler.

60
00:02:42,320 --> 00:02:46,020
>> Dette er, hvordan det ville se ud, hvis vi vendte alle de noder til C struct.

61
00:02:46,880 --> 00:02:48,410
Bemærk, at hvis et barn mangler,

62
00:02:48,410 --> 00:02:50,340
markøren er nul.

63
00:02:50,340 --> 00:02:53,270
Hvordan tjekker vi for at se, hvis 7 er i træet?

64
00:02:53,270 --> 00:02:55,020
Vi starter ved roden.

65
00:02:55,020 --> 00:02:58,690
Syv er større end 6, så hvis det er i træet, skal det være til højre.

66
00:02:59,680 --> 00:03:03,650
Derefter er det mindre end 8, og det må være op.

67
00:03:03,650 --> 00:03:06,210
Her har vi fundet 7.

68
00:03:06,210 --> 00:03:08,160
Nu vil vi kontrollere for 5.

69
00:03:08,160 --> 00:03:11,500
Fem er mindre end 6, så det må være til venstre.

70
00:03:11,500 --> 00:03:13,460
Fem er større end 2,

71
00:03:13,460 --> 00:03:15,010
så det må være rigtigt,

72
00:03:15,010 --> 00:03:18,100
og det er også større end 4, så det må være rigtigt igen.

73
00:03:18,100 --> 00:03:20,300
Der er imidlertid ingen børn her.

74
00:03:20,300 --> 00:03:22,000
Markøren er null.

75
00:03:22,000 --> 00:03:24,270
Dette betyder, at 5 ikke er i vores træ.

76
00:03:24,270 --> 00:03:27,250
>> Vi kan søge det binære træ med følgende kode:

77
00:03:28,430 --> 00:03:31,140
Ved hver node, tjekker vi for at se, om vi har fundet

78
00:03:31,140 --> 00:03:33,020
den værdi, vi er på udkig efter.

79
00:03:33,020 --> 00:03:35,740
Hvis vi ikke finder det, vi afgøre, om det skal være

80
00:03:35,740 --> 00:03:38,990
på venstre eller højre, og kontroller, at undertræ.

81
00:03:38,990 --> 00:03:41,160
Denne løkke vil fortsætte ned i træet

82
00:03:41,160 --> 00:03:44,190
indtil der ikke er barneknudepunkt på enten venstre eller højre.

83
00:03:45,190 --> 00:03:48,600
>> Husk, at 5 ikke var i træet.

84
00:03:48,600 --> 00:03:50,460
Hvordan kan vi indsætter det?

85
00:03:50,460 --> 00:03:52,370
Processen ligner søge.

86
00:03:52,370 --> 00:03:54,830
Vi gentage ned i træet startende fra 6,

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

88
00:03:57,040 --> 00:03:59,140
ret til 4,

89
00:03:59,140 --> 00:04:02,500
og til højre igen, men 4 har intet barn på denne side.

90
00:04:02,500 --> 00:04:06,090
Dette vil være den nye position for 5,

91
00:04:06,090 --> 00:04:08,500
og det vil begynde med ingen børn.

92
00:04:09,020 --> 00:04:12,220
>> Hvor hurtigt er operationer på et binært søgetræ?

93
00:04:12,220 --> 00:04:15,410
Husk, at Bigohnotation søger at tilvejebringe en øvre grænse.

94
00:04:15,410 --> 00:04:17,390
I værste fald,

95
00:04:17,390 --> 00:04:19,480
vores træ kunne simpelthen være en sammenkædet liste

96
00:04:19,480 --> 00:04:22,220
hvilket betyder, at indsættelse, sletning og søgning

97
00:04:22,220 --> 00:04:25,380
kunne tage tid er proportional med antallet af knuder i træet.

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

99
00:04:27,380 --> 00:04:30,690
>> For eksempel er følgende en gyldig binær søgning træ.

100
00:04:31,850 --> 00:04:34,020
Men hvis vi forsøger at finde 9,

101
00:04:34,020 --> 00:04:36,760
Vi er nødt til at krydse hvert knudepunkt.

102
00:04:36,760 --> 00:04:39,120
Det er ikke bedre end en linket liste.

103
00:04:39,120 --> 00:04:41,410
Ideelt set ville vi ønsker hver node

104
00:04:41,410 --> 00:04:44,120
af vores binære søgetræ at have 2 børn.

105
00:04:44,120 --> 00:04:46,370
Denne måde, insertion, deletion og søgning

106
00:04:46,370 --> 00:04:50,190
ville tage i værste fald O (log n) tid.

107
00:04:50,190 --> 00:04:52,470
Træet fra før kunne være mere afbalanceret,

108
00:04:52,470 --> 00:04:54,140
som denne.

109
00:04:54,140 --> 00:04:57,980
Nu ser op nogen værdi tager, højst 3 trin.

110
00:04:57,980 --> 00:04:59,460
Dette træ er afbalanceret,

111
00:04:59,460 --> 00:05:01,190
forstand, at den har en minimal dybde

112
00:05:01,190 --> 00:05:03,680
i forhold til antallet af knudepunkter.

113
00:05:03,680 --> 00:05:06,300
>> Leder du efter en værdi i en balanceret binært søgetræ

114
00:05:06,300 --> 00:05:09,540
ligner binær søgning på en ordnet array.

115
00:05:09,540 --> 00:05:12,290
Faktisk, hvis vi ikke behøver at indsætte eller slette elementer

116
00:05:12,290 --> 00:05:15,150
de opfører sig nøjagtig samme måde.

117
00:05:15,150 --> 00:05:17,600
Men en træstruktur er bedre

118
00:05:17,600 --> 00:05:19,530
for håndtering indsætninger og sletninger

119
00:05:20,360 --> 00:05:22,670
>> Mit navn er Bannus Van der Kloot.

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