On the joint distribution of the insertion path length and the number of comparisons in search trees (Q1121028)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On the joint distribution of the insertion path length and the number of comparisons in search trees |
scientific article |
Statements
On the joint distribution of the insertion path length and the number of comparisons in search trees (English)
0 references
1988
0 references
A special type of an m-ary search tree successively created by insertion of n distinct numbers (keys) is considered. The sequence of the keys is supposed to be random. To insert the \((n+1)th\) key into the search tree one has to exercise \(C_ n\) comparisons and the key is placed into a note on \(L_ n\) level. The paper presents a proof, based on the Laplace transform, of the assertion claiming that the random vector \(L_ n\), \(C_ n\) is asymptotically Gaussian with the mean and the covariance matrix dependent only on m and the first and second order moments of the local (i.e. within one node) search.
0 references
number of comparisons
0 references
asymptotic properties
0 references
m-ary search tree
0 references