Next: Time and Space Complexity Up: Phase III Previous: Phase III

## 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
if and (the top 2 elements have the same levels)
then

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 = leveltop-1 on the top of the stack:
push(S, leveltop-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

The stack and queue operations take O(1) time
T(n) = c1nO(1) + c2nO(1) + c3(n-1)O(1) + c4

T(n) = O(n)
The space complexity is:
S(n) = 3n = O(n)

Next: Time and Space Complexity Up: Phase III Previous: Phase III
Sashka Davis;961;icsg6;
1999-01-14