Vés al contingut

Arbre M-ari

De la Viquipèdia, l'enciclopèdia lliure
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) [1][2] 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.[3]

Tipus d'arbres m-aris

[modifica]
  • 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.[4]

Propietats dels arbres m-aris

[modifica]
  • Per a un arbre m -ari amb alçada h, el límit superior del nombre màxim de fulles és .
  • 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 , mentre que l'alçada h és

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

  • 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à).

Referències

[modifica]
  1. Li, Liwu. Java: Data Structures and Programming (en anglès). Section 8.1.2.1, Multi-Ary Trees: Springer, 1998. DOI 10.1007/978-3-642-95851-9. ISBN 978-3-642-95853-3. 
  2. Stanley, Richard P. Enumerative Combinatorics, Volume I (en anglès). Appendix: Graph Theory Terminology: Cambridge University Press, 2011, p. 573. ISBN 978-1-107-60262-5. 
  3. «M-array Tree in Discrete Mathematics - javatpoint» (en anglès). [Consulta: 14 octubre 2023].
  4. «GRAPH THEORY – LECTURE 4: TREES» (en anglès). [Consulta: 14 octubre 2023].