1
00:00:07,050 --> 00:00:09,630
[Powered by Google Translate] Kako bi zastopa vse svoje družinske člane v računalniku?

2
00:00:10,790 --> 00:00:12,390
Lahko bi enostavno uporabite seznam,

3
00:00:12,390 --> 00:00:14,400
vendar pa je jasna hierarhija tukaj.

4
00:00:14,400 --> 00:00:17,110
>> Recimo, da smo začeli s svojo prababica, Alice.

5
00:00:17,110 --> 00:00:19,030
Ima 2 sinova, Bob

6
00:00:19,030 --> 00:00:21,310
in tvoj dedek, Charlie.

7
00:00:21,310 --> 00:00:23,190
Charlie ima 3 otroke,

8
00:00:23,190 --> 00:00:26,730
tvoj stric, Dave, tvoja teta, Eve, in tvoj oče, Fred.

9
00:00:26,730 --> 00:00:28,750
Vi ste edini otrok Fred.

10
00:00:28,750 --> 00:00:30,950
>> Zakaj bi organiziranje vaših družinskih članov na ta način

11
00:00:30,950 --> 00:00:34,010
bolje kot preprosto zastopanje seznama?

12
00:00:34,010 --> 00:00:36,630
Eden od razlogov je, da je to hierarhična struktura,

13
00:00:36,630 --> 00:00:39,660
imenovano "drevo" vsebuje več informacij kot preprosti seznam.

14
00:00:40,540 --> 00:00:43,520
Vemo, sorodstvenih odnosov med vsemi

15
00:00:43,520 --> 00:00:45,440
samo s preučevanjem drevo.

16
00:00:45,440 --> 00:00:47,250
Prav tako lahko pospeši

17
00:00:47,250 --> 00:00:50,010
Navlake čas strašen, če je razvrščen podatke o drevesu.

18
00:00:50,010 --> 00:00:53,850
>> Ne moremo izkoristiti, da tukaj, pa bomo videli zgled za to kmalu.

19
00:00:53,850 --> 00:00:56,150
Vsaka oseba, ki se predstavlja vozlišče v drevesu.

20
00:00:56,680 --> 00:00:58,370
Vozlišča lahko otrok vozlišč

21
00:00:58,370 --> 00:01:00,350
kot tudi matično vozlišču.

22
00:01:00,350 --> 00:01:02,390
To so tehnične izraze,

23
00:01:02,390 --> 00:01:05,220
tudi z uporabo dreves za stvari, poleg družine.

24
00:01:05,220 --> 00:01:07,940
Vozlišče Alice ima 2 otroka in ne staršev,

25
00:01:07,940 --> 00:01:11,500
medtem ko je vozlišče Charliejeva ima 3 otroke in 1 starš.

26
00:01:11,500 --> 00:01:14,330
>> Listov vozlišča je tisti, ki nima otrok

27
00:01:14,330 --> 00:01:16,410
na zunanjem robu drevo.

28
00:01:16,410 --> 00:01:18,520
Je najvišje vozlišče v drevesu, vozlišče koren,

29
00:01:18,520 --> 00:01:20,240
nima staršev.

30
00:01:20,240 --> 00:01:23,170
>> Binarno drevo je posebna vrsta drevesa,

31
00:01:23,170 --> 00:01:26,720
v katerem vsako vozlišče ima največ 2 otroka.

32
00:01:26,720 --> 00:01:30,490
Tukaj je struct za vozlišče binarno drevo C.

33
00:01:31,560 --> 00:01:34,530
Vsako vozlišče ima nekatere podatke, povezane z njim

34
00:01:34,530 --> 00:01:36,520
in 2 kazalci na drugih vozlišč.

35
00:01:36,520 --> 00:01:38,110
>> V našem družinskem drevesu

36
00:01:38,110 --> 00:01:40,900
pridruženih podatki so bili vsi ime osebe.

37
00:01:40,900 --> 00:01:43,850
Tukaj je int, čeprav bi lahko bilo karkoli.

38
00:01:44,510 --> 00:01:46,200
Kot se je izkazalo,

39
00:01:46,200 --> 00:01:48,990
binarno drevo ne bi bila dobra predstavitev za družino,

