A q -Analogue of the Path Length of Binary Search Trees

被引：0

作者：

H. Prodinger

机构：

[1] The John Knopfmacher Centre for Applicable Analysis and Number Theory,

[2] School of Mathematics,undefined

[3] ,undefined

[4] University of the Witwatersrand,undefined

[5] P.O. Wits,undefined

[6] 2050 Johannesburg,undefined

[7] South Africa. helmut@gauss.cam.wits.ac.za. http://www.wits.ac.za/helmut/index.htm.,undefined

来源：

Algorithmica | 2001年 / 31卷

关键词：

Key words. Binary search tree, Path length, Permutations, Geometric distribution, q -Analogues, Harmonic numbers.;

D O I：

暂无

中图分类号：

学科分类号：

摘要：

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

页数：8