[Powered by Google Translate] [Binär sökning]
[Patrick Schmid - Harvarduniversitetet]
[Detta är CS50. - CS50.TV]
>> Om jag gav dig en lista med Disney tecken namn i alfabetisk ordning
och bad dig att hitta Musse Pigg,
hur skulle du gå om att göra detta?
Ett självklart sätt skulle vara att skanna listan från början
och kontrollera varje namn för att se om det är Mickey.
Men när du läser Aladdin, Alice, Ariel, och så vidare,
du kommer snabbt att inse att starta längst fram i listan inte var en bra idé.
Okej, kanske du borde börja arbeta bakåt från slutet av listan.
Nu kan du läsa Tarzan, Stitch, Snövit, och så vidare.
Ändå verkar det inte som det bästa sättet att gå till väga.
>> Tja, är ett annat sätt att du kan gå om att göra detta för att försöka begränsa
listan med namn som du måste titta på.
Eftersom du vet att de är i alfabetisk ordning,
du kan bara titta på namnen i mitten av listan
och kontrollera om Musse Pigg är före eller efter detta namn.
Man tittar på efternamn i den andra kolumnen
du skulle inse att M för Mickey kommer efter J för Jasmine,
så du skulle helt enkelt ignorera den första halvan av listan.
Då skulle du förmodligen titta på toppen av den sista kolumnen
och se att det börjar med Rapunzel.
Mickey kommer före Rapunzel, ser ut som vi kan ignorera den sista kolumnen också.
Fortsatt sökstrategi, ser du snabbt att Mickey
är i den första hälften av den återstående listan med namn
och slutligen hitta Mickey gömmer mellan Merlin och Mimmi.
>> Vad du gjorde var i princip binär sökning.
Eftersom detta namn antyder, utför den sin sökning strategi i en binär fråga.
Vad betyder det här?
Tja, få en lista över sorterade poster, gör den binära sökalgoritmen en binär beslut -
vänster eller höger, större än eller mindre än, alfabetiskt före eller efter - vid varje punkt.
Nu när vi har ett namn som går längs med denna sökalgoritm,
låt oss titta på ett annat exempel, men den här gången med en lista över sorterade nummer.
Säg att vi letar efter numret 144 i listan över sorterade nummer.
Precis som tidigare, finner vi det nummer som är i mitten -
som i detta fall är 13 - och se om 144 är större än eller mindre än 13.
Eftersom det är klart större än 13, kan vi ignorera allt som är 13 eller mindre
och bara koncentrera sig på den återstående hälften.
Eftersom vi nu har ett jämnt antal artiklar kvar,
Vi väljer helt enkelt ett nummer som ligger nära mitten.
I det här fallet väljer vi 55.
Vi kunde ha lika lätt valt 89.
Okej. Återigen är 144 större än 55, så vi går till höger.
Lyckligtvis för oss, är nästa mellersta nummer 144,
den vi letar efter.
Så för att hitta 144 med hjälp av en binär sökning, vi kan hitta den i bara 3 steg.
Om vi ​​skulle ha använt linjär sökning här skulle det ha tagit oss 12 steg.
I själva verket, eftersom denna sökmetod halverar antalet objekt
det har att titta på vid varje steg, kommer det att hitta objektet den söker efter
ungefär i logaritmen av antalet objekt i listan.
Nu när vi har sett 2 exempel, låt oss ta en titt på
vissa pseudokod för en rekursiv funktion som implementerar binär sökning.
Börjar på toppen ser vi att vi måste hitta en funktion som tar 4 argument:
nyckel, array, min och max.
Nyckeln är det nummer som vi söker, så 144 i föregående exempel.
Array är en lista över nummer som vi söker.
Min och max är index för de lägsta och högsta positioner
att vi för närvarande tittar på.
Så när vi börjar, kommer min vara noll och max blir den maximala indexet i arrayen.
När vi begränsa sökningen ner kommer vi att uppdatera min och max
bara vara det område som vi fortfarande ser i.
>> Låt oss hoppa till den intressanta delen först.
Det första vi gör är att hitta mittpunkten,
det index som är halvvägs mellan min och max för den array som vi fortfarande överväger.
Sedan tittar vi på värdet av uppsättningen på den mittpunkt plats
och se om det antal som vi söker är mindre än den nyckeln.
Om antalet på den positionen är mindre,
då betyder det nyckeln är större än alla siffror till vänster om den positionen.
Så vi kan kalla binär sökfunktionen igen,
men denna gång uppdatera min och parametrar max för att läsa bara halv
som är större än eller lika med det värde vi bara tittat på.
Å andra sidan, om nyckeln är mindre än antalet vid den aktuella mittpunkten av arrayen,
vi vill gå åt vänster och ignorera alla nummer som är större.
Återigen, vi kallar binär sökning men denna gång med olika min och max uppdaterad
att inkludera bara den nedre halvan.
Om värdet vid den aktuella mittpunkten i arrayen är varken
större än eller mindre än nyckeln, då måste det vara lika med nyckeln.
Således kan vi återvända enkelt den aktuella mittpunkten index och vi är klara.
Slutligen är denna kontroll här fallet att antalet
är faktiskt inte i matris med tal som vi söker.
Om den maximala index intervallet som vi söker
är någonsin mindre än den minsta, innebär att vi har gått för långt.
Eftersom antalet inte var i inputuppställningen, återvänder vi -1
för att indikera att ingenting hittades.
>> Du kanske har märkt att detta algoritm ska fungera,
listan över nummer måste sorteras.
Med andra ord kan vi bara hitta 144 med binär sökning
om alla talen är ordnade från lägsta till högsta.
Om detta inte vore fallet, skulle vi inte kunna utesluta hälften av siffrorna i varje steg.
Så vi har 2 alternativ.
Antingen kan vi ta en osorterad lista och sortera den innan du använder binär sökning,
eller så kan vi se till att listan över nummer sorteras som vi lägga till siffror till det.
I stället för att sortera just när vi måste söka,
varför inte hålla listan sorteras hela tiden?
>> Ett sätt att hålla en lista med tal sorteras samtidigt tillåter
en för att lägga till eller flytta nummer från den här listan
är att använda något som kallas en binär sökträd.
En binär sökträdet är en datastruktur som har 3 egenskaper.
Det första innehåller den vänstra underträd någon nod endast värden som är mindre än
eller lika med nodens värde.
Det andra, innehåller rätt underträdet av en nod endast värden som är större än
eller lika med nodens värde.
Och slutligen både vänster och höger underträd av alla noder
är också binära sökträd.
Låt oss titta på ett exempel med samma nummer som vi använt tidigare.
För dig som aldrig har sett en datavetenskap träd innan,
Låt mig börja med att berätta att en datavetenskap träd växer nedåt.
Ja, till skillnad från träd du är van vid,
roten av en datavetenskap träd är överst,
och bladen är i botten.
Varje liten ruta kallas en nod, och noderna är förbundna med varandra genom kanterna.
Så roten till detta träd är en nod värde med värdet 13,
som har 2 barn noder med värdena 5 och 34.
En underträd är trädet som bildas genom att bara titta på en underavdelning av hela trädet.
>> Till exempel, är den vänstra underträd av noden 3 trädet skapas av noderna 0, 1, och 2.
Så, om vi går tillbaka till egenskaperna hos en binärt sökträd,
Vi ser att varje nod i trädet uppfyller alla 3 egenskaper, nämligen,
vänster underträd innehåller endast värden som är mindre än eller lika med nodens värde;
högra underträdet av alla noder
endast innehåller värden som är större än eller lika med nodens värde, och
både vänster och höger underträd av alla noder är också binära sökträd.
Även detta träd ser annorlunda, är detta en giltig binärt sökträd
för samma uppsättning siffror.
I själva verket finns det många olika sätt som du kan skapa
en giltig binärt sökträd från dessa siffror.
Nåväl, låt oss gå tillbaka till den första vi skapade.
Så vad kan vi göra med dessa träd?
Tja, vi kan mycket enkelt hitta de lägsta och högsta värdena.
De minimivärden kan hittas genom att alltid gå till vänster
tills det inte finns fler noder att besöka.
Omvänt, för att hitta den maximala ett helt enkelt går ner till höger vid varje tidpunkt.
>> Hitta något annat nummer som inte är det minsta eller högsta
är lika enkelt.
Säg att vi letar efter numret 89.
Vi kontrollerar bara värdet av varje nod och gå till vänster eller höger,
beroende på om nodens värde är mindre än eller större än
den vi letar efter.
Så börjar vid roten av 13 ser vi att 89 är större,
och så går vi till höger.
Sedan ser vi nod för 34, och igen vi gå till höger.
89 är fortfarande större än 55, så vi fortsätter att gå till höger.
Vi kommer sedan upp med en nod med värdet av 144 och gå till vänster.
Hör och häpna, 89 är rätt där.
>> En annan sak som vi kan göra är att skriva ut alla nummer genom att utföra en inorder förflyttning.
En inorder förflyttning innebär att skriva ut allt i den vänstra underträd
följd av tryckning själva noden
och sedan följt av tryckning allt ut i rätt underträd.
Till exempel, låt oss ta vår favorit träd binär sökning
och skriva ut numren i sorterad ordning.
Vi börjar vid roten av 13, men innan du skriver ut 13 måste vi skriva ut
allt i vänstra underträd.
Så vi går till 5. Vi måste fortfarande gå djupare ner i trädet tills vi hittar längst till vänster nod,
vilket är noll.
Efter utskrift noll, går vi tillbaka upp till 1 och skriva ut det.
Sen går vi åt höger underträd som är 2, och skriva ut det.
Nu när vi är klara med det underträd,
vi kan gå tillbaka till 3 och skriva ut den.
Fortsätter tillbaka upp, ut vi 5 och sedan 8.
Nu när vi har avslutat hela vänster underträd,
Vi kan skriva ut 13 och börja arbeta på rätt underträd.
Vi hoppa ner till 34, men innan du skriver ut 34 måste vi skriva ut sin vänstra underträd.
Så vi skriver ut 21, då får vi skriva ut 34 och besöka sin rätt underträd.
Sedan 55 har ingen vänstra underträd, skriva vi det och fortsätter till dess högra delträd.
144 har en vänster underträd, så vi skriver ut 89, följt av 144,
och slutligen längst till höger nod 233.
Där har du det, alla nummer skrivs ut i ordning från lägsta till högsta.
>> Lägga något till trädet är relativt smärtfritt också.
Allt vi behöver göra är att se till att vi följer 3 binära egenskaper sökträd
och sätt sedan in värdet där det finns utrymme.
Låt oss säga att vi vill infoga värdet 7.
Sedan 7 är mindre än 13, går vi till vänster.
Men det är större än 5, så vi korsar till höger.
Eftersom det är mindre än 8 och 8 är en lövnod lägger vi 7 till vänster barn 8.
Voila! Vi har lagt ett nummer till vår binära sökträd.
>> Om vi ​​kan lägga saker, att vi bättre kan ta bort saker också.
Tyvärr för oss, är att ta bort lite mer komplicerat -
inte mycket, men bara lite.
Det finns 3 olika scenarion som vi måste överväga
när du tar bort element från binära sökträd.
Först, är det enklaste fallet att elementet är en lövnod.
I det här fallet, ta bort vi bara den och gå vidare med vår verksamhet.
Säg att vi vill ta bort 7 som vi just lagt.
Tja, vi helt enkelt hitta den, ta bort den, och det är det.
Nästa fallet är om noden har endast 1 barn.
Här kan vi ta bort noden, men vi måste först se till att
att ansluta underträd som nu lämnas föräldralösa
till överordnade noden vi bort bara.
Säg att vi vill ta bort 3 från vår träd.
Vi tar barnet del av denna nod och bifoga det till den förälder av noden.
I det här fallet, vi fästa nu 1 till 5.
Detta fungerar utan problem eftersom vi vet, enligt binära sökträdet egendom,
att allt i vänstra delträd av 3 var mindre än 5.
Nu när 3: s underträd tas om hand, kan vi ta bort den.
Den tredje och sista fallet är den mest komplicerade.
Detta är fallet när noden vi vill ta bort har 2 barn.
För att göra detta måste vi först hitta noden som har den största värdet,
byta två, och sedan ta bort noden i fråga.
Lägg märke till nod som har den största värdet inte kan ha 2 barn själv
eftersom dess vänstra barn skulle vara en bättre kandidat för den näst största.
Därför, ta bort en nod med 2 barn uppgår till byta av 2 noder,
och sedan ta bort sköts av 1 av de 2 ovan nämnda reglerna.
Till exempel, låt oss säga att vi vill ta bort rotnoden, 13.
Det första vi gör är att vi hittar den näst största värdet i trädet
som i detta fall, är 21.
Vi byter sedan 2 noder, vilket 13 ett blad och 21 den centrala gruppen nod.
Nu kan vi helt enkelt ta bort 13.
>> Som nämndes tidigare, det finns många möjliga sätt att göra en giltig träd binär sökning.
Tyvärr för oss, vissa är värre än andra.
Till exempel, vad händer när vi bygger ett binärt sökträd
från en sorterad lista med nummer?
Alla siffror är bara till höger vid varje steg.
När vi vill söka efter ett nummer,
Vi har inget annat val än bara titta på rätt vid varje steg.
Detta är inte bättre än linjär sökning alls.
Även om vi inte kommer att täcka dem här, det finns andra, mer komplexa,
datastrukturer som ser till att detta inte sker.
Men en enkel sak som kan göras för att undvika detta
att bara slumpmässigt blanda de ingående värdena.
Det är högst osannolikt att genom slumpen en blandad lista med nummer sorteras.
Om så vore fallet, skulle kasinon inte stanna i affärer för länge.
>> Där har ni det.
Du vet nu om binär sökning och binära träd sökning.
Jag Patrick Schmid, och detta är CS50.
[CS50.TV]
Ett självklart sätt skulle vara att skanna listan från ... [pip]
... Antalet objekt ... Japp
[Skrattar]
... Post nod 234 ... augh.
>> Yay! Det var -