40
00:01:48,990 --> 00:01:51,960
saj ljudje pogosto imajo več kot 2 otroka.

41
00:01:51,960 --> 00:01:53,510
>> Binarno iskalno drevo

42
00:01:53,510 --> 00:01:56,380
je posebna, urejena vrsta drevesa binarnem

43
00:01:56,380 --> 00:01:58,090
ki nam omogoča, da pogled na vrednote hitro.

44
00:01:58,740 --> 00:02:00,050
Morda ste opazili,

45
00:02:00,050 --> 00:02:02,010
da vsako vozlišče pod koren drevesa

46
00:02:02,010 --> 00:02:04,620
je koren drevesa drugega, imenovanega "poddrevo."

47
00:02:04,960 --> 00:02:07,090
Tu so korenine drevesa je 6,

48
00:02:07,090 --> 00:02:09,860
in njena otroka, 2, je koren poddrevesa.

49
00:02:09,860 --> 00:02:11,870
>> V dvojiškega drevesa

50
00:02:11,870 --> 00:02:15,790
vse vrednosti vozlišča je desno poddrevo

51
00:02:15,790 --> 00:02:18,690
večje od vrednosti vozlišča. Tukaj: 6.

52
00:02:18,690 --> 00:02:22,640
No, vrednosti v levo poddrevo vozlišča

53
00:02:24,540 --> 00:02:26,890
manj kot vrednosti vozlišča.

54
00:02:26,890 --> 00:02:28,620
Če moramo ravnati podvojene vrednosti,

55
00:02:28,620 --> 00:02:31,760
moremo spremeniti niti tistih, ki se ohlapno neenakosti,

56
00:02:31,760 --> 00:02:34,410
kar pomeni, enake vrednosti se lahko bodisi padel na levo ali desno,

57
00:02:34,410 --> 00:02:37,400
tako dolgo, kot smo dosledno o njem po vsej.

58
00:02:37,400 --> 00:02:39,620
To drevo je dvojiško iskalno drevo

59
00:02:39,620 --> 00:02:41,540
ker naj bi se ta pravila.

60
00:02:42,320 --> 00:02:46,020
>> To je, kako bi bilo videti, če smo se obrnili vsa vozlišča v konstrukti C.

61
00:02:46,880 --> 00:02:48,410
Obvestilo, da če otrok ni,

62
00:02:48,410 --> 00:02:50,340
kazalec je nična.

63
00:02:50,340 --> 00:02:53,270
Kako preverite, ali 7 je na drevesu?

64
00:02:53,270 --> 00:02:55,020
Začnemo pri korenu.

65
00:02:55,020 --> 00:02:58,690
Sedem je več kot 6, tako da če je na drevesu, mora biti na desni strani.

66
00:02:59,680 --> 00:03:03,650
Potem pa je manj kot 8, zato mora ostati.

67
00:03:03,650 --> 00:03:06,210
Tu smo ugotovili, 7.

68
00:03:06,210 --> 00:03:08,160
Sedaj bomo preverite, 5.

69
00:03:08,160 --> 00:03:11,500
Pet je manj kot 6, tako da mora biti na levi strani.

70
00:03:11,500 --> 00:03:13,460
Pet je večje od 2,

71
00:03:13,460 --> 00:03:15,010
zato mora biti v redu,

72
00:03:15,010 --> 00:03:18,100
prav tako pa je večje od 4, zato mora biti spet v redu.

73
00:03:18,100 --> 00:03:20,300
Vendar pa ni otrok tukaj.

74
00:03:20,300 --> 00:03:22,000
Kazalec je nična.

75
00:03:22,000 --> 00:03:24,270
To pomeni, da je 5 ni v našem drevesu.

76
00:03:24,270 --> 00:03:27,250
>> Mi lahko iščete binarno drevo z naslednjo kodo:

77
00:03:28,430 --> 00:03:31,140
Na vsakem vozlišču, preverimo, če smo našli

78
00:03:31,140 --> 00:03:33,020
vrednota, ki jo iščete.

79
00:03:33,020 --> 00:03:35,740
Če ne bomo našli, bomo ugotovili, če je treba

