Publication
Journal of the ACM
Paper

An Analysis of Binary Search Trees Formed from Sequences of Nondistinct Keys

Download paper

Abstract

The expected depth of each key in the set of binary search trees formed from all sequences composed from a multiset {p1 · 1, p2 · 2, p3 · 3, ···, pn · 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. © 1976, ACM. All rights reserved.

Date

Publication

Journal of the ACM

Authors

Topics

Resources

Share