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

Hvis jeg gav dig en liste over Disney character navne i alfabetisk rækkefølge og bedt dig om at finde Mickey Mouse, hvordan ville du gå om at gøre dette? En indlysende måde ville være at scanne listen fra begyndelsen og kontrollere hver navn for at se, om det er Mickey. Men når du læser Aladdin, Alice, Ariel, og så videre, vil du hurtigt indse, at starte på forsiden af ​​listen ikke var en god idé. Okay, måske skulle du begynde at arbejde baglæns fra slutningen af ​​listen. Nu kan du læse Tarzan, Stitch, Snehvide, og så videre. Alligevel synes dette ikke som den bedste måde at gå om det. 

Nå, en anden måde, at du kunne gå om at gøre dette på er at forsøge at indsnævre listen over de navne, som du er nødt til at se på. Da du ved, at de er i alfabetisk rækkefølge, du bare kunne se på navnene i midten af ​​listen og kontrollere, om Mickey Mouse er før eller efter dette navn. Ser man på det sidste navn i anden kolonne du ville indse, at M for Mickey kommer efter J for Jasmine, så du ville bare ignorere den første halvdel af listen. Så skal du nok se på toppen af ​​den sidste kolonne og se, at det begynder med Rapunzel. Mickey kommer før Rapunzel, ser ud til vi kan ignorere den sidste kolonne så godt. Fortsat søgestrategien, vil du hurtigt se, at Mickey er i den første halvdel af den resterende navnelisten og endelig finde Mickey gemmer sig mellem Merlin og Minnie. 

Hvad du lige gjorde var dybest set binær søgning. Da dette navnet antyder, det udfører sin søgning strategi i en binær sag. Hvad betyder dette? Nå, få en liste med sorterede elementer, det binære søgealgoritme gør en binær afgørelse - venstre eller højre, over eller under, alfabetisk før eller efter - i hvert punkt. Nu hvor vi har et navn, der går langs med denne søgealgoritme, lad os se på et andet eksempel, men denne gang med en liste over sorteret numre. Siger, at vi er på udkig efter det nummer 144 i denne liste over sorteret numre. Ligesom før, finder vi det tal, der er i midten - som i dette tilfælde er 13 - og se om 144 er større end eller mindre end 13. Da det er klart større end 13, kan vi ignorere alt, der er 13 eller derunder og bare koncentrere sig om den resterende halvdel. Da vi nu har et lige antal elementer tilbage, vi simpelthen vælge et nummer, der er tæt på midten. I dette tilfælde vælger vi 55. Vi kunne have lige så let valgt 89. Okay. Igen, 144 er større end 55, så vi går til højre. Heldigvis for os, er det næste midterste tal 144, den vi leder efter. Så for at finde 144 ved hjælp af en binær søgning, vi er i stand til at finde det i kun 3 trin. Hvis vi ville have brugt lineær søgning her, ville det have taget os 12 trin. Som en kendsgerning, denne søgemetode siden halverer antallet af elementer det skal se på ved hvert trin, vil det finde det element, som søger efter i omkring loggen af ​​antallet af elementer på listen. Nu, hvor vi har set 2 eksempler, lad os tage et kig på nogle pseudokoden for en rekursiv funktion som implementerer binær søgning. Start foroven, kan vi se, at vi er nødt til at finde en funktion, der tager 4 argumenter: nøgle, array, min og max. Det centrale er det nummer, vi leder efter, så 144 i det foregående eksempel. Array er listen over numre, som vi søger. Min og max er indekser minimum og maksimum positioner at vi i øjeblikket kigger på. Så når vi starter, vil min være nul og maks. vil være den maksimale indeks af array. Som vi indsnævre søgningen ned, vil vi opdatere min og max at være lige det område, at vi stadig er på udkig i. 

Lad os springe til den interessante del først. Det første, vi gør, er at finde midtpunktet, det indeks, der ligger halvvejs mellem min og max af arrayet, at vi stadig overvejer. Så ser vi på værdien af ​​array ved at midtpunktet placering og se, om det nummer, vi leder efter, er mindre end den nøgle. Hvis antallet i denne position er mindre, så betyder det, at nøglen er større end alle numre til venstre for denne position. Så vi kan kalde binær søgefunktion igen, men denne gang opdatere min og max parametre for at læse bare det halve der er større end eller lig med den værdi, vi kiggede bare på. På den anden side, hvis nøglen er lavere end antallet i den aktuelle midtpunktet af arrayet vi ønsker at gå til venstre og ignorere alle tal, der er større. Igen, vi kalder binær søgning, men denne gang med den række af min og max opdateret omfatte blot den nederste halvdel. Hvis værdien på det aktuelle midtpunkt i arrayet er hverken større end eller mindre end tasten, så må det være lig med nøglen. Således kan vi blot returnere den aktuelle midtpunkt indeks, og vi er færdige. Endelig er denne kontrol her er for det tilfælde, at antallet er faktisk ikke i den vifte af numre, vi søger. Hvis den maksimale indeks for det område, vi er på udkig efter er stadig mindre end det minimum, der betyder, at vi har gået for langt. Da nummeret ikke var i inputarrayet, vender vi tilbage -1 at indikere, at intet blev fundet. 

