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.

• 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 ^[1] n-arno stablo kod koga se svi listovi nalaze na istoj dubini.^[2]
• 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".^[1]

• Za n-arno stablo sa visinom h, maksimalan broj listova je ${\displaystyle 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 ${\displaystyle \left\lfloor {\frac {n^{h+1}-1}{n-1}}\right\rfloor }$, dok je visina h jednaka

${\displaystyle \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:

${\displaystyle \log _{n}[(n-1)*{\mathit {broj\_cvorova}}+1]-1,n\geq 2.}$

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 ${\displaystyle n*i+1+c}$, dok se njegov roditelj (ako postoji) nalazi na indeksu ${\displaystyle \left\lfloor {\frac {i-1}{n}}\right\rfloor }$ (ako koren ima indeks 0). 

• Binarno stablo

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