28
Views
0
CrossRef citations to date
0
Altmetric
Original Articles

Optimal binary search trees

Pages 135-151 | Received 01 Jul 1985, Published online: 19 Mar 2007
 

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

Reprints and Corporate Permissions

Please note: Selecting permissions does not provide access to the full text of the article, please see our help page How do I view content?

To request a reprint or corporate permissions for this article, please click on the relevant link below:

Academic Permissions

Please note: Selecting permissions does not provide access to the full text of the article, please see our help page How do I view content?

Obtain permissions instantly via Rightslink by clicking on the button below:

If you are unable to obtain permissions via Rightslink, please complete and submit this Permissions form. For more information, please visit our Permissions help page.