1
00:00:07,050 --> 00:00:09,630
[Powered by Google Translate] Miten edustaa kaikkia perheenjäseniä tietokoneella?

2
00:00:10,790 --> 00:00:12,390
Voisimme yksinkertaisesti käyttää luetteloa,

3
00:00:12,390 --> 00:00:14,400
mutta on selvä hierarkia täällä.

4
00:00:14,400 --> 00:00:17,110
>> Sanotaan alamme kanssa isoisoäiti, Alice.

5
00:00:17,110 --> 00:00:19,030
Hän on 2 poikaa, Bob

6
00:00:19,030 --> 00:00:21,310
ja isoisäsi, Charlie.

7
00:00:21,310 --> 00:00:23,190
Charlie on 3 lasta,

8
00:00:23,190 --> 00:00:26,730
setäsi, Dave, tätisi, Eve, ja isäsi, Fred.

9
00:00:26,730 --> 00:00:28,750
Olet Fredin ainoa lapsi.

10
00:00:28,750 --> 00:00:30,950
>> Miksi järjestää perheenjäsenet tällä tavalla

11
00:00:30,950 --> 00:00:34,010
olla parempi kuin pelkkä luettelo edustus?

12
00:00:34,010 --> 00:00:36,630
Yksi syy on se, että tämä hierarkkista rakennetta,

13
00:00:36,630 --> 00:00:39,660
kutsutaan "puu" sisältää enemmän tietoa kuin pelkkä luettelo.

14
00:00:40,540 --> 00:00:43,520
Tiedämme perhesuhteiden kaikille

15
00:00:43,520 --> 00:00:45,440
vain tarkastelemalla puu.

16
00:00:45,440 --> 00:00:47,250
Lisäksi, se voi nopeuttaa

17
00:00:47,250 --> 00:00:50,010
look-up aika huimasti, jos puu tiedot lajitellaan.

18
00:00:50,010 --> 00:00:53,850
>> Emme voi hyödyntää tätä täällä, mutta näemme esimerkin tästä pian.

19
00:00:53,850 --> 00:00:56,150
Jokainen henkilö edustaa solmu puussa.

20
00:00:56,680 --> 00:00:58,370
Solmut voivat olla lapsen solmuja

21
00:00:58,370 --> 00:01:00,350
sekä isäsolmuun.

22
00:01:00,350 --> 00:01:02,390
Nämä ovat teknisiä termejä,

23
00:01:02,390 --> 00:01:05,220
vaikka käyttäen puita asioiden lisäksi perheille.

24
00:01:05,220 --> 00:01:07,940
Alicen solmu on 2 lasta eikä vanhempia,

25
00:01:07,940 --> 00:01:11,500
taas Charlien solmuun on 3 lasta ja 1 vanhempi.

26
00:01:11,500 --> 00:01:14,330
>> Lehtisolmu on sellainen, joka ei ole lapsia

27
00:01:14,330 --> 00:01:16,410
ulkoreunassa puun.

28
00:01:16,410 --> 00:01:18,520
Ylimmäinen solmu puun, juurisolmu

29
00:01:18,520 --> 00:01:20,240
ei vanhempi.

30
00:01:20,240 --> 00:01:23,170
>> Binääripuu on tietyntyyppinen puu,

31
00:01:23,170 --> 00:01:26,720
jossa kullakin solmulla on, enimmillään, 2 lasta.

32
00:01:26,720 --> 00:01:30,490
Tässä on struct on solmun binääri-puu C.

33
00:01:31,560 --> 00:01:34,530
Jokaisella solmulla on joitakin siihen liittyvät tiedot

34
00:01:34,530 --> 00:01:36,520
ja 2 viitteitä muihin solmuihin.

35
00:01:36,520 --> 00:01:38,110
>> Meidän sukupuu,

36
00:01:38,110 --> 00:01:40,900
liittyvät tiedot olivat kunkin henkilön nimi.

37
00:01:40,900 --> 00:01:43,850
Tässä se on int, vaikka se voi olla mitä tahansa.

38
00:01:44,510 --> 00:01:46,200
Kuten on käynyt ilmi,

39
00:01:46,200 --> 00:01:48,990
binääripuu ei olisi hyvä edustus perhe,

