Profunditat Primera i Primera cerca: amplitud

Si heu trigat a estudiar codi en qualsevol forma o forma, probablement trobareu estructures de dades. Les estructures de dades es componen d'una gran quantitat de possibilitats per emmagatzemar, organitzar i manipular dades. Alguns dels més populars inclouen matrius, llistes enllaçades, piles, cues i arbres de cerca binaris. Pel bé d’aquest article, ens centrarem en dues maneres diferents d’abordar el creuament dels arbres: Primera recerca de profunditat i Primera cerca d’amplitud.

Què és un arbre?

Un arbre és una estructura de dades composta per nodes, que contenen apunts a altres nodes. A diferència dels arbres de la vida real (o potser existeixen en algun lloc), un arbre de dades està al revés. Essencialment, l’arrel està a la part superior i les fulles a la part inferior.

Anem a desglossar el diagrama.

Cada arbre té un sol node arrel que es troba al nivell superior (en aquest cas, nivell 0). Aleshores veiem que al següent nivell, el node arrel A té apunts als nodes B i C. De la mateixa manera, els nodes B i C tenen els punters per al node A. En aquesta situació, el node A és el node pare i els nodes B i C són els seus fills. A més, els nodes B i C es consideren germans.

Potser us estareu preguntant si és possible que un node tingui més de 2 fills. La resposta és que sí! Aquesta representació específica és d’un arbre binari que es pot determinar amb un màxim de dos nodes fills per a cada pare.

Codi arbre

Renúncia: utilitzaré Javascript per crear un arbre senzill.

En primer lloc, hem de crear una classe de nodes:

Quan creem una classe de nodes, la passem per valor, o de dades, que es converteix en la propietat de dades del node. També tenim actualment propietats de pares i fills, que són nuls i una matriu buida, respectivament. Finalment, la propietat parent assenyalarà el pare del node específic i la propietat children indicarà els fills del node.

Després, creem la classe d’arbre:

La classe arbre conté una sola propietat, arrel, que inicialment és nul·la. Els arbres inclouen mètodes de prototip com ara conté (), inserir () i eliminar (), però els guardarem durant un dia plujós.

Cercant!

La primera recerca en profunditat i la primera amplada són mètodes de prototip de la classe Tree que s'utilitzen per determinar si hi ha un node particular que conté dades específiques dins d'un arbre. La representació següent mostra els dos procediments de cerca diferents.

Primera aproximació de profunditat

El mètode primer-profund comença al node arrel i es desplaça cap al node més esquerre. Una vegada que es colpeja al node més esquerre, recorre l'arbre de nou a l'arrel i després al node més dret. Si toca un node amb nens, es desplaçarà pels nens del node d'esquerra a dreta i segueix cap a la dreta.

Ordre de cerca: [10, 4, 1, 9, 17, 12, 18]

Codi

La primera recerca en profunditat implica un valor com a argument que és el valor que buscàvem a l'arbre. Com que volem recórrer els nodes d’esquerra a dreta, establim l’arrel com una pila perquè volem treure un últim enfocament primer. A continuació, realitzem un bucle while que continua mentre la pila conté elements. Dins el bucle while, eliminem el primer element de la pila o anomenem el mètode shift (), i el definim igual a un node. Comparem les dades d’aquest node amb el valor de l’argument i si coincideixen, la funció retorna. Si no és el cas, afegeix els fills del node a la part davantera de la pila o truca el mètode unshift (), i continua buscant les noves dades. Si el valor particular no existeix a l'arbre, la funció retorna falsa.

Primera aproximació de la paret

El primer abordatge d'amplada comença al node arrel i es recorre a través de cada nivell successiu per cercar el node desitjat. Igualment al primer acostament a fons, els nodes es llegeixen d’esquerra a dreta a cada nivell.

Ordre de cerca: [10, 4, 17, 1, 9, 12, 18]

Codi

