Arbre binari complet vs arbre binari complet
L'arbre binari és un arbre on cada node té un o dos fills. En un arbre binari, un node no pot tenir més de dos fills. En un arbre binari, els nens s'anomenen com a nens "esquerra" i "dreta". Els nodes fill contenen una referència al seu pare. Un arbre binari complet és un arbre binari en el qual tots els nivells de l'arbre binari s'omplen completament excepte l'últim nivell. Al nivell no omplert, els nodes s'adjunten començant des de la posició més a l'esquerra. Un arbre binari complet és un arbre en el qual cada node de l'arbre té dos fills excepte les fulles de l'arbre.
Què és l'arbre binari complet?
L'arbre binari complet és un arbre binari en què cada node de l'arbre té exactament zero o dos fills. En altres paraules, cada node de l'arbre, excepte les fulles, té exactament dos fills. La figura 1 següent mostra un arbre binari complet. En un arbre binari complet, el nombre de nodes (n), el nombre de laves (l) i el nombre de nodes interns (i) es relacionen d'una manera especial de manera que si coneixeu algun d'ells podeu determinar els altres dos. els valors següents:
1. Si un arbre binari complet té i nodes interns:
– Nombre de fulles l=i+1
– Nombre total de nodes n=2i+1
2. Si un arbre binari complet té n nodes:
– Nombre de nodes interns i=(n-1)/2
– Nombre de fulles l=(n+1)/2
3. Si un arbre binari complet té l fulles:
– Nombre total de nodes n=2l-1
– Nombre de nodes interns i=l-1
Què és l'arbre binari complet?
Com es mostra a la figura 2, un arbre binari complet és un arbre binari en el qual tots els nivells de l'arbre s'omplen completament excepte l'últim nivell. A més, a l'últim nivell, els nodes s'han d'adjuntar a partir de la posició més a l'esquerra. Un arbre binari complet d'alçada h compleix les condicions següents:
– Des del node arrel, el nivell per sobre de l'últim nivell representa un arbre binari complet d'alçada h-1
: un o més nodes de l'últim nivell poden tenir 0 o 1 fill
– Si a, b són dos nodes al nivell per sobre de l'últim nivell, aleshores a té més fills que b si i només si a es troba a l'esquerra de b
Quina diferència hi ha entre l'arbre binari complet i l'arbre binari complet?
Els arbres binaris complets i els arbres binaris complets tenen una clara diferència. Mentre que un arbre binari complet és un arbre binari en què cada node té zero o dos fills, un arbre binari complet és un arbre binari en què tots els nivells de l'arbre binari s'omplen completament excepte l'últim nivell. Algunes estructures de dades especials com els munts han de ser arbres binaris complets, mentre que no necessiten ser arbres binaris complets. En un arbre binari complet, si coneixeu el nombre de nodes totals o el nombre de laves o el nombre de nodes interns, podeu trobar els altres dos molt fàcilment. Però un arbre binari complet no té una propietat especial que relacioni aquests tres atributs.
