Masters Theses
Abstract
"Improving the efficiency of retrieving information concerns users of computer systems involved in many applications- One way of addressing this concern is to organize a sorted sequence into a binary search tree. Knuth's Algorithm K is a bottom-up organization algorithm that always constructs a binary tree which minimizes average search time. However, the cost of executing Algorithm K is prohibitive for a large tree. The aim of this work is to find a less costly method of organizing sorted sequences into nearly-optimal binary search trees.
We present a top-down organization method which yields better average search times than top-down methods already available, specifically height-balancing and weight-balancing. The variation in access frequency among the members of a sequence is used to recommend specific values for some of the parameters in this new method of organization.
The new method improves considerably on the cost of organization as opposed to the cost of using Algorithm K while producing trees whose average search times are close to minimal. The new algorithm yields an average search time that is usually within 1% of the minimal average search time and for every case attempted has been no worse than 1.5% larger than minimal"--Abstract, page ii.
Advisor(s)
Metzner, John R.
Committee Member(s)
Dekock, Arlan R.
Kluczny, Raymond Michael
Department(s)
Computer Science
Degree Name
M.S. in Computer Science
Publisher
University of Missouri--Rolla
Publication Date
Fall 1984
Pagination
v, 50 pages
Note about bibliography
Includes bibliographical references (pages 48-49).
Rights
© 1984 Joy L. Henderson, All rights reserved.
Document Type
Thesis - Open Access
File Type
text
Language
English
Thesis Number
T 5122
Print OCLC #
11594636
Link to Catalog Record
Recommended Citation
Henderson, Joy L., "A simple method for organizing nearly optimal binary search trees" (1984). Masters Theses. 225.
https://scholarsmine.mst.edu/masters_theses/225