[Powered by Google Translate] [Cautare binară]
[Patrick Schmid - Universitatea Harvard]
[Acest lucru este CS50. - CS50.TV]
>> Dacă ți-am dat o listă de nume de caractere Disney, în ordine alfabetică
și ți-a cerut să găsească Mickey Mouse,
cum ai de gând să faci asta?
Un mod evident ar fi de a scana si lista de la început
și să verificați fiecare nume pentru a vedea dacă e Mickey.
Dar, așa cum ai citit Aladdin, Alice, Ariel, și așa mai departe,
iti vei da seama repede că începând de la partea din față a listei nu a fost o idee bună.
Bine, poate că ar trebui să înceapă lucrul înapoi de la sfârșitul listei.
Acum ai citit Tarzan, Stitch, Alba ca Zapada, și așa mai departe.
Totusi, acest lucru nu pare ca cel mai bun mod de a merge despre asta.
>> Ei bine, un alt mod de faptul că ați putea merge despre a face acest lucru este de a încerca pentru a restrânge
lista de nume pe care va trebui să se uite la.
Din moment ce știu că sunt în ordine alfabetică,
ai putea uita doar la numele în mijlocul listei
și verificați dacă Mickey Mouse este înainte sau după acest nume.
Privind la numele de familie, în coloana a doua
vei realiza că M pentru Mickey vine dupa J pentru Jasmine,
asa ca ar fi pur și simplu ignorați prima jumătate a listei.
Apoi te-ai uita, probabil, în partea de sus a coloanei ultimei
și vezi că începe cu Rapunzel.
Mickey vine inainte de Rapunzel, arata ca putem ignora ultima coloana, de asemenea.
Continuând strategia de căutare, veți vedea repede că Mickey
este în prima jumătate a listei de nume rămase
și de a găsi în cele din urmă Mickey ascuns între Merlin și Minnie.
>> Ce ai făcut a fost practic căutare binară.
Deoarece această sugereaza si numele, aceasta efectuează strategia de căutare într-o chestiune binar.
Ce înseamnă?
Ei bine, având în vedere o listă de articole sortate, algoritmul de cautare binara face o decizie binar -
la stânga sau la dreapta, mai mare sau mai mică, în ordine alfabetică înainte sau după - la fiecare punct.
Acum, că avem un nume, care merge impreuna cu acest algoritm de căutare,
să ne uităm la un alt exemplu, dar de data aceasta cu o listă de numere sortate.
Spune cautam pentru numărul 144 în această listă de numere sortate.
La fel ca înainte, vom găsi numărul care este în mijlocul -
care în acest caz este de 13 - 144 și a vedea dacă este mai mare sau mai mică de 13.
Din moment ce este în mod evident mai mare de 13, putem ignora tot ceea ce este de 13 sau mai putin
și să se concentreze doar pe jumătatea rămasă.
Din moment ce avem acum un numar par de elemente plecat,
vom alege pur și simplu un număr care este aproape de mijloc.
În acest caz, vom alege 55.
Am fi putut la fel de ușor de ales 89.
Bine. Din nou, 144 este mai mare decât 55 de ani, asa ca du-te la dreapta.
Din fericire pentru noi, numărul de mijloc următoare este 144,
cel pe care îl căutăm.
Deci, în scopul de a găsi 144 utilizând o căutare binară, suntem în măsură să-l găsească în doar 3 pași.
Dacă ne-ar fi folosit de căutare liniară aici, ne-ar fi luat 12 etape.
Ca o chestiune de fapt, deoarece această metodă de căutare reprize la numărul de articole
are să se uite puțin la fiecare pas, ea va găsi elementul care este în căutarea
în legătură cu jurnalul de numărul de elemente din listă.
Acum, că ne-am văzut 2 exemple, haideți să aruncăm o privire la
unele pseudocod pentru o funcție recursivă care pune în aplicare cautare binara.
Începând de la partea de sus, vedem că trebuie să găsim o funcție care ia 4 argumente:
cheie, matrice, min, si max.
Cheia este numărul pe care îl căutați, deci 144 în exemplul anterior.
Array este lista de numere pe care le căutați.
Min și max sunt indicii ale pozițiilor minime și maxime
că suntem în prezent în căutarea de la.
Deci, atunci când vom începe, min va fi zero si maxim va fi indicele maxim de matrice.
Așa cum am restrânge căutarea în jos, vom actualiza min și max
să fie doar intervalul pe care suntem încă în căutarea inch
>> Să trece la partea interesantă primul.
Primul lucru pe care facem este să găsească punctul de mijloc,
indicele care este la jumătatea distanței dintre min si max de matrice pe care suntem încă în considerare.
Apoi ne uităm la valoarea de matrice de la acea locație punctul de mijloc
și a vedea dacă numărul pe care îl căutați este mai mică decât cea cheie.
În cazul în care numărul de la această poziție este mai puțin,
atunci înseamnă că cheia este mai mare decât toate numerele de la stânga această poziție.
Deci, putem apela funcția de căutare binară, din nou,
dar de data aceasta actualizarea min și max parametrii pentru a citi doar jumătate
care este mai mare sau egală cu valoarea ne-am uitat la.
Pe de altă parte, în cazul în care cheia este mai mic decât numărul de la punctul de mijloc curent de matrice,
vrem să mergem la stânga și ignora toate numerele care sunt mai mari.
Din nou, noi numim binar de căutare, dar de data aceasta cu gama de min max și actualizate
pentru a include doar jumătatea inferioară.
În cazul în care valoarea de la punctul de mijloc curentă în matrice nu este nici
mai mare decât nici mai mică decât cheia, atunci acesta trebuie să fie egală cu cheia.
Astfel, ne putem întoarce pur și simplu indicele mijloc curent, și am terminat.
În cele din urmă, această verificare este aici pentru cazul în care numărul de
nu este de fapt în matrice de numere cautam.
În cazul în care indicele maxim din gama pe care le căutați
este tot mai puțin decât minimul, ceea ce înseamnă că ne-am mers prea departe.
Deoarece numărul nu a fost în matrice de intrare, ne întoarcem -1
pentru a indica faptul că nimic nu a fost găsit.
>> Este posibil să fi observat că, pentru acest algoritm pentru a lucra,
lista de numere trebuie să fie sortate.
Cu alte cuvinte, putem găsi numai 144 folosind cautare binara
în cazul în care toate numerele sunt ordonate de la cel mai mic la cel mai mare.
Dacă acest lucru nu a fost cazul, nu am fi în măsură să excludă jumătate din numerele de la fiecare pas.
Deci avem 2 opțiuni.
Fie putem lua o listă nesortate și sorta-l înainte de a utiliza căutare binară,
sau putem să ne asigurăm că lista de numere este sortată după cum vom adăuga numere la ea.
Astfel, în loc de sortare doar atunci când avem de a căuta,
de ce nu ține lista sortată în orice moment?
>> O modalitate de a păstra o listă de numere sortată în același timp permițând
o să adăugați sau mutați numerele din această listă
este prin utilizarea ceva numit un arbore binar de căutare.
Un arbore binar de căutare este o structură de date care are 3 proprietati.
În primul rând, subarborele stâng al oricărui nod conține numai valorile care sunt mai puțin
sau egală cu valoarea nodului.
În al doilea rând, dreptul subarbore al unui nod conține doar valori care sunt mai mari decât
sau egală cu valoarea nodului.
Și, în sfârșit, atât subarbori stânga și din dreapta ale tuturor nodurilor
sunt, de asemenea, arbori binari de căutare.
Să ne uităm la un exemplu, cu aceleași numere le-am folosit mai devreme.
Pentru cei dintre voi care nu au văzut un copac computer înainte de stiinta,
permiteți-mi să încep prin a vă spune că un copac informatică crește în jos.
Da, spre deosebire de copaci v-ați obișnuit să,
rădăcina unui copac informatică este în partea de sus,
și frunzele sunt în partea de jos.
Fiecare cutie mica se numeste un nod, iar nodurile sunt conectate între ele prin muchii.
Deci, rădăcina acestui arbore este o valoare nod cu valoarea 13,
care are 2 copii cu noduri valorile 5 și 34.
Un subarbore este copac care este format doar uitandu-te la o subsecțiune a tot arborele.
>> De exemplu, subarbore stâng al nodului 3 este arborele creat de la 0, 1, noduri și 2.
Deci, dacă ne întoarcem la proprietățile unui arbore binar de căutare,
vedem că fiecare nod din arbore conform cu toate cele 3 proprietăți, și anume,
subarbore stânga conține numai valori care sunt mai mici sau egale cu valoarea nodului;
dreptul subarbore al tuturor nodurilor
conține numai valori care sunt mai mari sau egale cu valoarea nodului; și
subarbori atât stânga și dreapta ale tuturor nodurilor, de asemenea, sunt copaci de căutare binare.
Deși acest copac arată diferit, acest lucru este valabil un arbore binar de căutare
pentru același set de numere.
Ca o chestiune de fapt, există multe moduri posibile pe care le puteți crea
o adresă validă de căutare arbore binar de la aceste numere.
Ei bine, hai să ne întoarcem la primul am creat.
Deci, ce putem face cu aceste copaci?
Ei bine, putem foarte simplu găsi valorile minime și maxime.
Valorile minime pot fi găsite de către întotdeauna merge spre stânga
până când nu există noduri nu mai pentru a vizita.
În schimb, pentru a găsi cea maximă pur și simplu doar se duce în jos la dreapta, la fiecare dată.
>> Găsirea orice alt număr care nu este minim sau maxim
este la fel de ușor.
Spune-ne ce cautati numarul 89.
Noi verificam pur și simplu valoarea fiecărui nod și du-te la stânga sau la dreapta,
în funcție de valoarea nodului este mai mică sau mai mare decât
cel pe care îl căutăm.
Deci, pornind de la rădăcina de 13, vom vedea că 89 este mai mare,
și astfel vom merge la dreapta.
Apoi vom vedea nodul de 34, și din nou mergem la dreapta.
89 este încă mai mare decât 55 de ani, asa ca va continua spre dreapta.
Am venit apoi cu un nod cu valoarea de 144 și du-te la stânga.
Lo și iată, 89 este chiar acolo.
>> Un alt lucru pe care îl putem face este imprima toate numerele de efectuarea unei traversarea inorder.
O traversare inorder înseamnă totul pentru a imprima în subarborele stâng
urmată de imprimare nodul în sine
și apoi urmată de imprimarea totul în dreapta subarbore.
De exemplu, să luăm nostru favorit arbore binar de căutare
și imprima numerele în ordine sortată.
Vom începe de la rădăcina de 13, dar înainte de imprimare 13 trebuie să imprime
totul în subarborele stâng.
Deci, mergem la 5. Noi încă mai trebuie să meargă mai adânc în arborele până când vom găsi cea mai din stânga nod,
care este zero.
După imprimare de zero, vom merge înapoi până la 1 și a imprima asta.
Apoi vom merge la subarborele drept, care este 2, și imprima asta.
Acum că am terminat cu asta subarborele,
putem merge înapoi până la 3 și imprimați-l.
Continuând back-up, am imprima 5 și apoi 8.
Acum, că ne-am completat tot subarborele stânga,
putem imprima 13 și începe să lucreze la dreapta subarbore.
Am hop până la 34 de ani, dar înainte de imprimare 34 trebuie să imprime subarbore stânga sa.
Așa că am tipări 21; apoi vom ajunge să imprime 34 și vizita de dreptul său de subarborele.
Din moment ce 55 nu are subarbore stâng, l-am tipăriți și să continue pe subarbore drept al acestuia.
144 are un subarbore stâng, și așa am imprima 89, urmat de 144,
și, în final nodul dreapta-cea mai mare de 233.
Nu-l ai, toate numerele sunt imprimate în ordine de la cel mai mic la cel mai mare.
>> Adăugarea ceva de copac este relativ nedureroasa, de asemenea.
Tot ce trebuie să faceți este să vă asigurați că urmăm 3 Proprietăți de căutare binare copac
și apoi introduceți valoarea în cazul în care există spațiu.
Să spunem că doriți să introduceți valoarea de 7.
Deoarece 7 este mai mic de 13, mergem la stânga.
Dar e mai mare de 5, asa ca am traversare la dreapta.
Deoarece este mai mică de 8 și 8 este un nod frunză, se adaugă 7 la copilul stânga 8.
Voila! Am adăugat un număr la arbore binar nostru de cautare.
>> Dacă putem adăuga lucruri, vom fi mai în măsură să ștergeți lucrurile la fel de bine.
Din nefericire pentru noi, ștergerea este un pic mai complicată -
nu de mult, dar doar un pic.
Există 3 scenarii diferite care trebuie să le ia în considerare
atunci când ștergeți elemente din arborii de căutare binare.
În primul rând, cel mai simplu caz este faptul că elementul este un nod frunză.
În acest caz, vom șterge pur și simplu și du-te mai departe cu afacerea noastră.
Spune că vrem să ștergeți 7 pe care tocmai l-am adăugat.
Ei bine, am găsit pur și simplu, scoateți-l, și asta e tot.
Următorul caz este daca nodul are doar 1 copil.
Aici putem șterge nodul, dar mai întâi trebuie să ne asigurăm
pentru a conecta subarborelui care este acum lăsat fără părinți
la mamă a nodului ne-am șters.
Spune că vrem să ștergeți 3 de la copacul nostru.
Ne ia copilul elementul de acel nod și atașați-l la mamă a nodului.
În acest caz, suntem acum atașarea de la 1 la 5.
Aceasta funcționează fără nici o problemă pentru că știm, în funcție de copac binar de căutare de proprietate,
că totul în subarborele stâng al 3 a fost mai mică de 5.
Acum, că a subarborelui 3 este ocupat de, putem sterge.
Caz treia și ultima este cel mai complex.
Acesta este cazul atunci când nodul vrem să ștergeți are 2 copii.
În scopul de a face acest lucru, trebuie mai întâi să găsească nod care are cea mai mare valoare următoare,
schimba doi, iar apoi ștergeți nodul în cauză.
Observați nodul care are cea mai mare valoare următoare nu poate avea 2 copii în sine
de la copilul său din stânga ar fi un candidat mai bun pentru cea mai mare următoare.
De aceea, ștergerea unui nod cu 2 copii se ridică la schimbarea de 2 noduri,
și apoi ștergerea este manipulat de 1 din cele 2 regulilor menționate mai sus.
De exemplu, să spunem că doriți să ștergeți nodul rădăcină, 13.
Primul lucru ce facem este găsim valoarea următoare cea mai mare în structura
care, în acest caz, este de 21.
Noi swap cele 2 noduri, făcând o frunză 13 și 21 nodul central de grup.
Acum putem șterge pur și simplu 13.
>> În ceea ce a făcut aluzie la mai devreme, există multe moduri de a face posibile valid arbore binar de căutare.
Din nefericire pentru noi, unele sunt mai rău decât altele.
De exemplu, ce se întâmplă atunci când ne construim un arbore binar de căutare
dintr-o listă sortată de numere?
Toate numerele sunt doar adaugă la dreapta la fiecare pas.
Când ne-am dori pentru a căuta un număr,
nu avem de ales, ci doar să se uite la dreapta, la fiecare pas.
Acest lucru nu este mai bună decât căutarea liniară, la toate.
Desi nu le vom acoperi aici, există și alte, mult mai complexe,
structuri de date care fac sigur că acest lucru nu se întâmplă.
Cu toate acestea, un lucru simplu care poate fi făcut pentru a evita acest lucru este
la doar shuffle aleatoriu valorile de intrare.
Este foarte puțin probabil ca prin întâmplare o listă de numere amestecate este sortat.
Dacă acesta ar fi cazul, cazinourile nu ar rămâne în afaceri pentru mult timp.
>> Nu-l ai.
Acum știi despre căutarea binară și copaci de căutare binare.
Sunt Patrick Schmid, iar acest lucru este CS50.
[CS50.TV]
Un mod evident ar fi de a scana lista de la ... [bip]
... Numărul de articole ... yep
[Râde]
... Posta nod de 234 ... augh.
>> Yay! Asta a fost -