1
00:00:07,050 --> 00:00:09,630
[Powered by Google Translate] Hur skulle du representerar alla dina familjemedlemmar i en dator?

2
00:00:10,790 --> 00:00:12,390
Vi kan helt enkelt använda en lista,

3
00:00:12,390 --> 00:00:14,400
men det finns en tydlig hierarki här.

4
00:00:14,400 --> 00:00:17,110
>> Låt oss säga att vi börjar med din gammelmormor, Alice.

5
00:00:17,110 --> 00:00:19,030
Hon har 2 söner, Bob

6
00:00:19,030 --> 00:00:21,310
och din farfar, Charlie.

7
00:00:21,310 --> 00:00:23,190
Charlie har 3 barn,

8
00:00:23,190 --> 00:00:26,730
din farbror, Dave, din faster, Eve, och din far, Fred.

9
00:00:26,730 --> 00:00:28,750
Du är Freds enda barn.

10
00:00:28,750 --> 00:00:30,950
>> Varför skulle organisera dina familjemedlemmar på detta sätt

11
00:00:30,950 --> 00:00:34,010
vara bättre än den enkla listan representation?

12
00:00:34,010 --> 00:00:36,630
Ett skäl är att denna hierarkiska struktur,

13
00:00:36,630 --> 00:00:39,660
kallas "träd", innehåller mer information än en enkel lista.

14
00:00:40,540 --> 00:00:43,520
Vi vet att släktskap mellan alla

15
00:00:43,520 --> 00:00:45,440
bara genom att undersöka trädet.

16
00:00:45,440 --> 00:00:47,250
Det kan också påskynda

17
00:00:47,250 --> 00:00:50,010
look-up tid enormt, om träd data sorteras.

18
00:00:50,010 --> 00:00:53,850
>> Vi kan inte dra nytta av det här, men vi får se ett exempel på detta snart.

19
00:00:53,850 --> 00:00:56,150
Varje person representeras av en nod i trädet.

20
00:00:56,680 --> 00:00:58,370
Noder kan ha underordnade noder

21
00:00:58,370 --> 00:01:00,350
liksom en överordnad nod.

22
00:01:00,350 --> 00:01:02,390
Dessa är de tekniska termer,

23
00:01:02,390 --> 00:01:05,220
även om man använder träd för saker förutom familjer.

24
00:01:05,220 --> 00:01:07,940
Alice nod har 2 barn och inga föräldrar,

25
00:01:07,940 --> 00:01:11,500
medan Charlies nod har 3 barn och 1 förälder.

26
00:01:11,500 --> 00:01:14,330
>> Ett löv nod är en som inte har några barn

27
00:01:14,330 --> 00:01:16,410
på ytterkanten av trädet.

28
00:01:16,410 --> 00:01:18,520
Den översta nod i trädet, rotnoden,

29
00:01:18,520 --> 00:01:20,240
har ingen förälder.

30
00:01:20,240 --> 00:01:23,170
>> En binär träd är en specifik typ av träd,

31
00:01:23,170 --> 00:01:26,720
i vilket varje nod har, på sin höjd 2 barn.

32
00:01:26,720 --> 00:01:30,490
Här är struct av en nod i ett binärt träd i C.

33
00:01:31,560 --> 00:01:34,530
Varje nod har en del data i samband med det

34
00:01:34,530 --> 00:01:36,520
och 2 pekare till andra noder.

35
00:01:36,520 --> 00:01:38,110
>> I vårt släktträd,

36
00:01:38,110 --> 00:01:40,900
tillhörande data var varje persons namn.

37
00:01:40,900 --> 00:01:43,850
Här är det en int, men det kan vara vad som helst.

38
00:01:44,510 --> 00:01:46,200
Som det visar sig,

39
00:01:46,200 --> 00:01:48,990
ett binärt träd skulle inte vara en god representation för en familj,

