Abstract
Optimal binary search trees are described in practically every textbook on data structures. It is commonly accepted that since the publication of the paper by Knuth everything about them is known and understood.
This paper shows that it is not necessarily so, and that, in particular, “optimal binary search trees” as normally defined are not optimal at all. Various types of optimal split trees are more efficient than optimal search trees as defined by Knuth.
C.R. Categories:
Now at Deptartment of Computing Science. 615 General Services Building, University of Alberta, Edmonton. Alberta, Canada. T69 2HI
Now at Deptartment of Computing Science. 615 General Services Building, University of Alberta, Edmonton. Alberta, Canada. T69 2HI
Notes
Now at Deptartment of Computing Science. 615 General Services Building, University of Alberta, Edmonton. Alberta, Canada. T69 2HI