Average-case analysis of pattern-matching in trees under the BST probability model

Abstract

We analyze the average behaviour under the bst probability model of the simplest and most commonly used sequential tree-matching algorithm. When the uniform probability model for the input is assumed, it is well known that it takes O(n) steps on average to search all occurrences of a random pattern P in a random text T of joint size n. Under the bst probability model the analysis is itself more complex, involving the solution of partial differential equations. Nevertheless the difficulty to solve one of partial differential equations concerned leads us to seek for analytic properties of that solution which allow us to conclude, without the explicit knowledge of that solution, the main result: searching for all occurrences of a random pattern in a random binary tree of joint size n and distributed accordingly to the bst probability model is O(n ln n) on the average.