40
00:01:48,990 --> 00:01:51,960
koska ihmiset usein ovat enemmän kuin 2 lasta.

41
00:01:51,960 --> 00:01:53,510
>> Binäärihakupuu

42
00:01:53,510 --> 00:01:56,380
on erityinen, säntillinen tyyppi binaaripuun

43
00:01:56,380 --> 00:01:58,090
jonka avulla voimme tarkastella arvoihin nopeasti.

44
00:01:58,740 --> 00:02:00,050
Olet ehkä huomannut

45
00:02:00,050 --> 00:02:02,010
että jokainen solmu alle juuri puun

46
00:02:02,010 --> 00:02:04,620
on juuri toinen puu, jota kutsutaan "alipuu."

47
00:02:04,960 --> 00:02:07,090
Täällä puun juurta on 6,

48
00:02:07,090 --> 00:02:09,860
ja sen lapsi, 2, on juuri alipuun.

49
00:02:09,860 --> 00:02:11,870
>> In binäärihakupuu

50
00:02:11,870 --> 00:02:15,790
kaikki arvot solmun oikean alipuun

51
00:02:15,790 --> 00:02:18,690
ovat suurempia kuin solmun arvo. Täällä: 6.

52
00:02:18,690 --> 00:02:22,640
No, arvot solmun vasemman alipuun

53
00:02:24,540 --> 00:02:26,890
ovat vähemmän kuin solmun arvo.

54
00:02:26,890 --> 00:02:28,620
Jos meidän täytyy käsitellä päällekkäisiä arvoja,

55
00:02:28,620 --> 00:02:31,760
Voimme muuttaa jommankumman on löysä eriarvoisuutta,

56
00:02:31,760 --> 00:02:34,410
eli sama arvot voidaan laskea joko vasemmalle tai oikealle,

57
00:02:34,410 --> 00:02:37,400
niin kauan kuin olemme johdonmukaisesti siitä kaikkialla.

58
00:02:37,400 --> 00:02:39,620
Tämä puu on binäärinen hakupuu

59
00:02:39,620 --> 00:02:41,540
koska se seuraa näitä sääntöjä.

60
00:02:42,320 --> 00:02:46,020
>> Näin se näyttää, jos me käännetään kaikki solmut osaksi C tietueet.

61
00:02:46,880 --> 00:02:48,410
Huomaa, että jos lapsi puuttuu,

62
00:02:48,410 --> 00:02:50,340
osoitin on nolla.

63
00:02:50,340 --> 00:02:53,270
Miten tarkistaa, onko 7 on puu?

64
00:02:53,270 --> 00:02:55,020
Aloitamme juureen.

65
00:02:55,020 --> 00:02:58,690
Seitsemän on suurempi kuin 6, joten jos sitä on puu, se on oltava oikea.

66
00:02:59,680 --> 00:03:03,650
Sitten se on vähemmän kuin 8, joten sitä on jäljellä.

67
00:03:03,650 --> 00:03:06,210
Tässä olemme havainneet, 7.

68
00:03:06,210 --> 00:03:08,160
Nyt me tarkista 5.

69
00:03:08,160 --> 00:03:11,500
Viisi on alle 6, joten sen täytyy olla vasemmalla.

70
00:03:11,500 --> 00:03:13,460
Viisi on suurempi kuin 2,

71
00:03:13,460 --> 00:03:15,010
joten sen täytyy olla oikea,

72
00:03:15,010 --> 00:03:18,100
ja se on myös suurempi kuin 4, niin sen täytyy olla jälleen oikeaan.

73
00:03:18,100 --> 00:03:20,300
Kuitenkin, ei ole olemassa lapsi täällä.

74
00:03:20,300 --> 00:03:22,000
Osoitin on nolla.

75
00:03:22,000 --> 00:03:24,270
Tämä tarkoittaa, että 5 ei ole meidän puu.

76
00:03:24,270 --> 00:03:27,250
>> Voimme etsiä binääripuu seuraavalla koodilla:

77
00:03:28,430 --> 00:03:31,140
Jokaisessa solmussa, tarkistamme onko olemme löytäneet

78
00:03:31,140 --> 00:03:33,020
arvo etsimme.

79
00:03:33,020 --> 00:03:35,740
Jos emme löydä sitä, päätämme se olisi

