Phase III, Recombination

This phase builds an optimal alphabetic tree from the initial sequence of terminal nodes and their levels calculated in Phase I. Pair of adjacent nodes which are at the same maximum level are combined to produce a node at level l-1.

Level by level construction of the tree is achieved by combining nodes q_i and q_i+1 following the rules:

(i) q_i and q_i+1 must be adjacent nodes in the sequence.

(ii) The levels of q_i and q_i+1 must be the maximum among all the levels of the remaining nodes.

(iii) If q_i and q_i+1 are at level l then q_i must be the leftmost node satisfying (i) and (ii). Nodes at the lowest level are combined first, then the nodes on the next-to-lowest level are combined, etc. The process continues until there is only one node left and its level must be 0.

  

Figure 2.4: Level by level construction of alphabetic tree.

Note that the cost of the resulting tree is the same as the cost of the tree obtained at the end of the Combination phase. The tree constructed is alphabetic and optimal. The integers in the parenthesis above the circular nodes indicate the number of the iteration of the Reconstruction phase at which the node was created. Thus, circular node with weight 2 is constructed at the first step, circular node with weight 4 - at the second, circular node with weight 3 at the third, etc.

The Stack algorithm, described by T. C. Hu in [Hu82] can also be used to reconstruct the optimal alphabetic binary tree. This algorithm resembles the construction of the tree in the Phase I of the algorithm by combining local minimum compatible pairs as they are discovered. In the same fashion leftmost pairs of adjacent nodes with equal level are combined to form a node of higher level (the root of the tree has the highest level) as follows.

The algorithm uses a queue and a stack. Initially all the nodes with their levels are in the queue and the stack is empty. In subsequent steps the algorithm performs a check to see if the two elements at the top of the stack have equal levels. If they are equal then the two nodes are popped from the stack and combined to form a new node with a higher^2.4 level. For example, if the top of the stack has elements with levels (l+1), (l+1), after the combination, the top of the stack will have an element l. If the two elements on the top of the stack are not equal then the element from the head of the queue is extracted and pushed onto the stack. This process continues until the queue is empty and the stack contains only one element with level 0.

Here is an example of the Stack algorithm applied on the sequence of nodes from Figure 2.3.

1.

Queue content: 3,3,2,4,5,5,4,4,3,3
Stack content: empty

2.

Queue content: 3,2,4,5,5,4,4,3,3
Stack content: 3

3.

Queue content: 2,4,5,5,4,4,3,3
Stack content: 3,3

4.

Queue content: 2,4,5,5,4,4,3,3
Stack content: 2

5.

Queue content: 4,5,5,4,4,3,3
Stack content: 2,2

6.

Queue content: 4,5,5,4,4,3,3
Stack content: 1

7.

Queue content: 5,5,4,4,3,3
Stack content: 1,4

8.

Queue content: 5,4,4,3,3
Stack content: 1,4,5

9.

Queue content: 4,4,3,3
Stack content: 1,4,5,5

10.

Queue content: 4,4,3,3
Stack content: 1,4,4

11.

Queue content: 4,4,3,3
Stack content: 1,3

12.

Queue content: 4,3,3
Stack content: 1,3,4

13.

Queue content: 3,3
Stack content: 1,3,4,4

14.

Queue content: 3,3
Stack content: 1,3,3

15.

Queue content: 3,3
Stack content: 1,2

16.

Queue content: 3
Stack content: 1,2,3

17.

Queue content: empty
Stack content: 1,2,3,3

18.

Queue content: empty
Stack content: 1,2,2

19.

Queue content: empty
Stack content: 1,1

20.

Queue content: empty
Stack content: 0

21.

END.

  

Figure 2.5: Reconstruction phase, using the Stack Algorithm.

Note that the internal nodes are created in different order in comparison with the level by level construction. For example, the internal node with weight 14 is created at the seventh stage in the first case and during the second stage in the Stack algorithm. The result tree produced using the Stack algorithm is the same as the one constructed by combining the leftmost adjacent pairs at the lowest level first. The two algorithms achieve different time complexities. The Stack algorithm can be implemented in O(n) time while the level by level reconstruction in $O(n\lg n)$ time.

 

Footnotes

... higher^2.4

Higher level is closer to the root of the tree, which is at the highest level, and also has a lowest level value.