LIMIT LAWS FOR LOCAL COUNTERS IN RANDOM BINARY SEARCH-TREES

被引：43

作者：

DEVROYE, L

机构：

[1] School of Computer Science, McCill University, Montreal, H3A2K6

来源：

RANDOM STRUCTURES & ALGORITHMS | 1991年 / 2卷 / 03期

关键词：

BINARY SEARCH TREE; DATA STRUCTURES; PROBABILISTIC ANALYSIS; LIMIT LAW; CONVERGENCE; UNIFORM RANDOM RECURSIVE TREES; RANDOM TREES;

D O I：

10.1002/rsa.3240020305

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 ; 0835 ;

摘要：

Limit laws for several quantities in random binary search trees that are related to the local shape of a tree around each node can be obtained very simply by applying central limit theorems for m-dependent random variables. Examples include: the number of leaves (L(n)), the number of nodes with k descendants (k fixed), the number of nodes with no left child, the number of nodes with k left descendants. Some of these results can also be obtained via the theory of urn models, but the present method seems easier to apply.

引用

页码：303 / 315

页数：13

共 28 条

[1]

Aho A., 1983, DATA STRUCTURES ALGO

[2]

ALDOUS D, 1990, ASYMPTOTIC FRINGE DI

[3]

Athreya K., 1972, BRANCHING PROCESSES, DOI DOI 10.1007/978-3-642-65371-1

[4] ASYMPTOTIC NORMALITY IN THE GENERALIZED POLYA-EGGENBERGER URN MODEL, WITH AN APPLICATION TO COMPUTER-DATA STRUCTURES [J].