[Powered by Google Translate] [Recerca binària]
[Patrick Schmid - Harvard University]
[Aquesta és CS50. - CS50.TV]
>> Si et dono una llista dels noms dels personatges de Disney en ordre alfabètic
i li va demanar que trobés Mickey Mouse,
Com anar fent això?
Una manera òbvia seria per escanejar la llista des del principi
i verificar cada nom per veure si és Mickey.
Però a mesura que llegeix Aladdin, Alice, Ariel, i així successivament,
aviat et donaràs compte que a partir de la part davantera de la llista no era una bona idea.
Bé, potser hauria de començar a treballar cap enrere des del final de la llista.
Ara vostè llegir Tarzan, Stitch, Blancaneus, i així successivament.
No obstant això, això no sembla la millor manera d'anar-hi.
>> Bé, una altra forma en què vostè pot anar sobre fer això és intentar reduir
la llista de noms que s'ha de mirar.
Ja que vostè sap que ells estan en ordre alfabètic,
vostè podria mirar als noms en la meitat de la llista
i comprovar si Mickey Mouse és abans o després d'aquest nom.
Mirant el cognom a la segona columna
t'adonaries que M per Mickey ve després de J per Jasmine,
pel que simplement em ignoren la primera meitat de la llista.
Llavors probablement veuria a la part superior de l'última columna
i veure que comença amb Rapunzel.
Mickey ve abans de Rapunzel, sembla que podem passar per alt l'última columna també.
Continuant amb l'estratègia de recerca, que dóna gust veure que Mickey
és a la primera meitat de la llista restant de noms
i, finalment, trobar Mickey amagat entre Merlí i Minnie.
>> El que acabes de fer és buscar bàsicament binari.
Com aquest nom indica, es porta a terme la seva estratègia de cerca en qüestió binari.
Què vol dir això?
Doncs bé, donada una llista d'elements ordenats, l'algorisme de recerca binària pren una decisió binària -
esquerra o cap a la dreta, més gran que o més petit que, alfabèticament abans o després - en cada punt.
Ara que tenim un nom que va juntament amb aquest algorisme de recerca,
Vegem un altre exemple, però aquest cop amb una llista de nombres ordenats.
Diguem que estem buscant el número 144 en la llista de nombres ordenats.
Igual que abans, ens trobem amb el nombre que està al mig -
que en aquest cas és 13-144 i veure si és més o menys que 13.
Ja que és clarament superior a 13, es pot passar per alt tot el que és 13 o menys
i només es concentra en la meitat restant.
Com que ara tenim un nombre parell d'elements a l'esquerra,
simplement tria un nombre que és a prop del centre.
En aquest cas, vam triar 55.
Podríem haver triat la mateixa facilitat 89.
Bé. Un cop més, 144 és superior a 55, així que anem a la dreta.
Afortunadament per a nosaltres, el nombre central al costat és de 144,
la qual estem buscant.
Així que per trobar 144 mitjançant una recerca binària, podem trobar en només 3 passos.
Si haguéssim usat recerca lineal aquí, ens hauria pres 12 passos.
Com a qüestió de fet, ja que aquest mètode de recerca a la meitat el nombre d'articles
ha de mirar a cada pas, es troba l'article que està buscant
en aproximadament el log del nombre d'elements de la llista.
Ara que hem vist dos exemples, anem a fer una ullada a
alguns pseudocodi per a una funció recursiva que implementa la recerca binària.
Començant per la part superior, veiem que hem de trobar una funció que pren 4 arguments:
clau, array, min i max.
La clau és el nombre que estem buscant, així que 144 en l'exemple anterior.
Matriu és la llista dels nombres que estem buscant.
Min i max són els índexs de les posicions mínima i màxima
que actualment estem veient.
Així que quan vam començar, min serà zero i el màxim serà l'índex màxim de la matriu.
En reduir la recerca, actualitzarem min i max
a ser només el rang que encara estem mirant cap a dins
>> Anem a passar a la part interessant en primer lloc.
El primer que hem de fer és trobar el punt mig,
l'índex que està a mig camí entre el mínim i màxim de la matriu que encara estem considerant.
A continuació, ens fixem en el valor de la matriu de punt mitjà en aquest lloc
i veure si el nombre que estem buscant és menor que la clau.
Si el nombre en aquesta posició és menor,
llavors vol dir que la clau és més gran que tots els nombres a l'esquerra d'aquesta posició.
Així que podem trucar a la funció de cerca binària de nou,
però aquesta vegada l'actualització dels valors mínim i màxim dels paràmetres de llegir només la meitat
que és més gran que o igual al valor que acabem de veure.
D'altra banda, si la clau és menor que el nombre actual al punt mig de la matriu,
volem anar a l'esquerra i passar per alt tots els nombres que són majors.
Un cop més, fem una crida binari de recerca, però aquesta vegada amb la gamma de min i max actualització
per incloure només la meitat inferior.
Si el valor en el punt mitjà actual en la matriu no és ni
més gran que ni més petit que la clau, llavors ha de ser igual a la clau.
Per tant, podem simplement tornar l'índex actual punt mig, i ja està.
Finalment, aquesta comprovació aquí és per al cas que el nombre
no és en realitat en el conjunt de nombres que estem buscant.
Si l'índex màxim de la gamma que estem buscant
és sempre menor que el mínim, això vol dir que hem anat massa lluny.
Atès que el nombre no era a la matriu d'entrada, tornem -1
per indicar que no es va trobar res.
>> T'hauràs adonat que per aquest algorisme per treballar,
la llista de nombres ha de ser ordenats.
En altres paraules, només es pot trobar a la recerca binària 144
si tots els nombres estan ordenats de menor a major.
Si aquest no fos el cas, no seria capaç d'excloure mitjà dels nombres en cada pas.
Així que tenim dues opcions.
O es pot prendre una llista sense ordenar i classificar abans d'usar recerca binària,
o podem assegurar-nos que la llista de nombres s'ordenen com afegir números a la mateixa.
Així, en lloc de classificar en el moment en què hem de buscar,
¿Per què no mantenir la llista ordenada en tot moment?
>> Una manera de mantenir una llista de nombres ordenats alhora que permet
un per afegir o moure números d'aquesta llista
és l'ús d'alguna cosa que es diu un arbre de cerca binària.
Un arbre de recerca binari és una estructura de dades que té 3 propietats.
En primer lloc, el subarbre esquerre de qualsevol node conté només valors que són menors que
o igual que el valor del node.
En segon lloc, el subarbre dret d'un node només conté valors que són més grans que
o igual que el valor del node.
I, finalment, tant els subarbres esquerre i dret de tots els nodes
també són arbres binaris de cerca.
Vegem un exemple amb els mateixos números que fem servir abans.
Per a aquells de vostès que mai han vist un arbre abans de la informàtica,
m'ho dius a mi començar dient que un arbre de la informàtica creix cap avall.
Sí, a diferència dels arbres que estan acostumats,
l'arrel d'un arbre de la informàtica és a la part superior,
i les fulles estan a la part inferior.
Cada caixa petita s'anomena un node, i els nodes estan connectats entre si per les vores.
Així que l'arrel d'aquest arbre és un node de valor amb el valor 13,
que té 2 nodes fills amb els valors 5 i 34 anys.
Un subarbre és l'arbre que es forma amb només mirar una subsecció de tot l'arbre.
>> Per exemple, el subarbre esquerre del node 3 és l'arbre creat pels nodes 0, 1 i 2.
Així doncs, si ens remuntem a les propietats d'un arbre de cerca binària,
veiem que cada node de l'arbre s'ajusta a tots els 3 propietats, és a dir,
el subarbre esquerre només conté valors que són menors o iguals que el valor del node;
el subarbre dret de tots els nodes
només conté valors que són majors o iguals que el valor del node, i
subarbres esquerre i dret de tots els nodes també són arbres binaris de cerca.
Encara que aquest arbre es veu diferent, es tracta d'un arbre binari de cerca vàlid
per al mateix conjunt de nombres.
Com a qüestió de fet, hi ha moltes formes possibles que es poden crear
un arbre de recerca binari vàlid d'aquests nombres.
Bé, tornem a la primera que hem creat.
Llavors, què podem fer amb aquests arbres?
Bé, podem senzillament trobar els valors mínims i màxims.
Els valors mínims es pot trobar sempre va a l'esquerra
fins que no hi ha més nodes per visitar.
Per contra, per trobar el màxim simplement baixa a la dreta en cada moment.
>> Recerca de qualsevol altre nombre que no és el mínim o el màxim
és igual de fàcil.
Diguem que està buscant el número 89.
Nosaltres simplement comprovar el valor de cada node i vagi a l'esquerra oa la dreta,
depenent de si el valor del node és menor o major que
la qual estem buscant.
Així, a partir de l'arrel de 13, veiem que 89 és major,
i així ens anem a la dreta.
Després veiem el node de 34 anys, i una altra ens anem a la dreta.
89 és encara superior a 55, així que a seguir anant a la dreta.
A continuació, arribar a un node amb el valor de 144 i vagi a l'esquerra.
Però vet aquí que 89 és just allà.
>> Una altra cosa que podem fer és imprimir tots els nombres mitjançant la realització d'un recorregut en ordre.
Un recorregut en ordre significa per imprimir tot en el subarbre esquerre
seguit per la impressió del propi node
i després va seguir imprimint tot al subarbre dret.
Per exemple, prenguem el nostre arbre binari de cerca favorit
i imprimir els números en ordre.
Comencem a l'arrel de 13, però abans de la impressió 13 que ha d'imprimir
tot en el subarbre esquerre.
Així que ens anem a 5. Encara hem d'anar més avall en l'arbre fins a trobar el node més a l'esquerra,
que és zero.
Després de la impressió zero, tornar a pujar a la 1 i imprimir això.
Després anem al subarbre dret, que és 2, i imprimir això.
Ara que hem acabat amb aquest subarbre,
podem tornar a pujar a la 3 i imprimir-lo.
Continuant cap amunt, imprimim el 5 i després el 8.
Ara que hem completat tot el subarbre esquerre,
podem imprimir el 13 i començar a treballar en el subarbre dret.
Ens saltar fins a 34, però abans d'imprimir 34 hem de imprimir el seu subarbre esquerre.
Així que imprimir 21, llavors hem de imprimir 34 i visiti el seu subarbre dret.
Des de 55 no té subarbre esquerre, que l'imprimeixin i continuï amb la seva subarbre dret.
144 té un subarbre esquerre, i així d'imprimir la 89, seguit pel 144,
i, finalment, el node més a la dreta de 233.
Aquí el tenen, tots els nombres s'imprimeixen en ordre de menor a major.
>> Afegint alguna cosa que l'arbre és relativament sense dolor també.
Tot el que hem de fer és assegurar-nos seguir 3 propietats arbre de cerca binària
i després inserir el valor on hi ha espai.
Diguem que volem inserir el valor de 7.
Com 7 és menor que 13, ens anem a l'esquerra.
Però és més gran que 5, de manera que travessen a la dreta.
Com que és menys de 8 i 8 és un node fulla, s'afegeix 7 al fill esquerre de 8.
Voila! Hem afegit un nombre al nostre arbre de cerca binària.
>> Si podem afegir coses, és millor que ser capaç d'esborrar les coses tan bé.
Per desgràcia per a nosaltres, l'eliminació és una mica més complicat -
No és molt, però només una mica.
Hi ha 3 diferents escenaris que hem de considerar
en eliminar elements dels arbres binaris de cerca.
En primer lloc, el cas més senzill és que l'element és un node fulla.
En aquest cas, només ha d'esborrar i seguir amb el nostre negoci.
Diguem que vols eliminar el 7 que acaba d'afegir.
Bé, simplement ho troba, treure, i això és tot.
El següent cas és si el node té només 1 nen.
Aquí es pot eliminar el node, però primer hem d'assegurar
per connectar el subarbre que queda ara sense pares
el pare del node que acaba d'eliminar.
Diguem voler esborrar 3 del nostre arbre.
Prenem l'element fill d'aquest node i adjuntar-lo al pare del node.
En aquest cas, ara estem adjuntant la 1 a la 5.
Això funciona sense cap problema, perquè sabem, d'acord amb la propietat d'arbre binari de recerca,
que tot en el subarbre esquerre de 3 va ser inferior a 5.
Ara que el 3 de subarbre es cuida, es pot eliminar.
El tercer i últim cas és el més complex.
Aquest és el cas quan el node que voleu suprimir té 2 nens.
Per tal de fer això, primer ha de trobar el node que té el següent valor major,
canviar els dos, i després eliminar el node en qüestió.
Observeu el node que té el següent valor més gran no pot tenir 2 fills si
ja que el seu fill de l'esquerra seria un millor candidat per l'immediatament superior.
Per tant, l'eliminació d'un node amb 2 fills equival a 2 nodes d'intercanvi,
i esborrar està a càrrec d'una de les dues normes esmentades.
Per exemple, diguem que voleu eliminar el node arrel de 13.
El primer que fem és trobar el següent valor més gran en l'arbre
que, en aquest cas, és 21.
A continuació, canviar els 2 nodes, de manera que una fulla 13 i 21 el node del grup central.
Ara podem simplement esborrar 13.
>> Com es va esmentar anteriorment, hi ha moltes maneres possibles de fer un arbre binari de recerca vàlida.
Per desgràcia per a nosaltres, alguns són pitjors que altres.
Per exemple, què passa quan es construeix un arbre de cerca binària
a partir d'una llista ordenada de nombres?
Tots els números s'acaba d'afegir a la dreta en cada pas.
Quan volem buscar un nombre,
no tenim més remei que mirar a la dreta en cada pas.
Això no és millor que la recerca lineal en absolut.
Encara que no anem a cobrir aquí, hi ha altres, més complexes,
estructures de dades que asseguren que això no succeeixi.
No obstant això, una cosa simple que es pot fer per evitar-ho és
només a l'atzar a estudiar els valors d'entrada.
És molt poc probable que per l'atzar d'una llista de nombres estudien està ordenada.
Si aquest fos el cas, els casinos no romandre en el negoci per molt temps.
>> Aquí el tenen.
Ara ja sap de les cerques binàries i arbres binaris de cerca.
Sóc Patrick Schmid, i això és CS50.
[CS50.TV]
Una manera òbvia seria la d'examinar la llista de ... [xiulet]
... El nombre d'elements ... sip
[Rialles]
Node de publicar ... 234 ... augh.
>> Yay! Això va ser -