80
00:03:35,740 --> 00:03:38,990
na levo ali desno in preverite, ali poddrevo.

81
00:03:38,990 --> 00:03:41,160
Ta krog se bo nadaljeval z drevesa

82
00:03:41,160 --> 00:03:44,190
dokler ni otrok vozlišče bodisi na levo ali desno.

83
00:03:45,190 --> 00:03:48,600
>> Ne pozabite, da je 5 ni v drevesu.

84
00:03:48,600 --> 00:03:50,460
Kako ga vstavite?

85
00:03:50,460 --> 00:03:52,370
Postopek je podoben iskanje.

86
00:03:52,370 --> 00:03:54,830
Mi Ponovil navzdol drevesa od 6,

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

88
00:03:57,040 --> 00:03:59,140
Pravica do 4,

89
00:03:59,140 --> 00:04:02,500
in še enkrat desno, ampak 4 nima otroka na tej strani.

90
00:04:02,500 --> 00:04:06,090
To bo nov položaj 5,

91
00:04:06,090 --> 00:04:08,500
in bo začela brez otrok.

92
00:04:09,020 --> 00:04:12,220
>> Kako hitro so operacije na dvojiškega drevesa?

93
00:04:12,220 --> 00:04:15,410
Ne pozabite, da Bigohnotation želi zagotoviti zgornja meja.

94
00:04:15,410 --> 00:04:17,390
V najslabšem primeru,

95
00:04:17,390 --> 00:04:19,480
naše drevo lahko preprosto povezani seznam

96
00:04:19,480 --> 00:04:22,220
kar pomeni, da vstavljanje, brisanje in iskanje

97
00:04:22,220 --> 00:04:25,380
lahko traja nekaj časa, sorazmeren s številom vozlišč v drevesu.

98
00:04:25,380 --> 00:04:27,380
To je O (n).

99
00:04:27,380 --> 00:04:30,690
>> Na primer, tole ni veljavno binarno iskalno drevo.

100
00:04:31,850 --> 00:04:34,020
Vendar, če bomo poskušali najti 9,

101
00:04:34,020 --> 00:04:36,760
imamo za prečkanje vsako vozlišče.

102
00:04:36,760 --> 00:04:39,120
Ni boljšega kot povezan seznam.

103
00:04:39,120 --> 00:04:41,410
Idealno bi bilo, bi si želeli vsako vozlišče

104
00:04:41,410 --> 00:04:44,120
naše drevo binarno iskalno da ima 2 otroka.

105
00:04:44,120 --> 00:04:46,370
Na ta način, vstavljanje, brisanje in iskanje

106
00:04:46,370 --> 00:04:50,190
bi se v najslabšem primeru O (log n) časa.

107
00:04:50,190 --> 00:04:52,470
Drevo od prej bi mogla biti bolj uravnotežen,

108
00:04:52,470 --> 00:04:54,140
kot je ta.

109
00:04:54,140 --> 00:04:57,980
Zdaj pa gledal kakšno vrednost ima v največ 3 koraki.

110
00:04:57,980 --> 00:04:59,460
To drevo je uravnotežen,

111
00:04:59,460 --> 00:05:01,190
kar pomeni, da je ima minimalno globino

112
00:05:01,190 --> 00:05:03,680
glede na število vozlišč.

113
00:05:03,680 --> 00:05:06,300
>> Iščete vrednost v binarno iskalno drevo uravnoteženo

114
00:05:06,300 --> 00:05:09,540
Podobno je pri binarnem iskanju na razvrščeni matrike.

115
00:05:09,540 --> 00:05:12,290
V bistvu, če nam ni treba, da vstavite ali izbrišete elemente,

116
00:05:12,290 --> 00:05:15,150
se obnašajo natanko na enak način.

117
00:05:15,150 --> 00:05:17,600
Vendar pa je drevesna struktura je bolje

118
00:05:17,600 --> 00:05:19,530
za ravnanje z vstavki in izbrisi

119
00:05:20,360 --> 00:05:22,670
>> Moje ime je Bannus Van der Kloot.

120
00:05:22,670 --> 00:05:24,030
To je CS50.