Premium
On the distribution of binary search trees under the random permutation model
Author(s) -
Fill James Allen
Publication year - 1996
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/(sici)1098-2418(199601)8:1<1::aid-rsa1>3.0.co;2-1
Subject(s) - random binary tree , mathematics , combinatorics , random permutation , permutation (music) , independent and identically distributed random variables , markov chain , distribution (mathematics) , binary search tree , tree (set theory) , discrete mathematics , uniform distribution (continuous) , binary tree , binary number , set (abstract data type) , asymptotic distribution , random variable , statistics , computer science , mathematical analysis , symmetric group , physics , arithmetic , estimator , acoustics , programming language
We study the distribution Q on the set B n of binary search trees over a linearly ordered set of n records under the standard random permutation model. This distribution also arises as the stationary distribution for the move‐to‐root (MTR) Markov chain taking values in B n when successive requests are independent and identically distributed with each record equally likely. We identify the minimum and maximum values of the functional Q and the trees achieving those values and argue that Q is a crude measure of the “shape” of the tree. We study the distribution of Q ( T ) for two choices of distribution for random trees T ; uniform over B n and Q . In the latter case, we obtain a limiting normal distribution for −ln Q ( T ). © 1996 John Wiley & Sons, Inc.