Optimal Binary Trees vs. Optimal Alphabetic Binary Search Trees

An optimal alphabetic tree built on a given initial sequence of nodes is a tree whose cost is minimum and the leaf nodes of the tree preserve the alphabetic order of the initial sequence. An optimal alphabetic binary search tree can be obtained from an existing optimal alphabetic binary tree by embedding information supporting the binary search procedure in the internal nodes of the tree. Thus, as we will see later, the cost of an optimal alphabetic binary tree and an optimal alphabetic binary search tree is the same: the level assignments of the terminal nodes is preserved, both trees obey the alphabetic order of the initial sequence, but an optimal alphabetic binary search tree has a constraint on the key values of the internal nodes according to the order of the initial sequence. A given leaf node (a letter from the alphabet) of the optimal alphabetic binary search tree can be located using a binary search procedure. The latter does not hold for optimal alphabetic tree. Algorithms for building optimal alphabetic trees can be used to build optimal alphabetic binary search trees.

Let BT denote the set of all binary trees, ABT - the set of all alphabetic binary trees, OBT - the set of all optimal binary trees, and OABT - the set of all optimal alphabetic binary trees. OABST denotes a special case of the OABT. The cost of an OBT built on a given initial sequence of nodes can be lower than the cost of an OABST built on the same sequence.

$BT \supset ABT \supset OABT$; $OABT \approx OABST$
$BT \supset OBT$

OBT consists of larger set of trees and thus achieve a better optimality than OABST. See Section 4.6 for experimental comparison of the optimality that the Huffman and the Hu-Tucker algorithms achieve.

Building an optimal binary tree on a given initial sequence is very simple. Huffman described a greedy, bottom-up algorithm, running in $O(n\lg n)$ time that builds an optimal binary tree. The algorithm is intuitive and elegant but the resulting tree can only be used in the decoding process. An additional mapping mechanism is needed to resolve the correspondence of the plaintext letter to its codeword. On the other hand optimal alphabetic binary search trees are sufficient for both the encoding and decoding process. Decoding (same for OBTs and OABSTs) is just a traversal of the tree from the root to the terminal nodes, the choice of which branch to be taken is determined by the code sequence: 0 - left branch, 1 - right branch. The encoding process, when OABST exists, is also simple - it is a binary search procedure for locating the needed letter of the alphabet.

  

Figure 1.1: Extended alphabetic binary search tree and the corresponding prefix-free binary encoding.