[Powered by Google Translate] [Binary Search] [Patrick Schmid - Harvard University] [Dette er CS50. - CS50.TV] 

Hvis jeg ga deg en liste over Disney karakter navn i alfabetisk rekkefølge og ba deg om å finne Mikke Mus, hvordan ville du gå om du gjør dette? En åpenbar måte ville være å skanne listen fra begynnelsen og sjekk alle navn for å se om det er Mickey. Men som du leser Aladdin, Alice, Ariel, og så videre, du vil raskt innse at du starter på forsiden av listen var ikke en god idé. Ok, kanskje du burde begynne å jobbe bakover fra slutten av listen. Nå kan du lese Tarzan, Stitch, Snow White, og så videre. Likevel, dette ikke virke som den beste måten å gå om det. 

Vel, er en annen måte at du kan gå om du gjør dette for å prøve å innskrenke listen over navn som du må se på. Siden du vet at de er i alfabetisk rekkefølge, du kan bare se på navnene i midten av listen og sjekk om Mikke Mus er før eller etter dette navnet. Ser på etternavnet i den andre kolonnen du ville innse at M for Mickey kommer etter J for Jasmine, så du vil rett og slett ignorere første halvdel av listen. Så du vil nok se på toppen av den siste kolonnen og ser at det begynner med Rapunzel. Mickey kommer før Rapunzel, ser ut som vi kan ignorere den siste kolonnen i tillegg. Fortsetter søk strategi, vil du raskt se at Mickey er i den første halvdel av den gjenværende navneliste og til slutt finne Mikke gjemmer mellom Merlin og Minnie. 

Hva du har gjort var i utgangspunktet binære søk. Som dette navnet tilsier, utfører den sin søking strategi i en binær sak. Hva betyr dette? Vel, gitt en liste over sorterte elementene, gjør det binære søk algoritme en binær beslutning - venstre eller høyre, som er større enn eller mindre enn, alfabetisk før eller etter - ved hvert punkt. Nå som vi har et navn som går langs med dette søket algoritmen, la oss se på et annet eksempel, men denne gangen med en liste over sortert tall. Si er vi på jakt etter nummeret 144 i denne listen over sortert tall. Akkurat som før, finner vi tall som er i midten - som i dette tilfellet er 13 - og se om 144 er større enn eller mindre enn 13. Siden det er klart større enn 13, kan vi se bort fra alt som er 13 eller mindre og bare konsentrere seg om den andre halvparten. Siden vi nå har et likt antall elementer igjen, vi bare velge et tall som er nær midten. I dette tilfellet velger vi 55. Vi kunne ha like lett valgt 89. Okay. Igjen er 144 høyere enn 55, så vi går til høyre. Heldigvis for oss, er neste midterste tallet 144, den vi leter etter. Så for å finne 144 med et binært søk, er vi i stand til å finne den i kun 3 trinn. Hvis vi ville ha brukt lineær søk her, ville det ha tatt oss 12 trinn. Som et faktisk, siden denne søkemetode halverer antall elementer det har å se på hvert trinn, vil det finne elementet den søker etter i om loggen av antall elementer i listen. Nå som vi har sett to eksempler, la oss ta en titt på noen pseudokode for en rekursiv funksjon som implementerer binære søk. Starter på toppen, ser vi at vi må finne en funksjon som tar 4 argumenter: nøkkel, array, min og maks. Nøkkelen er nummeret som vi leter etter, så 144 i forrige eksempel. Array er listen over numre som vi søker. Min og maks er indeksene for de laveste og høyeste posisjoner at vi nå ser på. Så når vi starter, vil min være null og maks vil være den maksimale indeksverdien av tabellen. Som vi begrense søket ned, vil vi oppdatere min og maks å være nettopp det området som vi fortsatt ser i. 

La oss hoppe til den interessante delen først. Det første vi gjør er å finne midtpunktet, indeksen som ligger halvveis mellom min og maks av tabellen at vi fortsatt vurderer. Så vi ser på verdien av tabellen på det midtpunktet sted og se om det tallet vi leter etter er mindre enn den tasten. Hvis nummeret på den posisjonen er mindre, så det betyr at nøkkelen er større enn alle tallene til venstre for den posisjonen. Så vi kan kalle binært søkefunksjonen igjen, men denne gangen oppdatere min-parametere for å lese bare halvparten som er større enn eller lik verdien vi bare sett på. På den annen side, hvis nøkkelen er mindre enn tallet i den gjeldende midtpunktet av tabellen, vi ønsker å gå til venstre og ignorere alle tall som er større. Igjen, vi kaller binært søk, men denne gangen med et utvalg av min og maks oppdatert å inkludere bare den nedre halvdel. Hvis verdien ved gjeldende midtpunktet i matrisen er verken større enn eller mindre enn nøkkelen, så det må være lik nøkkelen. Dermed kan vi bare returnere gjeldende midtpunktet indeksen, og vi er ferdige. Endelig er denne sjekken her for saken at antall er faktisk ikke i rekken av tall vi søker. Hvis den maksimale indeksverdien i området som vi leter etter er stadig mindre enn den minste, betyr det at vi har gått for langt. Siden antallet var ikke i input array, returnerer vi -1 å indikere at ingenting ble funnet. 

