Binary Search Trees, Recurrent Properties and Wave Equations

• Autorzy: Fernández-Camacho M-I. , Sánchez-Couso J-R.
• Języki publikacji: EN

Abstrakty

EN

We give a generic framework to analyze the average-case running time for computing the so called recurrent properties for pairs of binary search trees. Recurrent properties are algorithms that operate on pairs of trees testing some characteristic on nodes by performing a preorder traversal on both trees. Analysis of recurrent properties using the probability model associated with randomly grown binary search trees leads to wave equations. We use a "normalized" integral equation as a pattern to model a specific wave equation and investigate the asymptotic behavior of its solution. This methodology is applied to some particular cases of recurrent properties like testing equality, detecting direct occurrences and clashes or pattern matching.

Słowa kluczowe

EN

average case analysis; generating functions; binary search tree; singularity analysis; integral equation; asymptotic expansion

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2007
• Tom: Vol. 81, nr 4
• Strony: 409--439
• Opis fizyczny: bibliogr. 42 poz., wykr.

Twórcy

autor

Fernández-Camacho M-I.

autor

Sánchez-Couso J-R.

• Department Sistemas Informaticos y Computacion, Facultad CCV. Matematicas, , Universidad Complutense 28040 Madrid, Spain,

Bibliografia

• [1] Abramowitz M., Stegun, I. A.: Handbook of Mathematical functions, Dover Publ., New York, 1964.
• [2] Albert, L., Casas, R., Fages, F.: Average-case analysis of unification algorithms, Theoretical Computer Science, 113, 1993, 3-34.
• [3] Aragon, C. R., Seidel, R. G.: Randomized search trees, in: 30th Annual Symposium on Foundations of Computer Science, IEEE Computer Society, 1989, 540-545.
• [4] Bellman, J.: Stability Theory of Differential Equations, Mc-Graw Hill, 1953.
• [5] Bender, C. M., Orszag, S. A.: Advanced Mathematical Methods for Scientists and Engineers, Mc-Graw Hill Inc, 1978. Reprinted by Springer-Verlag, New York Inc, 1999.
• [6] Casas, R., Díaz. J., Martínez, C.: Statistics on random trees, in: Proc. of the 18th ICALP (J. Leach, B.Monien, M. Rodriguez-Artalejo, Eds.), LNCS 510, 1991, 186-203.
• [7] Casas, R., Fernández-Camacho,M. I., Steyaert, J. M.: Algebraic simplification in computer algebra: an analysis of bottom-up algorithms, Theoretical Computer Science, 74(3), 1990, 273-298.
• [8] Copson, E. T.: Partial Differential Equations, Cambridge University Press, 1975.
• [9] Fernández-Camacho, M. I.: Análisis Medio de Algoritmos de Reducción sobre Arboles, PhD. thesis, Universidad Complutense de Madrid, 1988.
• [10] Fill, J. A., Flajolet, P., Kapur, N.: Singularity analysis, Hadamard products and tree recurrences, Journal of Computational and Applied Mathematics, vol. 174, 2005, 271-313.
• [11] Flajolet, P., Odlyzko, A.: Singularity analysis of generating functions, SIAM J. on Discrete Mathematics, vol. 3, No. 2, 1990, 216-240.
• [12] Flajolet, P., Sedgewick, R.: The average case analysis of algorithms: Counting and generating functions, Research Report 1888, INRIA, March 1993.
• [13] Flajolet, P., Sedgewick, R.: The average case analysis of algorithms: Complex asymptotics and generating functions, Research Report 2026, INRIA, September 1993.
• [14] Goulden, I., Jackson, D.: Combinatorial Enumerations, JohnWiley, New York, 1983.
• [15] Gradshteyn, I. S., Ryzhik, I. M.: Table of Integrals, Series and Products, Ed. Academic Press Inc, 1980.
• [16] Gustafson, K. E.: Introduction to Partial Differential Equations and Hilbert Space Methods, John Wiley &Sons, Inc., 2nd Ed., 1987.
• [17] Guzmán, M.: Ecuaciones Diferenciales Ordinarias. Teoría de Estabilidad y Control, Ed. Alhambra, Madrid 1980.
• [18] Hardy, G. H.: Divergent Series, Oxford University Press, London, 1949.
• [19] Henrici, P.: Applied and Computational Complex Analysis, vol. 1 and 2,Wiley Interscience, New York, 1977.
• [20] Hoffmann, C. M., O'Donnell,M. J.: Pattern matching in trees, Journal of the ACM, vol. 29, No. 1, 1982, 68-95.
• [21] Knessl, C., Szpankowski,W.: The height of a binary search tree: the limiting distribution perspective, Theoretical Computer Science, 289(1), 2002, 649-703.
• [22] Knight, K.: Unification: a multidisciplinary survey, ACM Comp. Surveys 21, 1989, 93-124.
• [23] Knuth, D. E.: The Art of Computer Programming: Sorting and Searching, vol. 3, Addison-Wesley, Reading, MA, 1973.
• [24] Knuth, D. E., Bendix, P.: Simple word problems in universal algebras, in: Computational Problems in Abstract Algebra (J. Leech, Ed.), Pergamon Press, 1970, 263-397.
• [25] Kreyszig, E.: Introductory Functional Analysis with Applications, Wiley Classics Library, J. Wiley & Sons, New York, 1989.
• [26] Maddox, I. J.: Elements of Functional Analysis, Cambridge University Press, 2nd. Ed., 1988.
• [27] Mahmoud, H.: Evolution of Random Search Trees, John Wiley, New York, 1992.
• [28] Martínez, C.: Statistics under the BST Model, PhD. thesis, U. Politécnica de Cataluña, April 1992.
• [29] Martínez, C., Panholzer, A., Prodinger, H.: Partial match queries in relaxed multidimensional search trees, Algorithmica 29(1), 2001, 181-204.
• [30] Motwani, R., Raghavan, P.: Randomized Algorithms, Cambridge Univ. Press, 1995.
• [31] Polyanin, A. D., Zaitsev, V. F.: Handbook of Exact Solutions for Ordinary Differential Equations, Chapman & Hall/CRC, 2nd Ed., 2003.
• [32] Polyanin, A. D., Zaitsev, V. F.: Handbook of Nonlinear Partial Differential Equations.Chapman&Hall/CRC, 2004.
• [33] Robinson, J. A.: Computational logic: the unification computation, in: Machine Intelligence (B. Meltzer, D. Michie, Eds.), vol. 6, Elsevier, New York, 1971.
• [34] Sánchez-Couso, J. R., Fernández-Camacho, M. I.: Average-case analysis of pattern matching in trees under the BST probability model, in: Proc. of the 21st ICALP (Shamir, Ed.), LNCS 820, 1994, 178-190.
• [35] Sánchez-Couso, J. R., Fernández-Camacho, M. I.: Reductions in binary search trees, Theoretical Computer Science, 355(3), 2006, 327-353.
• [36] Sedgewick, R., Flajolet, P.: An Introduction to the Analysis of Algorithms, Addison-Wesley Publishing Company, 1996.
• [37] Steyaert, J. M.: Structure et Complexité des Algorithmes, PhD. thesis, Université Paris, April 1984.
• [38] Steyaert, J. M., Flajolet, P.: Patterns and pattern-matching in trees : an analysis, Information and Control 58, 1983, 19-58.
• [39] Titchmarsh, E. C.: The Theory of Functions, Oxford University Press, Oxford, 1939.
• [40] Vitter, J. S., Flajolet, P.: Average-case analysis of algorithms and data structures, in: Handbook of Theoretical Computer Science (Jan van Leeuwen, Ed.), vol. A: Algorithms and Complexity (A), 1990, 431-524.
• [41] Vuillemin, J.: A unifying look at data structures, Communications of the ACM 23, 4, 1980, 229-239.
• [42] Zwillinger, D.: Handbook of Differential Equations, Academic Press, San Diego, CA, 1989.