[Powered by Google Translate] Hvordan vil du representere alle dine familiemedlemmer i en datamaskin?
Vi kan ganske enkelt bruke en liste,
men det er et klart hierarki her.
>> La oss si at vi begynner med oldemor, Alice.
Hun har to sønner, Bob
og bestefar, Charlie.
Charlie har 3 barn,
onkelen din, Dave, tante, Eve, og din far, Fred.
Du er Fred eneste barn.
>> Hvorfor skulle organisere dine familiemedlemmer på denne måten
være bedre enn den enkel liste representasjon?
En grunn er at dette hierarkisk struktur,
kalt en "tre", inneholder mer informasjon enn en enkel liste.
Vi vet den familiære relasjoner mellom alle
bare ved å undersøke treet.
Dessuten kan det fremskynde
look-up tid enormt, hvis tre data er sortert.
>> Vi kan ikke dra nytte av det her, men vi får se et eksempel på dette snart.
Hver person er representert av en node på treet.
Noder kan ha barnet noder
samt en foreldrenoden.
Dette er de tekniske begrepene,
selv når du bruker trær for ting enn familier.
Alice node har 2 barn og ingen foreldre,
mens Charlie node har 3 barn og en forelder.
>> Et blad node er en som ikke har noen barn
på utsiden kanten av treet.
Den øverste node i treet, rotnoden,
har ingen foreldre.
>> En binær treet er en bestemt type treet,
hvori hver node har, på det meste, 2 barn.
Her er struct av en node i et binært tre i C.
Hver node har noen data knyttet til den
og 2 pekere til andre noder.
>> I vårt slektstre,
tilhørende data var hver persons navn.
Her er det en int, selv om det kan være noe.
Som det viser seg,
et binært tre ville ikke være en god representasjon for en familie,
siden folk ofte har mer enn 2 barn.
>> En binært søketre
er en spesiell, ordnet type binærtreet
som tillater oss å se på verdier raskt.
Du har kanskje lagt merke til
at hver node under roten av et tre
er roten av et annet tre, kalt en "subtre.
Her, er roten av treet 6,
og barn, 2, er roten av et katalogtre.
>> I et binært søketre
alle verdiene i en node er rett subtre
er større enn noden verdi. Her: 6.
Vel, verdiene i en node venstre subtre
er mindre enn noden verdi.
Hvis vi trenger for å håndtere like verdier,
vi kan endre noen av disse til en løs ulikhet,
betyr identiske verdier kan falle enten på venstre eller høyre,
så lenge vi er konsekvente på det hele.
Dette treet er et binært søketre
fordi den følger disse reglene.
>> Dette er hvordan det ville sett ut hvis vi slått alle nodene i C structs.
Legg merke til at hvis et barn mangler,
pekeren er null.
Hvordan sjekker vi for å se om 7 er i treet?
Vi starter ved roten.
Seven er større enn 6, så hvis det er i treet, må det være til høyre.
Deretter er det mindre enn 8, så det må bli stående.
Her har vi funnet syv.
Nå vil vi se etter 5.
Fem er mindre enn 6, så det må være til venstre.
Fem er større enn 2,
så det må være riktig,
og det er også større enn 4, slik at det må være til høyre igjen.
Det er imidlertid ingen barn her.
Pekeren er null.
Dette betyr at 5 ikke er i treet vårt.
>> Vi kan søke den binære treet med følgende kode:
På hver node, sjekker vi å se om vi har funnet
verdien vi leter etter.
Hvis vi ikke finner det, finner vi om det bør være
på venstre eller høyre og sjekk at subtre.
Denne sløyfen vil fortsette ned treet
til det ikke er barnenode enten på venstre eller høyre.
>> Husk at 5 var ikke i treet.
Hvordan setter vi det?
Prosessen ligner å søke.
Vi iterate ned treet fra 6,
venstre til 2,
rett til 4,
og høyre igjen, men 4 har ingen barn på denne siden.
Dette vil være den nye posisjonen for 5,
og det vil begynne med ingen barn.
>> Hvor raske er operasjoner på et binært søketre?
Husk at Bigohnotation søker å gi en øvre grense.
I verste fall,
vår treet kunne bare være en lenket liste
noe som betyr at innsetting, sletting, og søk
kan ta tid proporsjonal til antall noder i treet.
Dette er O (n).
>> For eksempel, er det følgende et gyldig binært søketre.
Men hvis vi prøver å finne 9,
vi må traversere hver node.
Det er ikke bedre enn en lenket liste.
Ideelt sett ville vi ønsker hver node
av vår binært søketre å ha 2 barn.
Denne måten, innsetting, sletting og søk
ville ta i verste fall O (log n) tid.
Treet fra før kan være mer balansert,
som dette.
Nå ser opp noen verdi tar, på det meste, 3 trinn.
Dette treet er balansert,
betydning at den har en minimal dybde
i forhold til antall noder.
>> Leter du etter en verdi i en balansert binært søketre
er lik binært søk på en sortert array.
Faktisk, hvis vi ikke trenger å sette inn eller slette elementer,
de oppfører seg på akkurat samme måte.
Imidlertid er en trestruktur bedre
for håndtering innsettinger og slettinger
>> Mitt navn er Bannus Van der Kloot.
Dette er CS50.