A q-analogue of the path length of binary search trees

被引:3
作者
Prodinger, H [1 ]
机构
[1] Univ Witwatersrand, Sch Math, John Knopfmacher Ctr Applicable Anal & Number The, ZA-2050 Johannesburg, South Africa
关键词
binary search tree; path length; permutations; geometric distribution; q-analogues; harmonic numbers;
D O I
10.1007/s00453-001-0058-y
中图分类号
TP31 [计算机软件];
学科分类号
081202 [计算机软件与理论]; 0835 [软件工程];
摘要
A reformulation of the path length of binary search trees is given in terms of permutations, allowing us to extend the definition to the instance of words, where the letters are obtained by independent geometric random variables (with parameter q). In this way, expressions for expectation and variance are obtained which in the limit for q --> 1 are the classical expressions.
引用
收藏
页码:433 / 441
页数:9
相关论文
共 5 条
[1]
[Anonymous], 1998, SORTING SEARCHING
[2]
[Anonymous], 1994, FDN COMPUTER SCI
[3]
Mahmoud H, 1992, EVOLUTION RANDOM SEA
[4]
PRODINGER H, 2001, IN PRESS ANN COMBINA
[5]
Sedgewick Robert., 2013, INTRO ANAL ALGORITHM