Binary Search Trees, Recurrent Properties andWave Equations

Article type: Research Article

Authors: Fernández-Camacho, María-Inés | Sánchez-Couso, José-Ramón

Affiliations: Dpto. Sistemas Informáticos y Computación, Facultad CC. Matemáticas, Universidad Complutense. 28040 Madrid, Spain. E-mail: minesfc@sip.ucm.es | Dpto. de Lenguajes, Proyectos y Sistemas Informáticos, E.U. de Informática, Universidad Politécnica (UPM), Crta. Valencia Km. 7. 28031 Madrid, Spain. E-mail: jcouso@eui.upm.es

Abstract: 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.

Keywords: Average case analysis, generating function, binary search tree, singularity analysis, integral equation, asymptotic expansion

Journal: Fundamenta Informaticae, vol. 81, no. 4, pp. 409-439, 2007