Novel characteristics of split trees by use of renewal theory
Novel characteristics of split trees by use of renewal theory
We investigate characteristics of random split trees introduced by Devroye [SIAM J Comput 28, 409-432, 1998]; split trees include e.g., binary search trees, $m$-ary search trees, quadtrees, median of $(2k+1)$-trees, simplex trees, tries and digital search trees. More precisely: We use renewal theory in the studies of split trees, and …