Du har kanskje lagt merke til at for denne algoritmen skal fungere, listen over numre som skal sorteres i. Med andre ord, kan vi bare finne 144 med binære søk hvis alle numrene er bestilt fra laveste til høyeste. Hvis dette ikke var tilfelle, ville vi ikke være i stand til å utelukke halvparten av tallene på hvert trinn. Så vi har to alternativer. Enten kan vi ta en usortert liste og sortere det før du bruker binære søk, eller vi kan sørge for at listen over numre er sortert som vi legger tallene til det. Derfor, i stedet for å sortere akkurat når vi må søke, hvorfor ikke holde listen sortert til alle tider? 

En måte å holde en liste med tall sorteres samtidig gi en å legge til eller flytte tall fra denne listen er ved hjelp av noe som kalles et binært søketre. En binært søketre er en datastruktur som har 3 egenskaper. Først, inneholder den venstre subtre av enhver node bare verdier som er mindre enn eller lik noden verdi. Sekund, inneholder riktig undertreet av en node bare verdier som er større enn eller lik noden verdi. Og til slutt, både venstre og høyre undertreene av alle noder er også binære søk trær. La oss se på et eksempel med de samme tallene vi brukte tidligere. For de av dere som aldri har sett en datamaskin science treet før, la meg begynne med å fortelle deg at en datavitenskap treet vokser nedover. Ja, i motsetning til trær du er vant til, roten av en datamaskin science treet er på toppen, og bladene er nederst. Hver lille boksen kalles en node, og nodene er koblet til hverandre ved kantene. Så roten av dette treet er en node verdi med verdien 13, som har 2 barn noder med verdiene 5 og 34. Et undertre er det treet som er dannet bare ved å se på en underdel av hele treet. 

For eksempel, er den venstre undertreet av node 3 treet skapt av nodene 0, 1 og 2. Så, hvis vi går tilbake til egenskapene til et binært søketre, vi ser at hver node i treet i samsvar med alle tre egenskaper, nemlig, venstre undertreet inneholder bare verdier som er mindre enn eller lik til noden verdi; rett undertreet av alle noder bare inneholder verdier som er større enn eller lik til noden verdi, og både venstre og høyre undertreene av alle noder også er binære search trær. Selv om dette treet ser annerledes ut, er dette en gyldig binært søketre for samme sett med tall. Som et spørsmål om faktum, det er mange mulige måter du kan lage gyldig binært søketre fra disse tallene. Vel, la oss gå tilbake til den første som vi har skapt. Så hva kan vi gjøre med disse trærne? Vel, vi kan veldig enkelt finne minimums-og maksimumsverdier. Minimumsverdiene kan bli funnet ved alltid å gå til venstre til det ikke er flere noder å besøke. Omvendt, for å finne den maksimale en rett og slett bare går ned til høyre på hver gang. 

Finne et annet nummer som ikke er minimum eller maksimum er like enkelt. Si at vi leter etter nummer 89. Vi bare sjekke verdien av hver node og gå til venstre eller høyre, avhengig av om noden verdi er mindre enn eller større enn den vi leter etter. Så starter ved roten av 13, ser vi at 89 er større, og så vi går til høyre. Da ser vi noden for 34, og igjen vi går til høyre. 89 er fortsatt større enn 55, så vi fortsetter å gå til høyre. Vi deretter komme opp med en node med verdien 144 og gå til venstre. Lo og se, 89 er rett der. 

