Loading...
Loading...

Go to the content (press return)

On the number of descendants and ascendants in random search trees

Author
Martinez, C.; Prodinger, H.
Type of activity
Report
Date
1997-01
Code
R97-1
Repository
http://hdl.handle.net/2117/96448 Open in new window
Abstract
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 an...
Citation
Martinez, C., Prodinger, H. "On the number of descendants and ascendants in random search trees". 1997.
Keywords
Ascendants, Descendants, Probabilistic analysis, Random search trees
Group of research
ALBCOM - Algorithms, Computational Biology, Complexity and Formal Methods

Participants

Attachments