Implementation Model

The implementation model of the Recombination phase will use the Stack Algorithm described in Chapter 2, Section 2.2.3. The initial sequence of terminal nodes and their level assignments, calculated at the end of
phase II, will be used to construct the optimal alphabetic binary search tree.

Hu-Tucker Algorithm Phase III, Recombination
Initialize
Q[N]=T[N]
S=empty
Main Loop
while ( !((Q is empty) and $((size\_of(S))==1)) ) \mathbf{)}$
if $((size\_of(S)) \ge 2)$ and (the top 2 elements have the same levels)
then
$level_{top} = level\_of\_element (pop(S))$
Combine those two elements of the queue Q, whose levels
are at the top of the stack.
Remove the element from the top of the stack: pop(S)
Remove the element from the top of the stack: pop(S)
Push an element with level = level_top-1 on the top of the stack:
push(S, level_top-1)
else
Remove an element from the front of the queue Q
and push it on the top of the stack S: push(S, pop(Q))
End: Phase III Completed

Figures 3.5, 3.6, 3.7, and 3.8 illustrate the behavior of the algorithm with the example sequence of nodes used in Figures 3.3 and 3.4.
The time complexity of the third phase is
$T(n) = c_1nT(\mathsf{push}) + c_2nT(\mathsf{pop}) + c_3(n-1)T(\mathsf{combine}) + c_4$
The stack and queue operations take O(1) time $\Longrightarrow$
T(n) = c₁nO(1) + c₂nO(1) + c₃(n-1)O(1) + c₄
$T(n) = c_5nO(1) \leq c_6n$
T(n) = O(n)
The space complexity is:
S(n) = 3n = O(n)

  

Figure 3.5: The engine of the algorithm during the Reconstruction sequence.

  

Figure 3.6: Reconstruction phase in progress. Three elements from the queue Q are pushed on the stack S.

  

Figure 3.7: The top two elements of the stack are combined.

  

Figure 3.8: Completed Reconstruction phase.