On the average size of the intersection of binary trees

Abstract

The average-case analysis of algorithms for binary search trees yields very different results from those obtained under the uniform distribution. The analysis itself is more complex and replaces algebraic equations by integral equations. In this work this analysis is carried out for the computation of the average size of the intersection of two binary trees. The development of this analysis involves Bessel functions that appear in the solutions of partial differential equations, and the result has an average size of $O(n^{2\sqrt 2 - 2} /\sqrt {\log n} )$, contrasting with the size $O(1)$ obtained when considering a uniform distribution.

Postprint (published version)