2026-06-28T20:32:46Zhttps://docta.ucm.es/rest/oai/request

oai:docta.ucm.es:20.500.14352/505422023-08-27T22:54:34Zcom_20.500.14352_14col_20.500.14352_15

Reductions in binary search trees Sánchez Couso, José Ramón Fernández Camacho, María Inés 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. 2023-06-20T10:33:53Z 2023-06-20T10:33:53Z 2023-06-20T10:33:53Z 2006-04 journal article https://hdl.handle.net/20.500.14352/50542 0304-3975 10.1016/j.tcs.2005.12.015 eng MIDAS TIC2003-01000 restricted access Elsevier Science