Back to search

University of British Columbia

Some new results on constructing optimal alphabetic binary trees

Abstract

dc:description

This thesis studies the question of whether optimal alphabetic binary trees can be constructed in o(n lg n) time. Hu and Tucker [1] gave the first subquadratic algorithm in 1971, namely an O(n lg n) time algorithm. Optimal alphabetic binary trees have many applications and the question of whether an o(n lg n) time algorithm exists has remained an open problem in data structures for the last 20 years. We show that a class of techniques for finding optimal alphabetic trees which includes all current methods yielding O(n lg n) time algorithms are at least as hard as sorting in whatever model of computation used. We introduce a new idea for finding optimal alphabetic binary trees which we refer to as region-processing. Region-processing methods have been successfully used to give O(n) time algorithms for the case where all the input weights are within a constant factor of one another and when they are exponentially separated. Although the region based method we give exhibits o(n lg n) time performance for many cases, we also show a reduction from sorting to it as well. It is possible that the ideas used in this reduction can be extended to yield a general ω(n) lower bound.

Degree

thesis:*
Name thesis:degree_name
Master of Science - MSc
Level thesis:degree_level
master's
Discipline thesis:degree_discipline
Computer Science
Grantor dc:publisher
University of British Columbia
Year dc:date
1992

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Mumey, Brendan M.

Rights

dc:rights
Statement dc:rights
  • For non-commercial purposes only, such as research, private study and education. Additional conditions apply, see Terms of Use https://open.library.ubc.ca/terms_of_use.
Language dc:language
eng

Identifiers

dc:identifier.*
Handle dc:identifier
http://hdl.handle.net/2429/3384

Chain of custody

source
Harvested from
University of British Columbia
Base URL
circle.library.ubc.ca/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
related terms
citation

Mumey, Brendan M.. Some new results on constructing optimal alphabetic binary trees. master's thesis, University of British Columbia, 1992. http://hdl.handle.net/2429/3384