La primera cerca d’amplada és similar al codi que a la primera cerca en profunditat. Té un valor que es pot trobar com a argument. La diferència aquí és que en lloc d’utilitzar una pila, volem utilitzar una cua per poder fer un primer enfocament en primer lloc. Al bucle while, de manera similar a la recerca en primer lloc, volem utilitzar el mètode shift () per eliminar el primer element de la cua com a node. Tanmateix, si les dades del node no són el mateix que el valor desitjat, en comptes de canviar els fills del node, utilitzarem el mètode push () per afegir els fills al final de la cua. Això ens permet comprovar tots els nodes en un nivell abans de recórrer els nodes del nivell següent. Finalment, de la mateixa manera que la cerca en profunditat, si no es troba el valor, la funció serà falsa.

Què faig servir?

Tot i que les cerques en primer lloc (DFS) i primera d'amplada (BFS) són aproximacions legítimes i poden arribar a les mateixes conclusions, cadascuna es veu afavorida en determinades circumstàncies. Tanmateix, sovint no és obvi quin és el més eficient dels dos.

Renúncia: Aquestes són directrius generals. Sens dubte no sempre són els enfocaments més òptims.

DFS: generalment es prefereix quan l’arbre és molt profund i els valors o dades desitjades es produeixen amb freqüència.

BFS: Generalment es prefereix en arbres poc profunds que no són massa amplis. També s'utilitza si se sap que el node desitjat està més a prop del nivell d'arrel.

Tot i que hi ha preferències generals a l’hora de decidir quin mètode utilitzar, si no esteu segurs, probablement sigui millor provar ambdós mètodes i veure quin és més eficient.

Per exemple, diguem que utilitzeu l’arbre de dalt i que esteu buscant el node que conté 8. L’arbre no és tan profund, així que podríeu pensar que seria millor utilitzar un BFS. Tanmateix, en realitat seria més eficient utilitzar un DFS.

Comparem els dos mètodes i quins nodes s'han creuat:

DFS: 1, 2, 4, 8

BFS: 1, 2, 3, 4, 5, 6, 7, 8

Ja podem veure que una cerca d'amplada travessa més nodes i, per tant, necessita accés a més memòria.

A més, un cop localitzem el node 8, la pila DFS seria [8, 9, 5, 3] mentre que la cua BFS seria [8, 9, 10, 11, 13, 14]. La cua BFS conté 2 nodes més, que sembla que no s'equipara a gaire en aquest exemple, però en termes de memòria, encara utilitza una quantitat més gran. Per tant, en aquesta situació particular, una DFS seria més eficient que una BFS.

Tot i que aquest exemple és simple i senzill, en situacions en què els arbres són més profunds i amplis, és sens dubte molt més difícil determinar quin és el més òptim. La millor manera de dictar el millor mètode és intentar tots dos.

Complexitat

La complexitat de temps i d’espai tant per a DFS com per a BFS és bastant senzilla. Com que estem parlant de l’arbre de creuament, per determinar si hi ha un valor o dades dins l’arbre, hem de visitar tots els nodes. Visitar cada node un sol temps significa que la complexitat horària tant per DFS com per BFS són O (n) o lineals. Si pensem en els arbres com a matrius ordenades, només hauríem d’utilitzar una sola vegada per determinar si un valor coincideix o no amb el valor que buscem. De la mateixa manera, en termes de complexitat espacial, DFS és O (h) i BFS és O (w). Per a DFS, "h" és l'alçada, ja que la quantitat d'espai que ocuparà la funció depèn del nombre de nodes de fons de l'arbre. Així mateix, per a BFS, "w" és l'amplada, ja que l'espai depèn de l'amplada de l'arbre. Per descomptat, aquestes notacions O grans canvien en funció de l'estructura de dades, però pel bé dels arbres, les complexitats del temps i l'espai seran les mateixes.

Gràcies per dedicar-vos a llegir aquest article. Si teniu cap comentari o dubte, informeu-me! Espero que tinguis un bon dia!