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.

Department(s)

Computer Science

Comments

This report is substantially the M.S. thesis of the first author, completed August, 1984.

Report Number

CSC-84-13

Document Type

Technical Report

Document Version

Final Version

File Type

text

Language(s)

English

Rights

© 1984 University of Missouri--Rolla, All rights reserved.

Publication Date

August 1984

Download

Share

 
COinS