Skip to main content
SpringerLink
Log in

Efficient Generation, Ranking, and Unranking of (k, m)-Ary Trees in B-Order

  • Original Paper
  • Published:
Bulletin of the Iranian Mathematical Society Aims and scope Submit manuscript

Abstract

In this paper, we present a new generation algorithm with corresponding ranking and unranking algorithms for (k, m)-ary trees in B-order. (k, m)-ary tree is introduced by Du and Liu. A (k, m)-ary tree is a generalization of k-ary tree, whose every node of even level of the tree has degree k and odd level of the tree has degree 0 or m. Up to our knowledge no generation, ranking or unranking algorithms are given in the literature for this family of trees. We use Zaks’ encoding for representing (k, m)-ary trees and to generate them in B-order. We also prove that, to generate (k, m)-ary trees in B-order using this encoding, the corresponding codewords should be generated in reverse-lexicographical ordering. The presented generation algorithm has a constant average time and O(n) time complexity in the worst case. Due to the given encoding, both ranking and unranking algorithms are also presented taking O(n) and \(O(n\log n)\) time complexity, respectively.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5

Similar content being viewed by others

References

  1. Ahmadi-Adl, A., Nowzari-Dalini, A., Ahrabian, H.: Ranking and unranking algorithms for loopless generation of \(t\)-ary trees. Logic J. IGPL 19, 33–43 (2011)

    Article  MathSciNet  MATH  Google Scholar 

  2. Ahrabian, H., Nowzari-Dalini, A.: Parallel generation of \(t\)-ary trees in A-order. Comput. J. 50, 581–588 (2007)

    Article  MATH  Google Scholar 

  3. Amani, M., Nowzari-Dalini, A., Ahrabian, H.: Generation of neuronal trees by a new three letters encoding. Comput. Inform. J. 33(6), 1428–1450 (2014)

    MathSciNet  MATH  Google Scholar 

  4. Amani, M., Nowzari-Dalini, A.: Ranking and unranking algorithm for neuronal trees in B-order. J. Phys. Sci. 20, 19–34 (2015)

    MathSciNet  Google Scholar 

  5. Amani, M., Nowzari-Dalini, A.: Generation, ranking and unranking of ordered trees with degree bounds, in Proc. DCM 2015. Electron. Proc. Theor. Comput. Sci. 204, 31–45 (2015)

    Article  Google Scholar 

  6. Amani, M.: Gap terminology and related combinatorial properties for AVL trees and Fibonacci-isomorphic trees. AKCE Int. J. Graphs Comb. 15(1), 14–21 (2018)

    Article  MathSciNet  MATH  Google Scholar 

  7. Du, R.R.X., Liu, F.: \((k, m)\)-Catalan numbers and hook length polynomials for plane trees. Eur. J. Comb. 28, 1312–1321 (2007)

    Article  MathSciNet  MATH  Google Scholar 

  8. Durocher, S., Li, P.C., Mondal, D., Ruskey, F., Williams, A.: Cool-lex order and k-ary Catalan structures. J. Discrete Algorithms 16, 287–307 (2012)

    Article  MathSciNet  MATH  Google Scholar 

  9. Heubach, S., Li, N., Mansour, T.: Staircase tilings and \(k\)-Catalan structures. Discrete Math. 308, 5954–5964 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  10. Joichi, J.I., White, D.E., Williamson, S.G.: Combinatorial Gray codes. SIAM J. Comput. 9, 130–141 (1980)

    Article  MathSciNet  MATH  Google Scholar 

  11. Korsh, J.F., LaFollette, P.: Loopless generation of Gray codes for \(k\)-ary trees. Inf. Process. Lett. 70, 7–11 (1999)

    Article  MathSciNet  MATH  Google Scholar 

  12. Kreher, D.L., Stinson, D.R.: Combinatorial Algorithms, 2nd edn. CRC Press, New York (1999)

    MATH  Google Scholar 

  13. Li, L.: Ranking and unranking AVL trees. SIAM J. Comput. 15, 1025–1035 (1986)

    Article  MathSciNet  MATH  Google Scholar 

  14. Pallo, J.: Enumerating, ranking and unranking binary trees. Comput. J. 29, 171–175 (1986)

    Article  MathSciNet  MATH  Google Scholar 

  15. Pallo, J.: Generating trees with \(n\) nodes and \(m\) leaves. Int. J. Comput. Math. 21, 133–144 (1987)

    Article  MATH  Google Scholar 

  16. Pallo, J.: A simple algorithm for generating neuronal dendritic trees. Comput. Methods Program Biomed. 33, 165–169 (1990)

    Article  Google Scholar 

  17. van Baronaigien, D.R.: A loopless algorithm for generating binary trees sequences. Inf. Process. Lett. 39, 189–194 (1991)

    Article  MathSciNet  MATH  Google Scholar 

  18. van Baronaigien, D.R., Ruskey, F.: Generating \(t\)-ary trees in A-order. Inf. Process. Lett. 27, 205–213 (1988)

    Article  MathSciNet  MATH  Google Scholar 

  19. van Baronaigien, D.R.: A loopless Gray code algorithm for listing \(k\)-ary trees. J. Algorithms 35, 100–107 (2000)

    Article  MathSciNet  MATH  Google Scholar 

  20. Ruskey, F.: Generating \(t\)-ary trees lexicographically. SIAM J. Comput. 7, 424–439 (1978)

    Article  MathSciNet  MATH  Google Scholar 

  21. Seyedi-Tabari, E., Ahrabian, H., Nowzari-Dalini, A.: A new algorithm for generation of different types of RNA. Int. J. Comput. Math. 87, 1197–1207 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  22. Solomon, M., Finkel, R.A.: A note on enumerating binary trees. J. ACM 27, 3–5 (1980)

    Article  MathSciNet  Google Scholar 

  23. Stanley, R.P.: Enumerative Combinatorics, vol. 2. Cambridge University Press, Cambridge (1999)

    Book  MATH  Google Scholar 

  24. Stojmenovic, I.: Listing combinatorial objects in parallel. Int. J. Parallel Emerg. Distrib. Syst. 21, 127–146 (2006)

    Article  MathSciNet  MATH  Google Scholar 

  25. Vajnovszki, V.: Listing and random generation of neuronal trees coded by six letters. Autom. Comput. Appl. Math. 4, 29–40 (1995)

    MathSciNet  Google Scholar 

  26. Vajnovszki, V., Pallo, J.: Generating binary trees in A-order from codewords defined on four-letter alphabet. J. Inf. Optim. Sci. 15, 345–357 (1994)

    MathSciNet  MATH  Google Scholar 

  27. Wu, R., Chang, J., Wang, Y.: A linear time algorithm for binary tree sequences transformation using left-arm and right-arm rotations. Theor. Comput. Sci. 335, 303–314 (2006)

    Article  MathSciNet  MATH  Google Scholar 

  28. Wu, R., Chang, J., Chang, C.: Ranking and unranking of non-regular trees with a prescribed branching sequence. Math. Comput. Modell. 53, 1331–1335 (2011)

    Article  MathSciNet  MATH  Google Scholar 

  29. Zaks, S.: Lexicographic generation of ordered trees. Theor. Comput. Sci. 10, 63–82 (1980)

    Article  MathSciNet  MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. School of Mathematics, Statistics, and Computer Science, Colleague of Science, University of Tehran, Tehran, Iran

    M. Amani & A. Nowzari-Dalini

  2. Department of Computer Science (IDI), Norwegian University of Science and Technology (NTNU), Trondheim, Norway

    M. Amani

Authors
  1. M. Amani
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. A. Nowzari-Dalini
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to A. Nowzari-Dalini.

Additional information

Communicated by Hossein Hajiabolhassan.

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Amani, M., Nowzari-Dalini, A. Efficient Generation, Ranking, and Unranking of (k, m)-Ary Trees in B-Order. Bull. Iran. Math. Soc. 45, 1145–1158 (2019). https://doi.org/10.1007/s41980-018-0190-y

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s41980-018-0190-y

Keywords

Mathematics Subject Classification

Search

Navigation