Para acceder a los documentos con el texto completo, por favor, siga el siguiente enlace: http://hdl.handle.net/2117/96448

On the number of descendants and ascendants in random search trees
Martínez Parra, Conrado; Prodinger, Helmut
Universitat Politècnica de Catalunya. Departament de Ciències de la Computació
We consider here the probabilistic analysis of the number of descendants and the number of ascendants of a given internal node in a random search tree. The performance of several important algorithms on search trees is closely related to these quantities. For instance, the cost of a successful search is proportional to the number of ascendants of the sought element. On the other hand, the probabilistic behavior of the number of descendants is relevant for the analysis of paged data structures and for the analysis of the performance of quicksort, when recursive calls are not made on small subfiles. We also consider the number of ascendants and descendants of a random node in a random search tree, i.e., the grand averages of the quantities mentioned above. We address these questions for standard binary search trees and for locally balanced search trees. These search trees were introduced by Poblete and Munro and are binary search trees such that each subtree of size 3 is balanced; in other words, binary search trees where there are not two adjacent internal nodes with only one son each. In this work, we follow a purely combinatorial approach, extensively using generating functions, and derive exact and asymptotic expressions for the probability distribution and moments of some of the considered quantities, finding several new results as well as alternative derivations for already known results.
Àrees temàtiques de la UPC::Informàtica::Informàtica teòrica
Random search trees
Probabilistic analysis
Descendants
Ascendants
info:eu-repo/semantics/publishedVersion
Informe
         

Mostrar el registro completo del ítem

Documentos relacionados

Otros documentos del mismo autor/a

Martínez Parra, Conrado; Panholzer, Alois; Prodinger, Helmut
Duch Brown, Amalia; Lau Laynes-Lozada, Gustavo Salvador; Martínez Parra, Conrado
Kirschenhofer, P; Martínez Parra, Conrado; Prodinger, H
Martínez Parra, Conrado; Pahnholzer, A; Prodinger, H
Roura Ferret, Salvador; Martínez Parra, Conrado