[Powered by Google Translate] Miten edustaa kaikkia perheenjäseniä tietokoneella?
Voisimme yksinkertaisesti käyttää luetteloa,
mutta on selvä hierarkia täällä.
>> Sanotaan alamme kanssa isoisoäiti, Alice.
Hän on 2 poikaa, Bob
ja isoisäsi, Charlie.
Charlie on 3 lasta,
setäsi, Dave, tätisi, Eve, ja isäsi, Fred.
Olet Fredin ainoa lapsi.
>> Miksi järjestää perheenjäsenet tällä tavalla
olla parempi kuin pelkkä luettelo edustus?
Yksi syy on se, että tämä hierarkkista rakennetta,
kutsutaan "puu" sisältää enemmän tietoa kuin pelkkä luettelo.
Tiedämme perhesuhteiden kaikille
vain tarkastelemalla puu.
Lisäksi, se voi nopeuttaa
look-up aika huimasti, jos puu tiedot lajitellaan.
>> Emme voi hyödyntää tätä täällä, mutta näemme esimerkin tästä pian.
Jokainen henkilö edustaa solmu puussa.
Solmut voivat olla lapsen solmuja
sekä isäsolmuun.
Nämä ovat teknisiä termejä,
vaikka käyttäen puita asioiden lisäksi perheille.
Alicen solmu on 2 lasta eikä vanhempia,
taas Charlien solmuun on 3 lasta ja 1 vanhempi.
>> Lehtisolmu on sellainen, joka ei ole lapsia
ulkoreunassa puun.
Ylimmäinen solmu puun, juurisolmu
ei vanhempi.
>> Binääripuu on tietyntyyppinen puu,
jossa kullakin solmulla on, enimmillään, 2 lasta.
Tässä on struct on solmun binääri-puu C.
Jokaisella solmulla on joitakin siihen liittyvät tiedot
ja 2 viitteitä muihin solmuihin.
>> Meidän sukupuu,
liittyvät tiedot olivat kunkin henkilön nimi.
Tässä se on int, vaikka se voi olla mitä tahansa.
Kuten on käynyt ilmi,
binääripuu ei olisi hyvä edustus perhe,
koska ihmiset usein ovat enemmän kuin 2 lasta.
>> Binäärihakupuu
on erityinen, säntillinen tyyppi binaaripuun
jonka avulla voimme tarkastella arvoihin nopeasti.
Olet ehkä huomannut
että jokainen solmu alle juuri puun
on juuri toinen puu, jota kutsutaan "alipuu."
Täällä puun juurta on 6,
ja sen lapsi, 2, on juuri alipuun.
>> In binäärihakupuu
kaikki arvot solmun oikean alipuun
ovat suurempia kuin solmun arvo. Täällä: 6.
No, arvot solmun vasemman alipuun
ovat vähemmän kuin solmun arvo.
Jos meidän täytyy käsitellä päällekkäisiä arvoja,
Voimme muuttaa jommankumman on löysä eriarvoisuutta,
eli sama arvot voidaan laskea joko vasemmalle tai oikealle,
niin kauan kuin olemme johdonmukaisesti siitä kaikkialla.
Tämä puu on binäärinen hakupuu
koska se seuraa näitä sääntöjä.
>> Näin se näyttää, jos me käännetään kaikki solmut osaksi C tietueet.
Huomaa, että jos lapsi puuttuu,
osoitin on nolla.
Miten tarkistaa, onko 7 on puu?
Aloitamme juureen.
Seitsemän on suurempi kuin 6, joten jos sitä on puu, se on oltava oikea.
Sitten se on vähemmän kuin 8, joten sitä on jäljellä.
Tässä olemme havainneet, 7.
Nyt me tarkista 5.
Viisi on alle 6, joten sen täytyy olla vasemmalla.
Viisi on suurempi kuin 2,
joten sen täytyy olla oikea,
ja se on myös suurempi kuin 4, niin sen täytyy olla jälleen oikeaan.
Kuitenkin, ei ole olemassa lapsi täällä.
Osoitin on nolla.
Tämä tarkoittaa, että 5 ei ole meidän puu.
>> Voimme etsiä binääripuu seuraavalla koodilla:
Jokaisessa solmussa, tarkistamme onko olemme löytäneet
arvo etsimme.
Jos emme löydä sitä, päätämme se olisi
vasemmalle tai oikealle ja tarkista, että alipuu.
Tämä silmukka jatkuu alas puusta
kunnes ei ole lapsisolmuun joko vasemmalle tai oikealle.
>> Muista, että 5 ei ollut puussa.
Miten aseta se?
Prosessi näyttää samanlaiselta etsiä.
Me toistaa alas puusta alkaen 6,
jäljellä 2,
oikeus 4,
ja taas oikealle, mutta 4 ei lapsi tällä puolella.
Tämä on uutta asemaa 5,
ja se alkaa ilman lapsia.
>> Kuinka nopeasti toimintansa binäärihakupuu?
Muista, että Bigohnotation pyrkii tarjoamaan yläraja.
Pahimmassa tapauksessa,
meidän puu voisi yksinkertaisesti olla linkitetty lista
eli lisäys, poisto ja haku
voi kestää aikaa verrannollinen solmujen määrä puussa.
Tämä on O (n).
>> Esimerkiksi seuraava on voimassa binäärihakupuu.
Kuitenkin, jos yritämme löytää 9,
meidän täytyy kulkea jokaisessa solmussa.
Se ei ole parempi kuin linkitetty lista.
Ihannetapauksessa haluaisimme jokaisen solmun
meidän binäärihakupuu on 2 lasta.
Näin lisäys, poisto ja haku
veisi pahimmillaan O (log n) ajan.
Puu ennen voisi olla tasapainoisempi,
näin.
Nyt etsii kaikki arvot kestää enimmillään 3 askelmaa.
Tämä puu on tasapainoinen,
merkityksessä, että se on minimaalinen syvyys
suhteessa solmujen lukumäärä.
>> Etsitkö arvon tasapainoinen binäärihakupuu
on samanlainen binary haku lajiteltu array.
Itse asiassa, jos emme tarvitse lisätä tai poistaa kohteita,
ne käyttäytyvät täsmälleen samalla tavalla.
Kuitenkin, puurakenteeksi on parempi
käsittelyyn lisäykset ja poistot
>> Nimeni on Bannus Van der Kloot.
Tämä on CS50.