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 ${\sum }_{i=0}^h{m}^i=\frac{m^{h+1}-1}{m-1}$, mentre que l'alçada h és

$$\begin{array}{cc}& \frac{m^{h+1}-1}{m-1}\ge N>\frac{m^h-1}{m-1}\\ & m^{h+1}\ge (m-1)\cdot N+1>m^h\\ & h+1\ge {\log }_m((m-1)\cdot N+1)>h\\ & h\ge \lceil {\log }_m((m-1)\cdot N+1)-1\rceil .\end{array}$$Segons la definició de Big-Ω, la profunditat màxima $$D=h\ge \lceil {\log }_m((m-1)\cdot N+1)-1\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à).