[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.