80
00:03:35,740 --> 00:03:38,990
vasemmalle tai oikealle ja tarkista, että alipuu.

81
00:03:38,990 --> 00:03:41,160
Tämä silmukka jatkuu alas puusta

82
00:03:41,160 --> 00:03:44,190
kunnes ei ole lapsisolmuun joko vasemmalle tai oikealle.

83
00:03:45,190 --> 00:03:48,600
>> Muista, että 5 ei ollut puussa.

84
00:03:48,600 --> 00:03:50,460
Miten aseta se?

85
00:03:50,460 --> 00:03:52,370
Prosessi näyttää samanlaiselta etsiä.

86
00:03:52,370 --> 00:03:54,830
Me toistaa alas puusta alkaen 6,

87
00:03:54,830 --> 00:03:57,040
jäljellä 2,

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

89
00:03:59,140 --> 00:04:02,500
ja taas oikealle, mutta 4 ei lapsi tällä puolella.

90
00:04:02,500 --> 00:04:06,090
Tämä on uutta asemaa 5,

91
00:04:06,090 --> 00:04:08,500
ja se alkaa ilman lapsia.

92
00:04:09,020 --> 00:04:12,220
>> Kuinka nopeasti toimintansa binäärihakupuu?

93
00:04:12,220 --> 00:04:15,410
Muista, että Bigohnotation pyrkii tarjoamaan yläraja.

94
00:04:15,410 --> 00:04:17,390
Pahimmassa tapauksessa,

95
00:04:17,390 --> 00:04:19,480
meidän puu voisi yksinkertaisesti olla linkitetty lista

96
00:04:19,480 --> 00:04:22,220
eli lisäys, poisto ja haku

97
00:04:22,220 --> 00:04:25,380
voi kestää aikaa verrannollinen solmujen määrä puussa.

98
00:04:25,380 --> 00:04:27,380
Tämä on O (n).

99
00:04:27,380 --> 00:04:30,690
>> Esimerkiksi seuraava on voimassa binäärihakupuu.

100
00:04:31,850 --> 00:04:34,020
Kuitenkin, jos yritämme löytää 9,

101
00:04:34,020 --> 00:04:36,760
meidän täytyy kulkea jokaisessa solmussa.

102
00:04:36,760 --> 00:04:39,120
Se ei ole parempi kuin linkitetty lista.

103
00:04:39,120 --> 00:04:41,410
Ihannetapauksessa haluaisimme jokaisen solmun

104
00:04:41,410 --> 00:04:44,120
meidän binäärihakupuu on 2 lasta.

105
00:04:44,120 --> 00:04:46,370
Näin lisäys, poisto ja haku

106
00:04:46,370 --> 00:04:50,190
veisi pahimmillaan O (log n) ajan.

107
00:04:50,190 --> 00:04:52,470
Puu ennen voisi olla tasapainoisempi,

108
00:04:52,470 --> 00:04:54,140
näin.

109
00:04:54,140 --> 00:04:57,980
Nyt etsii kaikki arvot kestää enimmillään 3 askelmaa.

110
00:04:57,980 --> 00:04:59,460
Tämä puu on tasapainoinen,

111
00:04:59,460 --> 00:05:01,190
merkityksessä, että se on minimaalinen syvyys

112
00:05:01,190 --> 00:05:03,680
suhteessa solmujen lukumäärä.

113
00:05:03,680 --> 00:05:06,300
>> Etsitkö arvon tasapainoinen binäärihakupuu

114
00:05:06,300 --> 00:05:09,540
on samanlainen binary haku lajiteltu array.

115
00:05:09,540 --> 00:05:12,290
Itse asiassa, jos emme tarvitse lisätä tai poistaa kohteita,

116
00:05:12,290 --> 00:05:15,150
ne käyttäytyvät täsmälleen samalla tavalla.

117
00:05:15,150 --> 00:05:17,600
Kuitenkin, puurakenteeksi on parempi

118
00:05:17,600 --> 00:05:19,530
käsittelyyn lisäykset ja poistot

119
00:05:20,360 --> 00:05:22,670
>> Nimeni on Bannus Van der Kloot.

120
00:05:22,670 --> 00:05:24,030
Tämä on CS50.