En annen ting som vi kan gjøre er å skrive ut alle tallene ved å utføre en inorder traversering. En inorder traversering betyr å skrive alt ut i venstre subtre etterfulgt ved å skrive noden selv og deretter fulgt ved å skrive alt ut i riktig subtre. For eksempel, la oss ta vår favoritt binært søketre og skrive ut tallene i sortert rekkefølge. Vi starter ved roten av 13, men før utskrift 13 må vi skrive ut alt i venstre subtre. Så vi går til 5. Vi har fortsatt å gå dypere ned i treet til vi finner lengst til venstre node, som er null. Etter utskrift null, går vi tilbake til en og skrive det ut. Så går vi til høyre subtre, som er 2, og skrive det ut. Nå som vi er ferdig med det undertre, vi kan gå tilbake til 3 og skrive det ut. Fortsetter opp igjen, skriver vi 5 og deretter 8. Nå som vi har fullført hele venstre undertre, Vi kan skrive ut 13 og begynne å jobbe på høyre subtre. Vi hoppe ned til 34, men før utskrift 34 må vi skrive ut sin venstre subtre. Så vi skrive ut 21, så vi kommer til å skrive ut 34 og besøke sin rett subtre. Siden 55 har ingen venstre subtre, skriver vi det ut og fortsette videre til sin rett subtre. 144 har en venstre subtre, og så vi skrive ut 89, etterfulgt av 144, og til slutt lengst til høyre node av 233. Det du har det, alle numrene er skrevet ut i rekkefølge fra laveste til høyeste. 

Legge noe til treet er relativt smertefri også. Alt vi trenger å gjøre er å sørge for at vi følger tre binære søketre egenskaper og deretter sette verdien der det er plass. La oss si vi ønsker å sette verdien av 7. Siden 7 er mindre enn 13, går vi til venstre. Men den er større enn 5, slik at vi traversere til høyre. Siden det er mindre enn 8 og 8 er et blad node, legger vi 7 til venstre barn av 8. Voila! Vi har lagt til et tall til vår binært søketre. 

Hvis vi kan legge til ting, vi bedre være i stand til å slette ting også. Dessverre for oss, er å slette en litt mer komplisert - ikke mye, men bare litt. Det er 3 forskjellige scenarier som vi må vurdere når du sletter elementer fra binære søk trær. Først, er den enkleste tilfelle at elementet er en bladnoden. I dette tilfellet, vi bare slette det og gå videre med vår virksomhet. Si at vi ønsker å slette 7 som vi nettopp har lagt. Vel, vi bare finne den, ta den, og det er det. Den neste tilfelle er hvis noden har bare 1 barn. Her kan vi slette noden, men vi må først sørge for å koble subtre som nå igjen foreldreløse til den overordnede av noden vi bare slettet. Si at vi ønsker å slette 3 fra treet vårt. Vi tar barnet element av at node og fest den til den overordnede av noden. I dette tilfellet, er vi nå feste en til 5. Dette fungerer uten problem fordi vi vet, ifølge binært søketre eiendom, at alt i venstre subtre av 3 var mindre enn 5. Nå som 3 sin subtre er tatt vare på, kan vi slette det. Den tredje og siste tilfellet er det mest komplekse. Dette er tilfelle når noden vi ønsker å slette har 2 barn. For å gjøre dette, må vi først finne noden som har den nest største verdien, bytte de to, og deretter slette noden i spørsmålet. Legg merke til noden som har den nest største verdien kan ikke ha to barn selv siden dens venstre barnet ville være en bedre kandidat for den nest største. Derfor slette en node med to barn utgjør bytting av to noder, og deretter slette håndteres av en av de to nevnte regler. For eksempel, la oss si at vi ønsker å slette rotnoden, 13 år. Det første vi gjør er vi finne den neste største verdien i treet som i dette tilfellet, er 21. Vi deretter bytte de to noder, noe som gjør 13 a leaf og 21 den sentrale gruppen node. Nå kan vi bare slette 13. 

Som antydet tidligere, er det mange mulige måter å gjøre en gyldig binært søketre. Dessverre for oss, noen er verre enn andre. For eksempel, hva skjer når vi bygger et binært søketre fra en sortert liste med tall? Alle tall er bare lagt til rette på hvert trinn. Når vi ønsker å søke etter et nummer, Vi har ikke noe valg, men bare for å se på høyre på hvert trinn. Dette er ikke bedre enn lineær søkefunksjon. Selv om vi ikke vil dekke dem her, det finnes andre, mer komplekse, datastrukturer som gjør at dette ikke skjer. Det er imidlertid en enkel ting som kan gjøres for å unngå dette å bare tilfeldig shuffle beregningene. Det er svært usannsynlig at ved tilfeldige en stokket liste med tall er sortert. Hvis dette var tilfelle, ville kasinoer ikke bo i virksomheten for lenge. 

Det du har det. Du vet nå om binær søking og binære søk trær. Jeg er Patrick Schmid, og dette er CS50. [CS50.TV] En åpenbar måte ville være å skanne listen fra ... [pip] ... Antall elementer ... Jepp [Ler] ... Legge noden 234 ... augh. >> Yay! Det var -