Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

On the Collection of Fringe Subtrees in Random Binary Trees

  • Conference paper
  • First Online:
LATIN 2020: Theoretical Informatics (LATIN 2021)

Part of the book series: Lecture Notes in Computer Science ((LNTCS,volume 12118))

Included in the following conference series:

Abstract

A fringe subtree of a rooted tree is a subtree consisting of one of the nodes and all its descendants. In this paper, we are specifically interested in the number of non-isomorphic trees that appear in the collection of all fringe subtrees of a binary tree. This number is analysed under two different random models: uniformly random binary trees and random binary search trees.

In the case of uniformly random binary trees, we show that the number of non-isomorphic fringe subtrees lies between \(c_1n/\sqrt{\ln n}(1+o(1))\) and \(c_2n/\sqrt{\ln n}(1+o(1))\) for two constants \(c_1 \approx 1.0591261434\) and \(c_2 \approx 1.0761505454\), both in expectation and with high probability, where n denotes the size (number of leaves) of the uniformly random binary tree. A similar result is proven for random binary search trees, but the order of magnitude is \(n/\ln n\) in this case.

Our proof technique can also be used to strengthen known results on the number of distinct fringe subtrees (distinct in the sense of ordered trees). This quantity is of the same order of magnitude in both cases, but with slightly different constants in the upper and lower bounds.

This project has received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement No 731143 and the DFG research project LO 748/10-1 (QUANT-KOMP).

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

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 84.99
Price excludes VAT (USA)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 109.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

