Optimum alphabetic binary trees

Bonn Univ. (Germany). Inst. fuer Oekonometrie und Operations Research)
Morgenthaler, J.D. (California Univ., San Diego, La Jolla, CA (United States). Dept. of Electrical Engineering and Computer Sciences)
Hu, T.C. (Bonn Univ. (Germany). Forschungsinstitut fuer Diskrete Mathematik
Bonn Univ. (Germany). Sonderforschungsbereich 303 - Information und die Koordination Wirtschaftlicher Aktivitaeten

Publication date

January 1995

Abstract

We describe a modification of the Hu-Tucker algorithm for constructing an optimal alphabetic tree that runs in O(n) time for several classes of inputs. These classes can be described in simple terms and can be detected in linear time. We also give simple conditions and a linear algorithm for determining if two adjacent nodes will be combined in the optimal alphabetic tree. (orig.)SIGLEAvailable from TIB Hannover: RN 4052(95850) / FIZ - Fachinformationszzentrum Karlsruhe / TIB - Technische InformationsbibliothekDEGerman

Extracted data

We use cookies to provide a better user experience.

Data Protection

Optimum alphabetic binary trees

Abstract

Extracted data

Optimum alphabetic binary trees

Abstract

Extracted data

Related items

Related items