
Universität Bonn > Institut für Informatik > Abteilung V  
CSReports 1995  Copyright 1995 Universität Bonn, Institut für Informatik, Abt. V  
85134

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 (HuTucker and GarsiaWachs) for construction of optimal alphabetic trees are presented. A generalized version of the GarsiaWachs algorithm is given. Proof of this generalized version works in a structured and illustrative way and clarifies the usually poorlyunderstood behavior of both the HuTucker and GarsiaWachs algorithms. The generalized version permits any nonnegative weights, as opposed to strictly positive weights required in the original GarsiaWachs algorithm. New local structural properties of optimal alphabetic trees are given. The concept of {\em wellshaped 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 wellshaped, and this implies correctness of the algorithms rather easily. The crucial part of the correctness proof of the GarsiaWachs algorithm, namely the {\em structural theorem}, concerning {\em wellshaped windows\/}, is identaified. The new correctness proof of the HuTucker algorithm consists of showing a simple mutual simulation between this algorithm and the GarsiaWachs algorithm. For this proof, it is essential to use the generalized version of GarsiaWachs 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 HuTucker algorithm. This is related to the proof, by simulation, of correctness of the HuTucker algorithm. It is shown that the condition that there are no ties may generally be assumed without harm and that, essentially, the HuTucker algorithm avoids ties automatically. 

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