×

zbMATH — the first resource for mathematics

Weighted height of random trees. (English) Zbl 1147.68058
Summary: We consider a model of random trees similar to the split trees of L. Devroye [SIAM J. Comput. 28, 409–432 (1998; Zbl 0915.68089)] in which a set of items is recursively partitioned. Our model allows for more flexibility in the choice of the partitioning procedure, and has weighted edges. We prove that for this model, the height \(H_{n}\) of a random tree is asymptotic to \(c \log n\) in probability for a constant \(c\) that is uniquely characterized in terms of multivariate large deviations rate functions. This extension permits us to obtain the height of pebbled tries, pebbled ternary search tries, \(d\)-ary pyramids, and to study geometric properties of partitions generated by \(k\)-\(d\) trees. The model also includes all polynomial families of increasing trees recently studied by N. Broutin, L. Devroye, E. McLeish and M. de la Salle [“The height of increasing trees”, Random Struct. Algorithms 32, 494–518 (2008; Zbl 1148.05024)].

MSC:
68R10 Graph theory (including graph drawing) in computer science
05C05 Trees
05C80 Random graphs (graph-theoretic aspects)
68P05 Data structures
Software:
PATRICIA; Quicksort
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Archibald, M., Clément, J.: Average depth in binary search tree with repeated keys. In: Fourth Colloquium on Mathematics and Computer Science, volume AG of DMTCS Proceedings, pp. 309–320. Discrete Mathematics and Theoretical Computer Science (2006) · Zbl 1191.68372
[2] Athreya, K.B., Ney, P.E.: Branching Processes. Springer, Berlin (1972) · Zbl 0259.60002
[3] Barabási, A.L., Albert, R.: Emergence of scaling in random network. Science 286, 509–512 (1999) · Zbl 1226.05223 · doi:10.1126/science.286.5439.509
[4] Bentley, J.L.: Multidimensional binary search trees used for associative searching. Commun. ACM 18, 509–517 (1975) · Zbl 0306.68061 · doi:10.1145/361002.361007
[5] Bentley, J.L., Sedgewick, R.: Fast algorithm for sorting and searching strings. In: Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 360–369. SIAM, 1997 · Zbl 1321.68549
[6] Bergeron, F., Flajolet, P., Salvy, B.: Varieties of increasing trees. In: CAAP, volume 581 of Lecture Notes in Computer Science, pp. 24–48. Springer, Berlin (1992)
[7] Bhattacharya, P.K., Gastwirth, J.L.: A nonhomogeneous markov model of a chain-letter scheme. In: Rizvi, M.H., Rustagi, J.S., Siegmund, D.(eds) Recent Advances in Statistics: Papers in Honor of Herman Chernoff, Academic Press, New York (1983) · Zbl 0539.60071
[8] Biggins, J.D.: The asymptotic shape of the branching random walk. Adv. Appl. Probab. 10, 62–84 (1978) · Zbl 0383.60078 · doi:10.2307/1426719
[9] Biggins, J.D.: The growth and spread of the general branching random walk. Ann. Appl. Probab. 5, 1008–1024 (1995) · Zbl 0859.60075 · doi:10.1214/aoap/1177004604
[10] Biggins, J.D.: How fast does a general branching random walk spread. In: Athreya, K.B., Jagers, P.(eds) Classical and Modern Branching Processes, Springer, New York (1996) · Zbl 0873.60061
[11] Biggins, J.D., Grey, D.R.: A note on the growth of random trees. Statist. Probab. Lett. 32, 339–342 (1997) · Zbl 0904.60067 · doi:10.1016/S0167-7152(96)00092-2
[12] Billingsley, P.: Probability and Measure, 3rd edn. Wiley, New York (1995) · Zbl 0822.60002
[13] Broutin, N.: Shedding New Light on Random Trees. Ph.D. thesis, McGill University, Montreal (2007)
[14] Broutin, N., Devroye, L.: Large deviations for the weighted height of an extended class of trees. Algorithmica 46, 271–297 (2006) · Zbl 1106.68027 · doi:10.1007/s00453-006-0112-x
[15] Broutin, N., Devroye, L.: An analysis of the height of tries with random weights on the edges. Combinatorics, Probability and Computing 17, 161–202 (2008) · Zbl 1144.68054 · doi:10.1017/S0963548307008796
[16] Broutin, N., Devroye, L.: The height of list tries and TST. In: International Conference on Analysis of Algorithms, DMTCS Proceedings. Discrete Mathematics and Theoretical Computer Science, vol. AH, pp. 271–282 (2007) · Zbl 1192.68945
[17] Broutin, N., Devroye, L., McLeish, E., de la Salle, M.: The height of increasing trees. Random Structures and Algorithms (2007, in press) (25 pages) · Zbl 1148.05024
[18] Brown, G.G., Shubert, B.O.: On random binary trees. Math. Oper. Res. 9, 43–65 (1984) · Zbl 0529.68035 · doi:10.1287/moor.9.1.43
[19] Clampett, H.A.: Randomized binary searching with tree structures. Commun. ACM 7(3), 163–165 (1964) · Zbl 0121.12207 · doi:10.1145/363958.363987
[20] Clément, J., Flajolet, P., Vallée, B.: The analysis of hybrid trie structures. In: 9th annual ACM-SIAM Symposium on Discrete Algorithms, pp. 531–539. SIAM Press, Philadelphia, PA (1998) · Zbl 0930.68113
[21] Clément, J., Flajolet, P., Vallée, B.: Dynamical source in information theory: a general analysis of trie structures. Algorithmica 29, 307–369 (2001) · Zbl 1035.68039 · doi:10.1007/BF02679623
[22] Coffman, E.G., Eve, J.: File structures using hashing functions. Commun. ACM 13, 427–436 (1970) · Zbl 0216.24203 · doi:10.1145/362686.362693
[23] de la Briandais, R.: File searching using variable length keys. In: Proceedings of the Western Joint Computer Conference, Montvale, NJ, USA. AFIPS Press (1959)
[24] Dembo, A., Zeitouni, O.: Large Deviation Techniques and Applications, 2nd edn. Springer, Berlin (1998) · Zbl 0896.60013
[25] den Hollander, F.: Large Deviations. American Mathematical Society, Providence, RI (2000) · Zbl 0949.60001
[26] Deuschel, J.-D., Stroock, D.W.: Large Deviations. American Mathematical Society, Providence, RI (1989) · Zbl 0705.60029
[27] Devroye, L.: A note on the height of binary search trees. J. ACM 33, 489–498 (1986) · Zbl 0741.05062 · doi:10.1145/5925.5930
[28] Devroye, L.: Branching processes in the analysis of the heights of trees. Acta Inform. 24, 277–298 (1987) · Zbl 0643.60065 · doi:10.1007/BF00265991
[29] Devroye, L.: On the expected height of fringe balanced trees. Acta Inform. 30, 459–466 (1993) · Zbl 0790.68025 · doi:10.1007/BF01210596
[30] Devroye, L.: Universal limit laws for depth in random trees. SIAM J. Comput. 28(2), 409–432 (1998) · Zbl 0915.68089 · doi:10.1137/S0097539795283954
[31] Devroye, L., Jabbour, J., Zamora-Cura, C.: Squarish k-d trees. SIAM J. Comput. 30, 1678–1700 (2001) · Zbl 0977.68024 · doi:10.1137/S0097539799358926
[32] Duch, A.: Design and Analysis of Multidimensional Data Structures. Ph.D. thesis, UPC, Barcelona (2004) · Zbl 1116.68402
[33] Duch, A., Estivill-Castro, V., Martínez, C.: Randomized k-dimensional binary search trees. In: Chwa, K.-Y., Ibarra, O.H.(eds) Proc. of the 9th International Symposium on Algorithms and Computation (ISAAC’98), vol. 1533 of Lecture Notes in Computer Science, pp. 199–208. Springer, Berlin (1998)
[34] Duch, A., Martínez, C.: On the average performance of orthogonal range search in multidimensional data structures. J. Algorithms 44(1), 226–245 (2002) · Zbl 1010.68048 · doi:10.1016/S0196-6774(02)00213-4
[35] Ellis, R.S.: Large deviations for a general class of random vectors. Ann. Probab. 12, 1–12 (1984) · Zbl 0534.60026 · doi:10.1214/aop/1176993370
[36] Finkel, R.A., Bentley, J.L.: Quad trees, a data structure for retrieval on composite keys. Acta Inform. 4, 1–19 (1974) · Zbl 0302.68055 · doi:10.1007/BF00288933
[37] Flajolet, P.: The ubiquitous digital tree. In: Durand, B., Thomas, W.(eds) STACS 2006, Annual Symposium on Theoretical Aspects of Computer Science, vol 3884 of Lecture Notes in Computer Science, pp. 1–22. Springer, Berlin (2006) · Zbl 1136.68364
[38] Flajolet, P., Puech, C.: Partial match retrieval of multidimensional data. J. ACM 33(2), 371–407 (1986) · doi:10.1145/5383.5453
[39] Fredkin, E.: Trie memory. Commun. ACM 3(9), 490–499 (1960) · doi:10.1145/367390.367400
[40] Gärtner, J.: On large deviations from the invariant measure. Theory Probabab. Appl. 22, 24–39 (1977) · Zbl 0375.60033 · doi:10.1137/1122003
[41] Gastwirth, J.L., Bhattacharya, P.K.: Two probability models of pyramid or chain letter schemes demonstrating that their promotional claims are unreliable. Oper. Res. 32(3), 527–536 (1984) · Zbl 0544.90062 · doi:10.1287/opre.32.3.527
[42] Gonnet, G.H., Baeza-Yates, R.: Handbook of Algorithms and Data Structures, 2nd edn. Addison-Wesley, Workingham (1991) · Zbl 0755.68063
[43] Graham, R.L., Knuth, D.E., Patashnik, O.: Concrete Mathematics, 2nd edn. Addison-Wesley, Reading, MA (1994) · Zbl 0836.00001
[44] Groeneboom, P., Oosterhoff, J., Ruymgaart, F.H.: Large deviation theorems for empirical probability measures. Ann. Probab. 7, 553–586 (1979) · Zbl 0425.60021 · doi:10.1214/aop/1176994984
[45] Hoare, C.A.R.: Quicksort. Comput. J. 5, 10–15 (1962) · Zbl 0108.13601 · doi:10.1093/comjnl/5.1.10
[46] Huffman, D.A.: A method for constructing minimum redundancy codes. In: Proceedings of the Institude of Radio Engineers, pp. 1098–1102 (1952) · Zbl 0137.13605
[47] Knuth, D.E.: The Art of Computer Programming: Sorting and Searching, vol. 3. Addison-Wesley, Reading, MA (1973) · Zbl 0302.68010
[48] Konheim, A.G., Newman, D.J.: A note on growing binary trees. Discrete Math. 4, 57–63 (1973) · Zbl 0247.05105 · doi:10.1016/0012-365X(73)90114-3
[49] Lynch, W.C.: More combinatorial properties of certain trees. Comput. J. 7, 299–302 (1965) · Zbl 0136.38801
[50] Mahmoud, H.M.: A strong law for the height of random binary pyramids. Ann. Appl. Probab. 4, 923–932 (1994) · Zbl 0812.60073 · doi:10.1214/aoap/1177004977
[51] Martínez, C., Panholzer, A., Prodinger, H.: Partial match in relaxed multidimensional search trees. Algorithmica 29(1–2), 181–204 (2001) · Zbl 0967.68054 · doi:10.1007/BF02679618
[52] Martínez, C., Roura, S.: Optimal sampling strategies in quicksort and quickselect. SIAM J. Comput. 31, 683–705 (2001) · Zbl 0996.68038 · doi:10.1137/S0097539700382108
[53] Morrison, D.R.: Patricia–Practical Algorithm To Retrieve Information Coded in Alphanumeric. J. ACM 15, 514–534 (1968) · doi:10.1145/321479.321481
[54] Neininger, R., Rüschendorf, L.: A survey of multivariate aspects of the contraction method. Discrete Math. Theor. Comput. Sci. 8, 31–56 (2006) · Zbl 1157.60307
[55] Nerman, O.: On the convergence of a supercritical general (C-M-J) branching process. Zeitschrift für Wahrscheinlichkeitstheorie verwandte Gebiete 57, 365–395 (1981) · Zbl 0451.60078 · doi:10.1007/BF00534830
[56] Pittel, B.: Note on the height of random recursive trees and m-ary search trees. Random Struct. Algorithms 5, 337–347 (1994) · Zbl 0790.05077 · doi:10.1002/rsa.3240050207
[57] Rachev, S.T., Rüschendorf, L.: Probability metrics and recursive algorithms. Adv. Appl. Probab. 27, 770–799 (1995) · Zbl 0829.60094 · doi:10.2307/1428133
[58] Rockafellar, R.: Convex Analysis. Princeton University Press, Princeton, NJ (1970) · Zbl 0193.18401
[59] Rösler, U.: A fixed point theorem for distributions. Stochastic Process. Appl. 37, 195–214 (1992) · Zbl 0761.60015 · doi:10.1016/0304-4149(92)90035-O
[60] Rösler, U., Rüschendorf, L.: The contraction method for recursive algorithms. Algorithmica 29, 3–33 (2001) · Zbl 0967.68166 · doi:10.1007/BF02679611
[61] Samet, H.: Applications of Spatial Data Structures: Computer Graphics, Image Processing, and GIS. Addison-Wesley, Reading, MA (1990)
[62] Samet, H.: The Design and Analysis of Spatial Data Structures. Addison-Wesley, Reading, MA (1990) · Zbl 0719.90022
[63] Sedgewick, R., Flajolet, P.: An Introduction to the Analysis of Algorithm. Addison-Wesley, Reading, MA (1996) · Zbl 0841.68059
[64] Smythe, R.T., Mahmoud, H.M.: A survey of recursive trees. Theor. Probab. Math. Statist. 51, 1–27 (1995) · Zbl 0933.05038
[65] Szpankowski, W.: Average Case Analysis of Algorithms on Sequences. Wiley, New York (2001) · Zbl 0968.68205
[66] Van Emden, M.: Increasing the efficiency of quicksort. Commun. ACM 13, 563–567 (1970) · Zbl 0198.50703 · doi:10.1145/362736.362753
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.