Data Structures, Algorithms, & Applications in Java
Chapter 14, Exercise 9

(a)

The size of the array tree[] is m where m is the smallest integer >= n that is a power of 2. It may be shown that n <= m < 2n - 1. Therefore, the additional space is for at most n - 1 positions of tree.

(b)

The new implementation is given below. The data member offset equals m-1. Since the players and internal nodes are in different arrays, it is still necessary to play lowest-level matches separately from the remaining matches.

---

public class FullWinnerTree implements WinnerTree
{
   // data members
   int offset;           // 2^ceil(log n) - 1
   int [] tree;          // array for winner tree
   Playable [] player;   // array of players

   // only default constructor available

   /** @return the winner of the tournament
     * @return 0 if there are no players */
   public int getWinner()
      {return (tree == null) ? 0 : tree[1];}

   /** initialize winner tree for thePlayer[1:thePlayer.length-1] */
   public void initialize(Playable [] thePlayer)
   {
      int n = thePlayer.length - 1;
      if (n < 2)
         throw new IllegalArgumentException
                   ("must have at least 2 players");

      // compute  smallest m >= n and a power of 2
      int m;
      for (m = 1; m < n; m += m);
   
      // set instance data members
      player = thePlayer;
      tree = new int [m];
      offset = m - 1;
   
      int p = (n + offset) / 2;  // tree[p] is largest p where a match is played

      // play match at tree[p]
      if (n % 2 == 1)
         // n is odd, tree[p] has only one child
          tree[p] = n;
      else
         // n is even, tree[p] has two children
         tree[p] = player[n - 1].winnerOf(player[n]) ? n - 1 : n;

      // play remaining matches at lowest level
      int lp = 1;  // player[lp] is left child player
      for (int i = m / 2; i < p; i++)
      {
         tree[i] = player[lp].winnerOf(player[lp + 1]) ? lp : lp + 1;
         lp += 2;
      }

      // play matches at remaining levels
      for (int i = p / 2; i >= 1; i--)
      {
          int lc = 2 * i;  // index of left child of node i
          if (tree[lc + 1] == 0)
             // no right child
             tree[i] = tree[lc];
          else
             tree[i] = player[tree[lc]].winnerOf(player[tree[lc + 1]]) ?
                                        tree[lc] : tree[lc + 1];
      }
   }
   
   
   /** replay matches for player i */
   public void rePlay(int i)
   {
      int n = player.length - 1;  // number of players
      if (i <= 0 || i > n)
         throw new IllegalArgumentException("No player " + i);
   
      // play first match
      int p = (i + offset) / 2;  // node for first match
      if (2 * p + 1 > n)
         // only player for this match
         tree[p] = i;
      else
      {// two players
         int lp = 2 * p - offset;   // left player
         tree[p] = player[lp].winnerOf(player[lp + 1]) ? lp : lp + 1;
      }

      // play remaining matches
      p /= 2;  // move to parent
      for (; p >= 1; p /= 2)
         if (tree[2 * p + 1] == 0)
            // only one player
            tree[p] = tree[2 * p];
         else
            // two players
            tree[p] = player[tree[2 * p]].winnerOf(
                      player[tree[2 * p + 1]]) ? tree[2 * p] : tree[2 * p + 1];
   }
}

(c)

A test program, input and output appear in the files FullWinnerTree.*.

(d)

Although the asymptotic complexity of both implementations is the same, we expect the implementation of this exercise to take more time than taken by the implementation of the text because most of the matches played in the implementation of this exercise require us to determine whether or not we have a right child player. Such a determination is not done in the implementation of the text.