More Results on Priority Trees
Tenth Seminar on Analysis of Algorithms
June 14, 2004 11:00 AM to 12:00 PM
Speakers:
|
 |
Abstract: |
In this talk we presented an average case analysis of some quantities of interest of priority trees, which is a data structure used for priority queue administration. Under the so called random permutation model for the data, we can give by generating functions approach limiting distribution results for the quantities “depths of random node”, “recursion depth when inserting a random node' and “number of desecndents of a random node'. Moreover, we obtain asymptotic results for the expected “ancestor-tree size' and the “Steiner-distance” of randomly selected nodes. On our approach a certain combinatorial decomposition of the considered objectsleads via generating functions to systems of differential equations. |
Keywords: |
Analysis of algorithms; Priority queues; priority trees; node depths;recursion depth; Ancestor-tree size; Steiner-distance. |
|
|