40
00:01:48,990 --> 00:01:51,960
eftersom människor har ofta mer än 2 barn.

41
00:01:51,960 --> 00:01:53,510
>> En binär sökträdet

42
00:01:53,510 --> 00:01:56,380
är en speciell, ordnad typ av binära träd

43
00:01:56,380 --> 00:01:58,090
som tillåter oss att titta på värden snabbt.

44
00:01:58,740 --> 00:02:00,050
Du kanske har märkt

45
00:02:00,050 --> 00:02:02,010
att varje nod under roten av ett träd

46
00:02:02,010 --> 00:02:04,620
är roten till ett annat träd, en så kallad "underträd."

47
00:02:04,960 --> 00:02:07,090
Här, är roten av trädet 6,

48
00:02:07,090 --> 00:02:09,860
och dess barn, 2, är roten till ett underträd.

49
00:02:09,860 --> 00:02:11,870
>> I ett binärt sökträd

50
00:02:11,870 --> 00:02:15,790
alla värden i en nod rätt underträd

51
00:02:15,790 --> 00:02:18,690
är större än nodens värde. Här: 6.

52
00:02:18,690 --> 00:02:22,640
Tja, värdena i en nod vänstra underträd

53
00:02:24,540 --> 00:02:26,890
är mindre än nodens värde.

54
00:02:26,890 --> 00:02:28,620
Om vi ​​behöver för att hantera dubbletter,

55
00:02:28,620 --> 00:02:31,760
vi kan ändra någon av dem till en lös ojämlikhet,

56
00:02:31,760 --> 00:02:34,410
betyder identiska värden kan falla antingen på vänster eller höger,

57
00:02:34,410 --> 00:02:37,400
så länge vi är konsekventa om det hela.

58
00:02:37,400 --> 00:02:39,620
Detta träd är ett binärt sökträd

59
00:02:39,620 --> 00:02:41,540
eftersom den följer dessa regler.

60
00:02:42,320 --> 00:02:46,020
>> Detta är hur det skulle se ut om vi vände alla noder i C-structs.

61
00:02:46,880 --> 00:02:48,410
Notera att om ett barn saknas,

62
00:02:48,410 --> 00:02:50,340
pekaren är null.

63
00:02:50,340 --> 00:02:53,270
Hur kontrollerar vi att se om 7 finns i trädet?

64
00:02:53,270 --> 00:02:55,020
Vi börjar vid roten.

65
00:02:55,020 --> 00:02:58,690
Sju är större än 6, så om det är i trädet, måste det vara till höger.

66
00:02:59,680 --> 00:03:03,650
Då är det mindre än 8, så det måste vara kvar.

67
00:03:03,650 --> 00:03:06,210
Här, har vi funnit 7.

68
00:03:06,210 --> 00:03:08,160
Nu ska vi leta efter 5.

69
00:03:08,160 --> 00:03:11,500
Fem är mindre än 6, så det måste vara till vänster.

70
00:03:11,500 --> 00:03:13,460
Fem är större än 2,

71
00:03:13,460 --> 00:03:15,010
så det måste vara rätt,

72
00:03:15,010 --> 00:03:18,100
och det är också större än 4, så det måste vara rätt igen.

73
00:03:18,100 --> 00:03:20,300
Det finns dock inget barn här.

74
00:03:20,300 --> 00:03:22,000
Pekaren är null.

75
00:03:22,000 --> 00:03:24,270
Detta innebär att 5 är inte i vårt träd.

76
00:03:24,270 --> 00:03:27,250
>> Vi kan söka det binära trädet med följande kod:

77
00:03:28,430 --> 00:03:31,140
Vid varje nod kontrollerar vi att se om vi har hittat

78
00:03:31,140 --> 00:03:33,020
det värde vi söker.

79
00:03:33,020 --> 00:03:35,740
Om vi ​​inte hittar den, avgör vi om det skulle vara

