RT Journal Article
T1 Reductions in binary search trees
A1 Sánchez Couso, José Ramón
A1 Fernández Camacho, María Inés
AB We analyze two bottom-up reduction algorithms over binary trees that represent replaceable data within a certain system, assuming the binary search tree (BST) probabilistic model. These reductions are based on idempotent and nilpotent operators, respectively. In both cases, the average size of the reduced tree, as well as the cost to obtain it, is asymptotically linear with respect to the size of the original tree. Additionally, the limiting distributions of the size of the trees obtained by means of these reductions satisfy a central limit law of Gaussian type.
PB Elsevier Science
SN 0304-3975
YR 2006
FD 2006-04
LK https://hdl.handle.net/20.500.14352/50542
UL https://hdl.handle.net/20.500.14352/50542
LA eng
DS Docta Complutense
RD 7 abr 2025