TY - THES
AU - Mumey, Brendan M.
PY - 1992
TI - Some new results on constructing optimal alphabetic binary trees
KW - Thesis/Dissertation
LA - eng
M3 - Text
AB - 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.
N2 - 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.
UR - https://open.library.ubc.ca/collections/831/items/1.0051343
ER - End of Reference