To implement the given initialization strategy,
we first create a winner tree and then
examine the nodes tree[1:n-1] resetting
each
tree[i] to the loser of the match played
at this node. To determine the loser of the match played at
tree[i],
we must first determine
the two players who palyed here. These two players can be determined
by accessing the two children of
tree[i]. Note that one or both of these children
may be external nodes. If a child is an internal node, then
the winner recorded at the internal node is a player; otherwise
the external node is a player.
We can tentatively compute the child index c as either
2 * i or
2 * i + 1 depending on whether we
are looking for the left or the right child of
i.
To determine q such that
player[q] is either the winner of the
match played at tree[c] or is the external node
at this child of
tree[i] we must invert Equation 13.1, which
currently tells us how to go from an external node to its parent.
Doing this inversion yields the following code:
if (c <= n - 1)
q = tree[c];
else
// child is an external node
if (c <= offset)
q = c + lowExt - n + 1;
else
q = c - offset;
Once we have identified the two players of the match at
tree[i], we can determine the
loser by comparing with the known winner of the match
played at this node.
The code to replay a match when the winner has changed
is simpler than the corresponding code for a winner tree.