N-arno stablo

U teoriji grafova,  n-arno stablo je stablo sa korenom u kojem svaki čvor ima najviše n dece. Još se zove i k-arno stablo i m-arno stablo. Binarno stablo je specijalan slučaj kada je n=2.

Tipovi n-arnih stabala

• Puno n-arno stablo je n-arno stablo kod koga na svakom nivou svaki čvor ima 0 ili n dece.
• Savršeno n-arno stablo je puno  n-arno stablo kod koga se svi listovi nalaze na istoj dubini.
• Kompletno n-arno stablo je n-arno stablo kod koga je najefikasnije iskorišćen prostor. Svaki nivo sem poslednjeg mora biti potpuno popunjen (svaki čvor koji nije na poslednjem nivou ima n dece). Međutim, ako poslednji nivo nije kompletno popunjen, svi čvorovi moraju biti postavljeni što je moguće više "u levo".

Svojstva n-arnih stabala

• Za n-arno stablo sa visinom h, maksimalan broj listova je $n^h$.
  
• Visina h n-arnog stabla ne uključuje čvor korena stabla, stablo koje sadrži samo koren ima visinu 0.
• Broj čvorova u savršenom n-arnom stablu je $\lfloor \frac{n^{h+1}-1}{n-1}\rfloor$, dok je visina h jednaka

$\lceil {\log }_n(n-1)+{\log }_n(𝑏𝑟𝑜𝑗\mathrm{\_}𝑐𝑣𝑜𝑟𝑜𝑣𝑎)-1\rceil .$

Napomena : Za stablo koje sadrži samo jedan čvor se uzima da mu je visina 0, da bi ova formula važila.

Napomena : Formula ne važi za 2-arno stablo sa visinom 0, jer operator zaokruživanja na gornju celobrojnu vrednost pojednostavljuje punu formulu, koja glasi:

${\log }_n[(n-1)*𝑏𝑟𝑜𝑗\mathrm{\_}𝑐𝑣𝑜𝑟𝑜𝑣𝑎+1]-1,n\ge 2.$

Metodi skladištenja n-arnih stabala

Nizovi

N-arno stablo se može uskladištiti u nizove u vidu poretka u širinu, a ako je stablo kompletno n-arno stablo, ovim metodom se ne gubi prostor. U ovom kompaktnom obliku, ako čvor ima indeks i, njegovo c-to dete se nalazi na indeksu $n*i+1+c$, dok se njegov roditelj (ako postoji) nalazi na indeksu $\lfloor \frac{i-1}{n}\rfloor$ (ako koren ima indeks 0). 

Vidi još

• Binarno stablo

Spoljašnje veze

• N-ary trees, Bruno R. Preiss, P.Eng.