Mixed Poisson approximation of node depth distributions in random binary search trees

Rudolf Grubel, Nikolce Stefanoski

We investigate the distribution of the depth of a node containing a specific key or, equivalently, the number of steps needed to retrieve an item stored in a randomly grown binary…