80
00:03:35,740 --> 00:03:38,990
på vänster eller höger och kontrollera att underträd.

81
00:03:38,990 --> 00:03:41,160
Denna slinga fortsätter ned trädet

82
00:03:41,160 --> 00:03:44,190
tills ingen barnnod på antingen vänster eller höger.

83
00:03:45,190 --> 00:03:48,600
>> Kom ihåg att 5 inte var i trädet.

84
00:03:48,600 --> 00:03:50,460
Hur sätter vi den?

85
00:03:50,460 --> 00:03:52,370
Processen liknar söka.

86
00:03:52,370 --> 00:03:54,830
Vi upprepa ned trädet från 6,

87
00:03:54,830 --> 00:03:57,040
vänster till 2,

88
00:03:57,040 --> 00:03:59,140
rätt till 4,

89
00:03:59,140 --> 00:04:02,500
och höger igen, men 4 har inget barn på denna sida.

90
00:04:02,500 --> 00:04:06,090
Detta kommer att vara den nya positionen för 5,

91
00:04:06,090 --> 00:04:08,500
och det kommer att börja med inga barn.

92
00:04:09,020 --> 00:04:12,220
>> Hur snabb är operationer på ett binärt sökträd?

93
00:04:12,220 --> 00:04:15,410
Kom ihåg att Bigohnotation söker tillhandahålla en övre gräns.

94
00:04:15,410 --> 00:04:17,390
I värsta fall,

95
00:04:17,390 --> 00:04:19,480
vår träd kan helt enkelt vara en länkad lista

96
00:04:19,480 --> 00:04:22,220
vilket innebär att infogning, utelämning, och sök

97
00:04:22,220 --> 00:04:25,380
kan ta tid proportionell mot antalet noder i trädet.

98
00:04:25,380 --> 00:04:27,380
Detta är O (n).

99
00:04:27,380 --> 00:04:30,690
>> Till exempel är följande en giltig binärt sökträd.

100
00:04:31,850 --> 00:04:34,020
Men om vi försöker hitta 9,

101
00:04:34,020 --> 00:04:36,760
vi måste passera varje nod.

102
00:04:36,760 --> 00:04:39,120
Det är inte bättre än en länkad lista.

103
00:04:39,120 --> 00:04:41,410
Helst skulle vi vilja varje nod

104
00:04:41,410 --> 00:04:44,120
vår binära sökträd att ha 2 barn.

105
00:04:44,120 --> 00:04:46,370
På detta sätt, infogning, utelämning och sökning

106
00:04:46,370 --> 00:04:50,190
skulle ta i värsta fall O (log n) tid.

107
00:04:50,190 --> 00:04:52,470
Trädet från tidigare kunde vara mer balanserad,

108
00:04:52,470 --> 00:04:54,140
så här.

109
00:04:54,140 --> 00:04:57,980
Nu ser upp något värde tar som mest 3 steg.

110
00:04:57,980 --> 00:04:59,460
Detta träd är balanserad,

111
00:04:59,460 --> 00:05:01,190
mening som har en minimal djup

112
00:05:01,190 --> 00:05:03,680
förhållande till antalet noder.

113
00:05:03,680 --> 00:05:06,300
>> Letar du efter ett värde i en balanserad binärt sökträd

114
00:05:06,300 --> 00:05:09,540
liknar binär sökning på en sorterad array.

115
00:05:09,540 --> 00:05:12,290
Faktum är att om vi inte behöver infoga eller ta bort objekt,

116
00:05:12,290 --> 00:05:15,150
de beter exakt samma sätt.

117
00:05:15,150 --> 00:05:17,600
Emellertid är en trädstruktur bättre

118
00:05:17,600 --> 00:05:19,530
För hantering infogningar och borttagningar

119
00:05:20,360 --> 00:05:22,670
>> Mitt namn är Bannus Van der Kloot.

120
00:05:22,670 --> 00:05:24,030
Detta är CS50.