On the joint distribution of the insertion path length and the number of comparisons in search trees
type: Item
instance of: scholarly article
title: On the joint distribution of the insertion path length and the number of comparisons in search trees
zbMATH Open document ID: 0673.68044
DOI: 10.1016/0166-218X(88)90080-7
author: Hosam M. Mahmoud
author: Boris Pittel
published in: Discrete Applied Mathematics
publication date: 1988-01-01T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 68P10
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 05C05
zbMATH DE Number: 4102503
zbMATH Keywords: number of comparisons
zbMATH Keywords: asymptotic properties
zbMATH Keywords: m-ary search tree
reviewed by: Radim Jiroušek
MaRDI profile type: Publication
cites work: Q5585020
cites work: On the Most Probable Shape of a Search Tree Grown from a Random Permutation
cites work: On growing random binary trees
Recommended article: On the Joint Path Length Distribution in Random Binary Trees
Recommended article: Analysis of the space of search trees under the random insertion algorithm
Recommended article: On the height of random m‐ary search trees
Recommended article: On the average cost of insertions on random relaxed K-d trees
Recommended article: An almost sure result for path lengths in binary search trees
Recommended article: Q4868264
Recommended article: An Improved Bound for Random Binary Search Trees with Concurrent Insertions
Recommended article: EXTREMAL WEIGHTED PATH LENGTHS IN RANDOM BINARY SEARCH TREES
description: scientific article; zbMATH DE number 4102503