dc.contributor
Universitat Politècnica de Catalunya. Departament de Teoria del Senyal i Comunicacions
dc.contributor
Facultat d'Informàtica de Barcelona
dc.contributor
Universitat Politècnica de Catalunya. ALBCOM - Algorismia, Bioinformàtica, Complexitat i Mètodes Formals
dc.contributor.author
Baeza Yates, Ricardo
dc.contributor.author
Cases Muñoz, Rafel
dc.contributor.author
Díaz Cort, Josep
dc.contributor.author
Martínez Parra, Conrado
dc.identifier
Baeza, R., Cases, R., Diaz, J., Marínez, C. "On the average size of the intersection of binary trees". 1989.
dc.identifier
https://hdl.handle.net/2117/110571
dc.description.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.
dc.description.abstract
Postprint (published version)
dc.format
application/pdf
dc.subject
Àrees temàtiques de la UPC::Informàtica::Enginyeria del software
dc.subject
Trees (Graph theory)
dc.subject
Arbres (Teoria de grafs)
dc.title
On the average size of the intersection of binary trees
dc.type
External research report