References

  1. Abiteboul, S., Bourhis, P., Vianu, V.: Highly expressive query languages for unordered data trees. Theory Comput. Syst. 57(4), 927–966 (2015)

    Article  MathSciNet  Google Scholar 

  2. Aho, A.V., Sethi, R., Ullman, J.D.: Compilers: Principles, Techniques, and Tools. Addison-Wesley Series in Computer Science/World Student Series Edition. Addison-Wesley (1986)

    Google Scholar 

  3. Aldous, D.: Asymptotic fringe distributions for general families of random trees. Ann. Appl. Probab. 1(2), 228–266 (1991)

    Article  MathSciNet  Google Scholar 

  4. Bóna, M., Flajolet, P.: Isomorphism and symmetries in random phylogenetic trees. J. Appl. Probab. 46(4), 1005–1019 (2009)

    Article  MathSciNet  Google Scholar 

  5. Boneva, I., Ciucanu, R., Staworko, S.: Schemas for unordered XML on a DIME. Theory Comput. Syst. 57(2), 337–376 (2015)

    Article  MathSciNet  Google Scholar 

  6. Bousquet-Mélou, M., Lohrey, M., Maneth, S., Noeth, E.: XML compression via DAGs. Theory Comput. Syst. 57(4), 1322–1371 (2015)

    Article  MathSciNet  Google Scholar 

  7. Bryant, R.E.: Symbolic boolean manipulation with ordered binary-decision diagrams. ACM Comput. Surv. 24(3), 293–318 (1992)

    Article  Google Scholar 

  8. Buneman, P., Grohe, M., Koch, C.: Path queries on compressed XML. In: Freytag, J.C., et al. (eds.) Proceedings of the 29th Conference on Very Large Data Bases, VLDB 2003, pp. 141–152. Morgan Kaufmann (2003)

    Google Scholar 

  9. Dennert, F., Grübel, R.: On the subtree size profile of binary search trees. Comb. Probab. Comput. 19(4), 561–578 (2010)

    Article  MathSciNet  Google Scholar 

  10. Devroye, L.: On the richness of the collection of subtrees in random binary search trees. Inf. Process. Lett. 65(4), 195–199 (1998)

    Article  MathSciNet  Google Scholar 

  11. Devroye, L., Janson, S.: Protected nodes and fringe subtrees in some random trees. Electron. Commun. Probab. 19, 1–10 (2014)

    Article  MathSciNet  Google Scholar 

  12. Drmota, M.: Random Trees: An Interplay Between Combinatorics and Probability, 1st edn. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-211-75357-6

    Book  MATH  Google Scholar 

  13. Feng, Q., Mahmoud, H.M.: On the variety of shapes on the fringe of a random recursive tree. J. Appl. Probab. 47(1), 191–200 (2010)

    Article  MathSciNet  Google Scholar 

  14. Fill, J.A.: On the distribution of binary search trees under the random permutation model. Random Struct. Algorithms 8(1), 1–25 (1996)

    Article  MathSciNet  Google Scholar 

  15. Finch, S.R., Rota, G.C.: Mathematical Constants. Encyclopedia of Mathematics and Its Applications. Cambridge University Press, Cambridge (2003)

    Google Scholar 

  16. Flajolet, P., Gourdon, X., Martínez, C.: Patterns in random binary search trees. Random Struct. Algorithms 11(3), 223–244 (1997)

    Article  MathSciNet  Google Scholar 

  17. Flajolet, P., Sedgewick, R.: Analytic Combinatorics. Cambridge University Press, Cambridge (2009)

    Book  Google Scholar 

  18. Flajolet, P., Sipala, P., Steyaert, J.-M.: Analytic variations on the common subexpression problem. In: Paterson, M.S. (ed.) ICALP 1990. LNCS, vol. 443, pp. 220–234. Springer, Heidelberg (1990). https://doi.org/10.1007/BFb0032034

    Chapter  Google Scholar 

  19. Frick, M., Grohe, M., Koch, C.: Query evaluation on compressed trees (extended abstract). In: Proceedings of the 18th Annual IEEE Symposium on Logic in Computer Science, LICS 2003, pp. 188–197. IEEE Computer Society Press (2003)

    Google Scholar 

  20. Ganardi, M., Hucke, D., Lohrey, M., Benkner, L.S.: Universal tree source coding using grammar-based compression. IEEE Trans. Inf. Theory 65(10), 6399–6413 (2019)

    Article  MathSciNet  Google Scholar 

  21. Holmgren, C., Janson, S.: Limit laws for functions of fringe trees for binary search trees and random recursive trees. Electron. J. Probab. 20, 1–51 (2015)

    MathSciNet  MATH  Google Scholar 

  22. Kieffer, J.C., Yang, E.H., Szpankowski, W.: Structural complexity of random binary trees. In: Proceedings of the 2009 IEEE International Symposium on Information Theory, ISIT 2009, pp. 635–639. IEEE (2009)

    Google Scholar 

  23. Lohrey, M., Maneth, S., Reh, C.P.: Compression of unordered XML trees. In: Proceedings of the 20th International Conference on Database Theory, ICDT 2017, Venice, Italy, 21–24 March 2017, pp. 18:1–18:17 (2017)

    Google Scholar 

  24. Paterson, M., Wegman, M.N.: Linear unification. J. Comput. Syst. Sci. 16(2), 158–167 (1978)

    Article  MathSciNet  Google Scholar 

  25. Ralaivaosaona, D., Wagner, S.G.: Repeated fringe subtrees in random rooted trees. In: Proceedings of the 12th Workshop on Analytic Algorithmics and Combinatorics, ANALCO 2015, pp. 78–88. SIAM (2015)

    Google Scholar 

  26. Seelbach Benkner, L., Lohrey, M.: Average case analysis of leaf-centric binary tree sources. In: Proceedings of the 43rd International Symposium on Mathematical Foundations of Computer Science, MFCS 2018, Liverpool, UK, 27–31 August 2018, pp. 16:1–16:15 (2018)

    Google Scholar 

  27. Seelbach Benkner, L., Wagner, S.: On the collection of fringe subtrees in random binary trees. arXiv e-prints arXiv:2003.03323 (2020). https://arxiv.org/abs/2003.03323

  28. Zhang, J., Yang, E.H., Kieffer, J.C.: A universal grammar-based code for lossless compression of binary trees. IEEE Trans. Inf. Theory 60(3), 1373–1386 (2014)

    Article  MathSciNet  Google Scholar 

  29. Zhang, S., Du, Z., Wang, J.T.: New techniques for mining frequent patterns in unordered trees. IEEE Trans. Cybern. 45(6), 1113–1125 (2015)

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department für Elektrotechnik und Informatik, Universität Siegen, Hölderlinstrasse 3, 57076, Siegen, Germany

    Louisa Seelbach Benkner

  2. Department of Mathematical Sciences, Stellenbosch University, Private Bag X1, Matieland, 7602, South Africa

    Stephan Wagner

  3. Department of Mathematics, Uppsala Universitet, Box 480, 751 06, Uppsala, Sweden

    Stephan Wagner

Authors
  1. Louisa Seelbach Benkner
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Stephan Wagner
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Louisa Seelbach Benkner .

Editor information

Editors and Affiliations

  1. University of São Paulo, São Paulo, Brazil

    Yoshiharu Kohayakawa

  2. University of Campinas, Campinas, Brazil

    Flávio Keidi Miyazawa

Rights and permissions

Reprints and permissions

Copyright information

© 2020 Springer Nature Switzerland AG

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Seelbach Benkner, L., Wagner, S. (2020). On the Collection of Fringe Subtrees in Random Binary Trees. In: Kohayakawa, Y., Miyazawa, F.K. (eds) LATIN 2020: Theoretical Informatics. LATIN 2021. Lecture Notes in Computer Science(), vol 12118. Springer, Cham. https://doi.org/10.1007/978-3-030-61792-9_43

Download citation

  • DOI: https://doi.org/10.1007/978-3-030-61792-9_43

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-030-61791-2

  • Online ISBN: 978-3-030-61792-9

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation