𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On the joint distribution of the insertion path length and the number of comparisons in search trees

✍ Scribed by Hosam M. Mahmoud; Boris Pittel

Publisher
Elsevier Science
Year
1988
Tongue
English
Weight
786 KB
Volume
20
Category
Article
ISSN
0166-218X

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

On the internal path length of d-dimensi
On the internal path length of d-dimensional quad trees
✍ Ralph Neininger; Ludger RΓΌschendorf πŸ“‚ Article πŸ“… 1999 πŸ› John Wiley and Sons 🌐 English βš– 241 KB

It is proved that the internal path length of a d-dimensional quad tree after normalization converges in distribution. The limiting distribution is characterized as a fixed point of a random affine operator. We obtain convergence of all moments and of the Laplace transforms. The moments of the limit

On the joint distribution of the nodes i
On the joint distribution of the nodes in uniform multidimensional binary trees
✍ Rainer Kemp πŸ“‚ Article πŸ“… 1998 πŸ› John Wiley and Sons 🌐 English βš– 313 KB πŸ‘ 2 views

Multidimensional binary trees represent a symbiosis of trees and tries, and they essentially arise in the construction of search trees for multidimensional keys. The set of nodes in a d-dimensional binary tree can be partitioned into layers according to the nodes appearing in the ith dimension. We d

On the distribution of binary search tre
On the distribution of binary search trees under the random permutation model
✍ James Allen Fill πŸ“‚ Article πŸ“… 1996 πŸ› John Wiley and Sons 🌐 English βš– 865 KB

We study the distribution Q on the set B, 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,, when successive requests ar