Н-арно стабло

У теорији графова,  н-арно стабло је стабло са кореном у којем сваки чвор има највише н деце. Још се зове и к-арно стабло и м-арно стабло. Бинарно стабло је специјалан случај када је н=2.

Типови н-арних стабала

• Пуно н-арно стабло је н-арно стабло код кога на сваком нивоу сваки чвор има 0 или н деце.
• Савршено н-арно стабло је пуно  н-арно стабло код кога се сви листови налазе на истој дубини.
• Комплетно н-арно стабло је н-арно стабло код кога је најефикасније искоришћен простор. Сваки ниво сем последњег мора бити потпуно попуњен (сваки чвор који није на последњем нивоу има н деце). Међутим, ако последњи ниво није комплетно попуњен, сви чворови морају бити постављени што је могуће више "у лево".

Својства н-арних стабала

• За н-арно стабло са висином х, максималан број листова је $n^{h}$.
  
• Висина х н-арног стабла не укључује чвор корена стабла, стабло које садржи само корен има висину 0.
• Број чворова у савршеном н-арном стаблу је $\left\lfloor {\frac {n^{h+1}-1}{n-1}}\right\rfloor$, док је висина х једнака

$\left\lceil \log _{n}(n-1)+\log _{n}({\mathit {broj\_cvorova}})-1\right\rceil .$

Напомена : За стабло које садржи само један чвор се узима да му је висина 0, да би ова формула важила.

Напомена : Формула не важи за 2-арно стабло са висином 0, јер оператор заокруживања на горњу целобројну вредност поједностављује пуну формулу, која гласи:

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

Методи складиштења н-арних стабала

Низови

Н-арно стабло се може ускладиштити у низове у виду поретка у ширину, а ако је стабло комплетно н-арно стабло, овим методом се не губи простор. У овом компактном облику, ако чвор има индекс и, његово ц-то дете се налази на индексу $n*i+1+c$, док се његов родитељ (ако постоји) налази на индексу $\left\lfloor {\frac {i-1}{n}}\right\rfloor$ (ако корен има индекс 0). 

Види још

• Бинарно стабло

Спољашње везе

• Н-арy треес, Бруно Р. Преисс, П.Енг.