Diferència clau: arbre binari i arbre de cerca binari
Una estructura de dades és una manera sistemàtica d'organitzar les dades per utilitzar-les de manera eficient. L'ordenació de les dades mitjançant l'estructura de dades hauria de reduir el temps d'execució o el temps d'execució. A més, l'estructura de dades hauria de requerir una quantitat mínima de memòria. De vegades, les dades es poden organitzar en una estructura d'arbre. Un arbre representa un node connectat per arestes. El node superior és l'arrel. Cada node pot tenir un màxim de dos nodes. Es coneixen com a nodes fills. El node a l'esquerra del node pare és el node fill esquerre mentre que el node a la dreta del node pare és el node dret. L'arbre binari i l'arbre de cerca binari són dues estructures de dades d'arbre. Un arbre binari és un tipus d'estructura de dades on cada node pare pot tenir com a màxim dos nodes fill. L'arbre de cerca binari és un arbre binari on el fill esquerre només conté nodes amb valors inferiors o iguals al node pare, i on el fill dret només conté nodes amb valors superiors al node pare. Aquesta és la diferència clau. A diferència de les estructures de dades com les matrius, l'arbre binari i l'arbre de cerca binari no tenen un límit superior per emmagatzemar dades.
Què és l'arbre binari?
Quan s'organitzen les dades en una estructura d'arbre, el node de la part superior de l'arbre es coneix com el node arrel. Només hi pot haver una arrel per a tot l'arbre. Qualsevol node excepte el node arrel té una vora cap amunt fins a un node. S'anomena node pare. El node que hi ha sota el codi pare s'anomena node fill. Cada node pare pot tenir un màxim de dos nodes fill. Es coneixen com a node fill esquerre i node fill dret. Un node sense cap node fill s'anomena node fulla. No hi ha cap manera específica d'ordenar les dades a l'arbre binari. Hi ha un camí des del node arrel fins a cada node.
Figura 01: Exemple d'arbre binari
A sobre hi ha un exemple d'arbre binari. L'element 2, a la part superior de l'arbre, és l'arrel. Cada node té un màxim de dos nodes. Si un arbre conté algun bucle o si un node conté més de dos nodes, no es pot classificar com a arbre binari. Per anar d'un node a l' altre, sempre hi ha un camí. Els nodes fills del node arrel 2 són 7 i 5. També és possible que un node no tingui nodes. Però qualsevol node no pot tenir més de dos nodes. L'element dret de l'arrel és 5. Aquest element 5 és el node pare per al node fill 9. Els nodes 4 i 11 no tenen elements secundaris. Per tant, són nodes de fulla.
L'arbre binari s'utilitza per emmagatzemar dades en ordre jeràrquic. És similar a l'estructura de fitxers de l'ordinador. L'estructura de dades com una matriu pot emmagatzemar una quantitat específica de dades. Però en un arbre binari, no hi ha un límit superior en el nombre de nodes.
Què és l'arbre de cerca binari?
Un arbre de cerca binari és una estructura de dades d'arbre binari. De manera similar a un arbre binari, l'arbre de cerca binari també pot tenir dos nodes. Qualsevol node excepte el node arrel té una vora cap amunt fins a un node. S'anomena node pare. El node per sota d'un determinat connectat per la seva vora cap avall s'anomena node fill. Un node sense cap node fill s'anomena node fulla. Cada node pare pot tenir un màxim de dos nodes. Hi ha nodes fills que fan referència a un node fill esquerre i un node fill dret. L'element superior s'anomena node arrel. El fill esquerre només conté nodes amb valors inferiors o iguals al node pare. El fill dret només conté nodes amb valors superiors o iguals al node pare.
Figura 02: Exemple d'arbre de cerca binària
L'element 8 és l'element superior. Per tant, és el node arrel. Si 3 és un node pare, aleshores 1 i 6 són nodes fills. L'1 és el node fill esquerre mentre que 6 és el node fill dret. El fill esquerre conté valors inferiors o iguals al node pare. Quan 3 és el node pare, el costat esquerre hauria de tenir un element que sigui menor o igual que 3. En aquest exemple, és 1. El fill dret només conté nodes amb valors més grans que el node pare. Quan 3 és el node pare, el node fill dret hauria de tenir un valor superior a 3. En aquest exemple, és 6. De la mateixa manera, hi ha un cert ordre per organitzar cada element de dades en un arbre de cerca binari. És una estructura de dades que ofereix una manera eficient d'ordenar, recuperar i cercar dades.
Quines similituds hi ha entre l'arbre binari i l'arbre de cerca binari?
- Tant l'arbre binari com l'arbre de cerca binari són estructures de dades jeràrquiques.
- Tant l'arbre binari com l'arbre de cerca binari tenen una arrel.
- Tant l'arbre binari com l'arbre de cerca binari poden tenir un màxim de dos nodes secundaris.
Quina diferència hi ha entre l'arbre binari i l'arbre de cerca binari?
Arbre binari vs arbre de cerca binari |
|
| Un arbre binari és un tipus d'estructura de dades on cada node principal pot tenir com a màxim dos nodes secundaris. | L'arbre de cerca binari és un arbre binari on el fill esquerre només conté nodes amb valors inferiors o iguals al node pare, i on el fill dret només conté nodes amb valors superiors al node pare. |
| Ordre d'ordenació de dades | |
| Un arbre binari no té un ordre específic per organitzar els elements de dades. | Un arbre de cerca binari té un ordre específic per organitzar els elements de dades. |
| Ús | |
| Un arbre binari s'utilitza com a cerca eficient de dades i informació en una estructura d'arbre. | S'utilitza un arbre de cerca binari per inserir, suprimir i cercar les dades. |
Resum: arbre binari i arbre de cerca binari
Una estructura de dades és una manera d'organitzar les dades. De vegades, les dades es poden organitzar en una estructura d'arbre. Dos d'ells són l'arbre binari i l'arbre de cerca binari. En aquest article es parla de la diferència entre l'arbre binari i l'arbre de cerca binari. Un arbre binari és un tipus d'estructura de dades on cada node pare pot tenir com a màxim dos nodes fill. L'arbre de cerca binari és un arbre binari on el fill esquerre només conté nodes amb valors inferiors o iguals al node pare, i on el fill dret només conté nodes amb valors superiors al node pare.
Descarregueu el PDF de Binary Tree vs Binary Search Tree
Podeu descarregar la versió PDF d'aquest article i utilitzar-la per a finalitats fora de línia segons la nota de citació. Si us plau, descarregueu la versió PDF aquí: Diferència entre l'arbre binari i l'arbre de cerca binari
