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

来源：

ALGORITHMICA | 2001年 / 31卷 / 03期

关键词：

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