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

Download

Share

 
COinS