On the joint distribution of the insertion path length and the number of comparisons in search trees (Q1121028): Difference between revisions
From MaRDI portal
Set profile property. |
ReferenceBot (talk | contribs) Changed an Item |
||
Property / cites work | |||
Property / cites work: Q5585020 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On the Most Probable Shape of a Search Tree Grown from a Random Permutation / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On growing random binary trees / rank | |||
Normal rank |
Latest revision as of 15:29, 19 June 2024
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