On random Cartesian trees. (English) Zbl 0792.05124
Summary: Cartesian trees are binary search trees in which the nodes exhibit the heap property according to a second (priority) key. If the search key and the priority key are independent, and the tree is built based on \(n\) independent copies, Cartesian trees basically behave like ordinary random binary search trees. In this article, we analyze the expected behavior when the keys are dependent: in most cases, the expected search, insertion, and deletion times are \(\Theta (\sqrt n)\). We indicate how these results can be used in the analysis of divide-and-conquer algorithms for maximal vectors and convex hulls. Finally, we look at distributions for which the expected time per operation grows like \(n^ a\) for \(a \in[1/2,1)\).
Keywords:
random trees; Cartesian trees; binary search trees; divide-and-conquer algorithms; maximal vectors; convex hullsReferences:
| [1] | Aho, Data Structures and Algorithms (1983) |
| [2] | C. R. Aragon R. G. Seidel Randomized search trees Proceedings of the 29th IEEE Symposium on the Foundations of Computer Science 1988 1 6 |
| [3] | Bentley, Proceedings of the First Annual ACMSIAM Symposium on Discrete Algorithms pp 179– (1990) |
| [4] | Bentley, On the average number of maxima in a set of vectors and applications, J. Assoc. Comput. Mach. 25 pp 536– (1982) · Zbl 0388.68056 · doi:10.1145/322092.322095 |
| [5] | Bentley, Divide and conquer for linear expected time, Inf. Process. Lett. 7 pp 87– (1978) · Zbl 0404.68046 |
| [6] | Buchta, On the average number of maxima in a set of vectors, Inf., Process. Lett. 33 pp 63– (1989) · Zbl 0682.68041 |
| [7] | Chernoff, A measure of asymptotic efficiency of tests of a hypothesis based on the sum of observations, Ann. Math. Stat. 23 pp 493– (1952) · Zbl 0048.11804 |
| [8] | K. L. Clarkson P. W. Shor Algorithms for diametrical pairs and convex hulls that are optimal, randomized, and incremental Proceedings of the Fourth Symposium on Computational Geometry, ACM 1988 12 17 |
| [9] | Clarkson, Applications of random sampling in computational geometry II, Discrete Comput. Geom. 4 pp 387– (1989) · Zbl 0681.68060 |
| [10] | Cormen, Introduction to Algorithms (1990) |
| [11] | Devroye, A note on finding convex hulls via maximal vectors, Inf., Process. Lett. 11 pp 53– (1980) · Zbl 0444.68063 |
| [12] | Devroye, Moment inequalities for random variables in computational geometry, Computing 30 pp 111– (1983) · Zbl 0502.60016 |
| [13] | Devroye, On the expected time required to construct the outer layer, Inf., Proc. Lett. 20 pp 255– (1985) · Zbl 0572.68032 |
| [14] | Devroye, A note on the height of binary search trees, J. Assoc. Comput. Mach. 33 pp 489– (1986) · Zbl 0741.05062 · doi:10.1145/5925.5930 |
| [15] | Devroye, Lecture Notes on Bucket Algorithms (1986) · Zbl 0644.68086 · doi:10.1007/978-1-4899-3531-1 |
| [16] | Devroye, Branching processes in the analysis of the heights of trees, Acta Inf. 24 pp 277– (1987) · Zbl 0643.60065 · doi:10.1007/BF00265991 |
| [17] | Devroye, Applications of the theory of records in the study of random trees, Acta Inf. 26 pp 123– (1988) · Zbl 0656.68065 |
| [18] | Dwyer, Kinder, gentler average-case analysis for convex hulls and maximal vectors, SIGACT News 21 pp 64– (1990) |
| [19] | Flajolet, The average height of binary trees and other simple trees, J. Comput. Syst. Sci. 25 pp 171– (1982) · Zbl 0499.68027 |
| [20] | J. Françon G. Viennot J. Vuillemin Description and analysis of an efficient priority queue representation Proceedings of the 19th IEEE Symposium on the Foundations of Computer Science 1978 1 7 |
| [21] | H. N. Gabow J. L. Bentley R. E. Tarjan Scaling and related techniques for geometry problems Proceedings of the 16th Annual Symposium on the Theory of Computing 1984 135 143 |
| [22] | Gonnet, A Handbook of Algorithms and Data Structures (1984) |
| [23] | Graham, An efficient algorithm for determining the convex hull of a finite planar set, Inf., Proc. Lett. 1 pp 132– (1972) · Zbl 0236.68013 |
| [24] | Kemp, Fundamentals of the Average Case Analysis of Particular Algorithms (1984) · Zbl 0638.68026 · doi:10.1007/978-3-663-12191-6 |
| [25] | Kirkpatrick, Proceedings of the 2nd Annual Symposium on Computatational Geometry, Baltimore pp 89– (1985) |
| [26] | Knuth, The Art of Computer Programming, Vol. 3: Sorting and Searching (1973) · Zbl 0302.68010 |
| [27] | Kung, On finding the maxima of a set of vectors, J. Assoc. Comput. Mach. 22 pp 469– (1975) · Zbl 0316.68030 · doi:10.1145/321906.321910 |
| [28] | Louchard, Exact and asymptotic distributions in digital and binary search trees, Theor. Inf., Appl. 21 pp 479– (1987) · Zbl 0643.68077 |
| [29] | Lynch, More combinatorial problems on certain trees, Comput. J. 7 pp 299– (1965) · Zbl 0136.38801 · doi:10.1093/comjnl/7.4.299 |
| [30] | Mahmoud, On the average internal path length of m-ary search trees, Acta Inf. 23 pp 111– (1986) |
| [31] | Mahmoud, Evolution of Random Search Trees (1992) · Zbl 0762.68033 |
| [32] | Mahmoud, On the joint distribution of the insertion path length and the number of comparisons in search trees, Discrete Appl. Math. 20 pp 243– (1988) · Zbl 0673.68044 |
| [33] | Mahmoud, On the most probable shape of a search tree grown from a random permutation, SIAM J. Algebraic Discrete Methods 5 pp 69– (1984) · Zbl 0529.05002 |
| [34] | McCreight, Priority search trees, SIAM J. Comput. 14 pp 257– (1985) · Zbl 0564.68050 |
| [35] | Pittel, On growing random binary trees, J. Math. Anal. Appl. 103 pp 461– (1984) · Zbl 0593.60014 |
| [36] | Robson, The height of binary search trees, Aust. Comput. J. 11 pp 151– (1979) |
| [37] | Sedgewick, Probability Theory and Computer Science pp 123– (1983) |
| [38] | Tarjan, Data Structures and Network Algorithms, CBMS 44 (1983) · Zbl 0584.68077 · doi:10.1137/1.9781611970265 |
| [39] | Vitter, Handbook of Theoretical Computer Science, Volume A: Algorithms and Complexity pp 431– (1990) |
| [40] | Vuillemin, A data structure for manipulating priority queues, Commun. ACM 21 pp 309– (1978) · Zbl 0371.68011 |
| [41] | Vuillemin, A unifying look at data structures, Commun. ACM 23 pp 229– (1980) · Zbl 0434.68047 |
| [42] | Wheeden, Measure and Integral (1977) |
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
