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.
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 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.