1993 Reports
New Lower Bounds on the Cost of Binary Search Trees
In this paper we provide new lower bounds on the cost of binary search trees. The bounds are expressed in terms of the entropy of the probability distribution, the number of elements and the probability that a search is successfully. Most of our lower bounds are derived by means of a new technique which exploits the relation between trees and codes. Our lower bounds compare favorably with known limitations. We also provide an achievable upper bound on the Kraft sum generalized to the internal nodes of a tree. This improves on a previous result.
Subjects
Files
- cucs-031-93.pdf application/pdf 163 KB Download File
More About This Work
- Academic Units
- Computer Science
- Publisher
- Department of Computer Science, Columbia University
- Series
- Columbia University Computer Science Technical Reports, CUCS-031-93
- Published Here
- January 27, 2012