Du har måske bemærket, at for denne algoritme til at arbejde, listen over numre skal sorteres. Med andre ord kan vi kun finde 144 ved hjælp af binær søgning hvis alle tallene bestilles fra laveste til højeste. Hvis dette ikke var tilfældet, ville vi ikke være i stand til at udelukke halvdelen af ​​numrene på hvert trin. Så vi har 2 muligheder. Enten kan vi tage en usorteret liste og sortere det, før du bruger binær søgning, eller vi kan sørge for, at listen over numre sorteres som vi tilføje numre til det. I stedet for at sortere lige når vi er nødt til at søge, hvorfor ikke holde listen sorteres på alle tidspunkter? 

En måde at holde en liste over numre sorteres samtidig tillader en til at tilføje eller flytte numre fra denne liste er ved hjælp af noget, der hedder et binært søgetræ. En binær søgning træ er en datastruktur, der har 3 egenskaber. Først den venstre undertræ et emne indeholder kun værdier, der er mindre end eller lig med knudepunktet værdi. Dels ret undertræ af et knudepunkt kun indeholder værdier, der er større end eller lig med knudepunktet værdi. Og endelig både venstre og højre undertræer af alle knuder er også binære søgetræer. Lad os se på et eksempel med de samme numre, vi brugte tidligere. For dem af jer, der aldrig har set en computer science træ før, lad mig starte med at fortælle dig, at en computer science træet vokser nedad. Ja, i modsætning til træer du er vant til, roden af ​​en computer science træ er øverst, og bladene er i bunden. Hver lille boks kaldes en knude, og knuderne er forbundet med hinanden ved kanterne. Så roden af ​​dette træ er et knudepunkt værdi med værdien 13, der har 2 børn noder med værdierne 5 og 34 år. Et undertræ er træet, der dannes blot ved at kigge på en underafdeling af hele træet. 

For eksempel er den venstre undertræ af knudepunktet 3 træet skabt af knudepunkterne 0, 1 og 2. Så hvis vi går tilbage til egenskaberne af en binær søgning træ, vi se, at hver node i træet i overensstemmelse med alle 3 ejendomme, nemlig, den venstre undertræ kun indeholder værdier, der er mindre end eller lig med knudepunktet værdi; ret undertræ over alle emner kun indeholder værdier, der er større end eller lig med knudepunktet værdi, og både venstre og højre undertræer af alle knuder også er binære søgetræer. Selv om dette træ ser anderledes ud, dette er en gyldig binær søgning tree for det samme sæt af numre. Som en kendsgerning, er der mange mulige måder, du kan oprette en gyldig binær søgning træ fra disse numre. Nå, lad os gå tilbage til den første, vi har oprettet. Så hvad kan vi gøre med disse træer? Nå, kan vi ganske enkelt finde minimum og maksimum værdier. Minimumsværdierne findes ved altid at gå mod venstre indtil der ikke er flere knuder at besøge. Omvendt at finde den maksimalt en simpelthen bare går ned til højre på hver gang. 

Finde et andet nummer, der ikke er minimum eller maksimum er lige så nemt. Siger, at vi leder efter nummeret 89. Vi har simpelthen kontrollere værdien af ​​hver node og gå til venstre eller højre, afhængigt af om knudens værdi er mindre end eller større end den vi leder efter. Så starter ved roden af ​​13, ser vi, at 89 er større, og så går vi til højre. Så vi ser node for 34, og vi igen gå til højre. 89 er stadig større end 55, så fortsætter vi gå til højre. Vi derefter komme med en node med værdien af ​​144 og gå til venstre. Lo og beskue, 89 er lige der. 

