Arbre M-ari

Un exemple d'arbre m-ari amb m=5

En teoria de grafs, un arbre m-ari (per a nombres enters no negatius m) (també conegut com a arbre n-ary, k-ary o k-way) és una arborescència (o, per a alguns autors, un arbre ordenat) en què cada node no té més de m fills. Un arbre binari és el cas especial on m = 2, i un arbre ternari és un altre cas amb m = 3 que limita els seus fills a tres.

Tipus d'arbres m-aris

• Un arbre m-ari complet és un arbre m -ari on dins de cada nivell cada node té 0 o m fills.
• Un arbre m-ari complet (o, menys habitualment, un arbre m-ari perfecte) és un arbre m -ari complet en el qual tots els nodes de fulles es troben a la mateixa profunditat.

Propietats dels arbres m-aris

• Per a un arbre m -ari amb alçada h, el límit superior del nombre màxim de fulles és $m^{h}$.
• L'alçada h d'un arbre m -ari no inclou el node arrel, amb un arbre que només conté un node arrel amb una alçada de 0.
• L'alçada d'un arbre és igual a la profunditat màxima D de qualsevol node de l'arbre.
• El nombre total de nodes en un arbre m -ari perfecte és ${\textstyle \sum _{i=0}^{h}m^{i}={\frac {m^{h+1}-1}{m-1}}}$, mentre que l'alçada h és

$${\begin{aligned}&{\frac {m^{h+1}-1}{m-1}}\geq N>{\frac {m^{h}-1}{m-1}}\\[8pt]&m^{h+1}\geq (m-1)\cdot N+1>m^{h}\\[8pt]&h+1\geq \log _{m}\left((m-1)\cdot N+1\right)>h\\[8pt]&h\geq \left\lceil \log _{m}((m-1)\cdot N+1)-1\right\rceil .\end{aligned}}$$

Segons la definició de Big-Ω, la profunditat màxima

$$D=h\geq \left\lceil \log _{m}((m-1)\cdot N+1)-1\right\rceil =O(\log _{m}n)=O(\log n/\log m).$$

• L'alçada d'un arbre m -ari complet amb n nodes és .
• El nombre total de possibles arbre m -ari amb n nodes és (que és un número català).