Implementation Model of Combination Phase With Local Minimum Compatible Pairs.

As I mentioned earlier in Chapter 2, Section 2.2.1, an alternate way for building the optimal tree in Phase I is by combining local minimum compatible pairs. This section will present the algorithm for finding l.c.m.p. and building the optimal binary tree, whose leaf levels can be realized by an OABT. The implementation model is simple. We need to represent the initial sequence of terminal nodes and the constantly changing working sequence of nodes. The abstraction representing the initial sequence is the array T[N], having simpler responsibility then the one described in Section 3.1.1. Each element of the array needs to keep the following information about the node: position in the sequence, type of the node which can be internal or terminal, weight, letter of the alphabet, left and right tree descendants. The node descendants of terminal nodes are null. The abstraction representing the working sequence of nodes at any stage of the algorithm during Phase I can be an array or doubly linked list.

The algorithm simply searches for l.m.c.p. in the working sequence, scanning it from left to right, finds it and combines it. This process is repeated N-1 times. At the end only one node remains in the working sequence. The algorithm inspects the working sequence one Huffman Sequence at a time. The two nodes with minimum weight are located. They form a true l.m.c.p. if the right node of the pair is internal. If the right node of the potential l.m.c.p. is a terminal node, the weights of all the nodes compatible with it have to be compared to the weight of the left node of the potential l.m.c.p. by inspecting the right adjacent Huffman sequence. If the potential l.m.c.p. is a false l.m.c.p. then the search for l.m.c.p.resumes from the next Huffman sequence. The pseudo code of the algorithm is available in Appendix A, Section A.2.

The running time of this phase depends on the time units, T_lmcp, needed to locate a local minimum compatible pair. In the worse case scenario this will require a traversal of the entire working sequence, hence the number of comparisons that have to be performed to locate an l.m.c.p. is O(n).
$T_{lmcp} \leq$ n
T(n)_MainLoop = (n-1)T_lmcp
$T(n)_{Combination\_with\_lmcp} \leq$ (n-1)n = O(n²)