Séminaire du 6 décembre 2010, 14h00:
Cecilia Holmgren, Algorithms, INRIA Paris-Rocquencourt.
The Total Path Length of Split Trees
By using renewal theory we prove convergence in distribution of the
total path length, i.e., the sum of all depths, for the entire class
of random split trees introduced by Devroye. Many split trees are
models of sorting algorithms and data structures and the total path
length is a natural cost measure of the sorting algorithm. Split trees
include e.g., search trees, m-ary search trees, quad trees,
median of (2k+1)-trees, simplex trees, tries and digital search
trees.
Virginie Collette
Last modified: Thu Nov 18 15:48:21 CET 2010