Title:
|
On the average size of the intersection of binary trees
|
Author:
|
Baeza Yates, Ricardo; Cases Muñoz, Rafel; Diaz Cort, Josep; Martínez Parra, Conrado
|
Other authors:
|
Universitat Politècnica de Catalunya. Departament de Teoria del Senyal i Comunicacions; Facultat d'Informàtica de Barcelona; Universitat Politècnica de Catalunya. ALBCOM - Algorismia, Bioinformàtica, Complexitat i Mètodes Formals |
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. |
Subject(s):
|
-Àrees temàtiques de la UPC::Informàtica::Enginyeria del software -Trees (Graph theory) -Arbres (Teoria de grafs) |
Rights:
|
|
Document type:
|
Article - Published version Report |
Share:
|
|