Primer, entendrem el arbre binari i arbre de cerca binari per separat, i després veurem les diferències entre un arbre binari i un arbre de cerca binari.
Què és un arbre binari?
A Arbre binari és un
L'arbre binari es pot representar com:
A la figura anterior, podem observar que cada node conté com a màxim 2 fills. Si cap node no conté fill esquerre o dret, el valor del punter respecte a aquest fill seria NULL.
Les terminologies bàsiques utilitzades en un arbre binari són:
En un arbre binari, hi ha un arbre conegut com a arbre binari perfecte . És un arbre en el qual tots els nodes interns han de contenir dos nodes i tots els nodes full han d'estar a la mateixa profunditat. En el cas d'un arbre binari perfecte, el nombre total de nodes que existeixen en un arbre binari es pot calcular mitjançant l'equació següent:
n = 2m+1-1
on n és el nombre de nodes, m és la profunditat d'un node.
Què és un arbre de cerca binari?
A Arbre de cerca binari és un arbre que segueix algun ordre per disposar els elements, mentre que l'arbre binari no segueix cap ordre. En un arbre de cerca binari, el valor del node esquerre ha de ser més petit que el node pare i el valor del node dret ha de ser més gran que el node pare.
Entendrem el concepte d'arbre de cerca binari a través d'exemples.
A la figura anterior, podem observar que el valor del node arrel és 15, que és més gran que el valor de tots els nodes del subarbre esquerre. El valor del node arrel és menor que els valors de tots els nodes d'un subarbre dret. Ara, ens movem al fill esquerre del node arrel. 10 és més gran que 8 i menor que 12; també satisfà la propietat de l'arbre de cerca binari. Ara, ens movem al fill dret del node arrel; el valor 20 és superior a 17 i inferior a 25; també compleix la propietat de l'arbre de cerca binari. Per tant, podem dir que l'arbre que es mostra a dalt és l'arbre de cerca binari.
Ara, si canviem el valor de 12 a 16 a l'arbre binari anterior, haurem de trobar si encara és un arbre de cerca binari o no.
El valor del node arrel és 15, que és més gran que 10 però menor que 16, de manera que no compleix la propietat de l'arbre de cerca binari. Per tant, no és un arbre de cerca binari.
Operacions a l'arbre de cerca binari
Podem realitzar operacions d'inserció, eliminació i cerca a l'arbre de cerca binari. Entendrem com es realitza una cerca en una cerca binària. A continuació es mostra l'arbre binari sobre el qual hem de realitzar l'operació de cerca:
Suposem que hem de cercar 10 a l'arbre binari anterior. Per realitzar la cerca binària, considerarem tots els nombres enters d'una matriu ordenada. Primer, creem una llista completa en un espai de cerca i tots els números existiran a l'espai de cerca. L'espai de cerca està marcat per dos punters, és a dir, l'inici i el final. La matriu de l'arbre binari anterior es pot representar com
Primer, calcularem l'element central i compararem l'element central amb l'element que s'ha de cercar. L'element central es calcula utilitzant n/2. El valor de n és 7; per tant, l'element central és 15. L'element central no és igual a l'element cercat, és a dir, 10.
Nota: si l'element que s'està buscant és menor que l'element central, la cerca es realitzarà a la meitat esquerra; en cas contrari, la cerca es farà a la meitat dreta. En el cas d'igualtat, es troba l'element.
Com que l'element que s'ha de cercar és menor que l'element central, la cerca es realitzarà a la matriu esquerra. Ara la cerca es redueix a la meitat, com es mostra a continuació:
L'element central de la matriu esquerra és 10, que és igual a l'element cercat.
Complexitat temporal
En una cerca binària, hi ha n elements. Si l'element central no és igual a l'element cercat, aleshores l'espai de cerca es redueix a n/2, i continuarem reduint l'espai de cerca n/2 fins que trobem l'element. En tota la reducció, si passem de n a n/2 a n/4 i així successivament, es necessitarà log2n passos.
Diferències entre l'arbre binari i l'arbre de cerca binari
| Base per a la comparació | Arbre binari | Arbre de cerca binari |
|---|---|---|
| Definició | Un arbre binari és una estructura de dades no lineal en la qual un node pot tenir el màxim de dos fills, és a dir, un node pot tenir 0, 1 o un màxim de dos fills. Un arbre de cerca binari és un arbre binari ordenat en el qual es segueix algun ordre per organitzar els nodes en un arbre. | |
| Estructura | L'estructura de l'arbre binari és que el primer node o el node superior es coneix com el node arrel. Cada node d'un arbre binari conté el punter esquerre i el punter dret. El punter esquerre conté l'adreça del subarbre esquerre, mentre que el punter dret conté l'adreça del subarbre dret. | L'arbre de cerca binari és un dels tipus d'arbre binari que té el valor de tots els nodes del subarbre esquerre menor o igual que el node arrel, i el valor de tots els nodes d'un subarbre dret és major o igual que el valor del node arrel. |
| Operacions | Les operacions que es poden implementar en un arbre binari són la inserció, la supressió i el recorregut. | Els arbres binaris de cerca són els arbres binaris ordenats que proporcionen una inserció ràpida, supressió i cerca. Les cerques implementen principalment la cerca binària, ja que totes les claus estan ordenades. |
| tipus | Quatre tipus d'arbres binaris són l'arbre binari complet, l'arbre binari complet, l'arbre binari perfecte i l'arbre binari estès. | Hi ha diferents tipus d'arbres de cerca binaris com ara arbres AVL, arbres Splay, arbres Tango, etc. |