Next: Building OABST using the Up: Hu-Tucker Algorithm, Phase I, Previous: Fast Implementation

# Implementation with Local Minimum Compatible Pairs

Initialization
for ( ++ )
Initialize T[k]

End:Initialization

Main Loop
for ( ++)
Initialize the search for l.m.c.p from the beginning of the
working sequence.
while
(1)
# This loop looks for l
.m.c.p. When it finds it combines the nodes
# in the pair and exits the while loop.
Locate the two nodes with least weight in the current
Huffman Sequence.
Let the A[i] and A[j] point to the element with the smallest and next
to smallest weights respectively within the current
Huffman Sequence.
if( both A[i] and A[j] point to internal nodes )
then
#This is a Combine the two nodes:

1. Create a new node I
I.position = min(i,j)
I.type = INTERNAL
(weights of the nodes pointed by A[i] and A[j])
I's left and right tree pointers = A[i] and A[j]
2. Update the array A[N]:
if (i<j)
then

A[j]=null
else

A[i]=null

break
else
#One of the nodes is a terminal node
if (the right node is a terminal node)
then
node from the right adjacent Huffman Sequence with
smaller weight than the left node of the pair )
then
Resume the search for l
.m.c.p. from the current
Huffman Sequence
continue
else
# l
.m.c.p is found

break
else
# l
.m.c.p. is found

break
End: while
End: Main Loop
End: Phase I Completed

Next: Building OABST using the Up: Hu-Tucker Algorithm, Phase I, Previous: Fast Implementation
Sashka Davis;961;icsg6;
1999-01-14