An Analysis of Binary Search Trees Formed from Sequences of Nondistinct Keys
- 1 July 1976
- journal article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 23 (3) , 451-454
- https://doi.org/10.1145/321958.321965
Abstract
The expected depth of each key in the set of binary search trees formed from all sequences composed from a multiset { p 1 · 1, p 2 · 2, p 3 · 3, ···, p n · n } is obtained, and hence the expected weight of such trees. The expected number of left-to-right local minima and the expected number of cycles in sequences composed from a multiset are then deduced from these results.Keywords
This publication has 3 references indexed in Scilit:
- Randomized binary search techniqueCommunications of the ACM, 1969
- Réarrangements de SuitesPublished by Springer Nature ,1969
- Problèmes combinatoires de commutation et réarrangementsLecture Notes in Mathematics, 1969