En anden ting, vi kan gøre, er at udskrive alle numre ved at udføre en inorder traversal. En inorder traversal betyder at udskrive alt ud i venstre undertræ efterfulgt af trykning knudepunktet selv og derefter efterfulgt af trykning alt ud i højre undertræ. For eksempel, lad os tage vores foretrukne binær søgning træ og udskrive tallene i sorteret orden. Vi starter ved roden af ​​13, men inden udskrivning 13 vi er nødt til at udskrive alt i venstre undertræ. Så vi går til 5. Vi har stadig nødt til at gå dybere ned i træet, indtil vi finder den længst til venstre knudepunkt, hvilket er nul. Efter udskrivning nul, går vi tilbage op til 1, og udskrive denne ud. Så går vi til højre undertræ, der er 2, og udskrive det ud. Nu, hvor vi er færdig med at undertræ, vi kan gå tilbage op til 3, og printe det ud. Fortsætter op igen, vi udskriver 5 og derefter 8. Nu, hvor vi har afsluttet hele venstre undertræ, vi kan printe ud de 13 og begynde at arbejde på højre undertræ. Vi hopper ned til 34, men inden udskrivning 34 vi er nødt til at udskrive sin venstre undertræ. Så vi udskrive 21, så vi kommer til at printe ud 34 og besøge sin ret undertræ. Siden 55 har ikke nogen venstre undertræ, vi printe den ud og fortsætte til sin ret undertræ. 144 har en venstre undertræ, og så vi udskrive 89, efterfulgt af 144, og endelig den yderste højre knudepunkt 233. Der har du det, alle de tal udskrives i rækkefølge fra laveste til højeste. 

Tilføjelse noget til træet er relativt smertefri så godt. Alt, hvad vi skal gøre, er at sikre, at vi følger 3 binære søgetræ egenskaber og derefter indsætte den værdi, hvor der er plads. Lad os sige, at vi ønsker at indsætte værdien af ​​7. Siden 7 er mindre end 13, vi går til venstre. Men det er større end 5, så vi krydser til højre. Da det er mindre end 8 og 8 er et blad node, tilføjer vi 7 til venstre barn af 8. Voila! Vi har tilføjet en række til vores binær søgning træ. 

Hvis vi kan tilføje ting, vi bedre kunne slette tingene så godt. Desværre for os, sletning er en lille smule mere kompliceret - ikke meget, men bare en lille smule. Der er 3 forskellige scenarier, som vi er nødt til at overveje når du sletter elementer fra binære søgetræer. For det første er den letteste sagen er, at elementet er et blad node. I dette tilfælde, skal du blot sletter vi det og gå videre med vores forretning. Sige at vi vil slette de 7, som vi lige har tilføjet. Tja, vi simpelthen finde det, fjerne det, og det er det. Den næste sag er, hvis knudepunkt har kun 1 barn. Her kan vi slette den knude, men vi først nødt til at sørge at forbinde undertræ der er nu overladt forældreløse til den forælder af den node vi netop slettet. Sige at vi vil slette 3 fra vores træ. Vi tager barnet element i denne knude, og fastgør den til den forælder, for node. I dette tilfælde vil vi nu fastgørelse af 1 til 5. Dette fungerer uden problemer, fordi vi ved, ifølge den binære søgetræ egenskaben, at alt i den venstre undertræ af 3 var mindre end 5. Nu, 3 's undertræ er taget sig af, kan vi slette det. Den tredje og sidste sag er den mest komplekse. Dette er tilfældet, når knuden vi ønsker at slette har 2 børn. For at kunne gøre dette, skal vi først nødt til at finde den knude, der har den næststørste værdi, bytte de to, og derefter slette den node i spørgsmålet. Bemærk den knude, der har den næststørste værdi kan ikke have 2 børn selv siden den venstre barn ville være en bedre kandidat til den næststørste. Derfor sletter en node med 2 børn svarer til swapping af 2 knuder, og derefter slette varetages af 1 af de 2 førnævnte regler. For eksempel sige, lad os vi ønsker at slette roden node, 13. Det første vi gør, er at vi finder den næststørste værdi i træet som i dette tilfælde er 21. Vi så bytte de 2 knuder, hvilket gør 13 et blad og 21 den centrale gruppe node. Nu kan vi blot slette 13. 

Som omtalt tidligere, er der mange muligheder for at gøre en gyldig binær søgning træ. Desværre for os, nogle er værre end andre. For eksempel sker det, når vi bygger et binært søgetræ fra en sorteret liste over numre? Alle numre er lige tilføjet til højre på hvert trin. Når vi ønsker at søge efter et nummer, vi har ikke noget valg, men kun for at se på højre ved hvert trin. Dette er ikke bedre end lineær søgning på alle. Selv om vi ikke vil dække dem her, der er andre, mere komplekse, datastrukturer, der gør sikker på, at dette ikke sker. Men en enkelt ting, der kan gøres for at undgå dette er til bare tilfældigt shuffle inputværdierne. Det er højst usandsynligt, at ved tilfældig chance en blandet liste af tal er sorteret. Hvis dette var tilfældet, ville kasinoer ikke bo i business for længe. 

Der har du det. Nu ved du om binær søgning og binær søgning træer. Jeg Patrick Schmid, og dette er CS50. [CS50.TV] En oplagt måde ville være at scanne listen fra ... [bip] ... Antallet af elementer ... yep [Griner] ... Sende knudepunkt 234 ... augh. >> Yay! Det var -