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 . 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 , dok je visina h jednaka
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:
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 , dok se njegov roditelj (ako postoji) nalazi na indeksu (ako koren ima indeks 0).
Vidi još Binarno stablo
Reference
Spoljašnje veze N-ary trees, Bruno R. Preiss, P.Eng.
Категорија:Стабла (структуре података) Категорија:Стабла (теорија графова)