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 $\left\lfloor {\frac {n^{h+1}-1}{n-1}}\right\rfloor$, dok je visina h jednaka

$\left\lceil \log _{n}(n-1)+\log _{n}({\mathit {broj\_cvorova}})-1\right\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)*{\mathit {broj\_cvorova}}+1]-1,n\geq 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 $\left\lfloor {\frac {i-1}{n}}\right\rfloor$ (ako koren ima indeks 0). 

Vidi još

• Binarno stablo

Spoljašnje veze

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