Rheinische Friedrich-Wilhelms-Universität Bonn Institut für Informatik
Abteilung V

Universität Bonn -> Institut für Informatik -> Abteilung V
CS-Reports 1995 Copyright 1995 Universität Bonn, Institut für Informatik, Abt. V

Correctness of Constructing Optimal Alphabetic Trees Revisited
Marek Karpinski, Lawrence L. Larmore, Wojciech Rytter
[Download PostScript] [Download PDF]

Several new observations which lead to new correctness proofs of two known algorithms (Hu-Tucker and Garsia-Wachs) for construction of optimal alphabetic trees are presented. A generalized version of the Garsia-Wachs algorithm is given. Proof of this generalized version works in a structured and illustrative way and clarifies the usually poorly-understood behavior of both the Hu-Tucker and Garsia-Wachs algorithms. The generalized version permits any non-negative weights, as opposed to strictly positive weights required in the original Garsia-Wachs algorithm. New local structural properties of optimal alphabetic trees are given. The concept of {\em well-shaped segment\/} (a part of an optimal tree) is introduced. It is shown that some parts of the optimal tree are known in advance to be well-shaped, and this implies correctness of the algorithms rather easily. The crucial part of the correctness proof of the Garsia-Wachs algorithm, namely the {\em structural theorem}, concerning {\em well-shaped windows\/}, is identaified. The new correctness proof of the Hu-Tucker algorithm consists of showing a simple mutual simulation between this algorithm and the Garsia-Wachs algorithm. For this proof, it is essential to use the generalized version of Garsia-Wachs algorithm, in which an arbitrary locally minimal pair is processed, not necessarily the rightmost minimal pair. Such a generalized version is also needed for parallel implementations. Another result presented in this paper is the clarification of the problem of resolving ties (equalitaies between weights of items) in the Hu-Tucker algorithm. This is related to the proof, by simulation, of correctness of the Hu-Tucker algorithm. It is shown that the condition that there are no ties may generally be assumed without harm and that, essentially, the Hu-Tucker algorithm avoids ties automatically.

Last Change: 08/18/99 at 13:00:38
Universität Bonn -> Institut für Informatik -> Abteilung V

Powered by Zope