Data Structures, Algorithms, & Applications in Java
Chapter 10, Exercise 10

(a)

The data members of the new class are the same as those for the class CompleteWinnerTree of the text. To initialize a winner tree, we first set tree[i] for the nodes that lie between the players and the match nodes. Next, we play the matches at tree[i] for i = n-1, n-2, ..., 1, in that order.

To replay matches when player[i] changes, we play matches on the path from the grandparent of this player to the root of the winner tree.

The code for the new implementation is given below.

---

public class CompleteWinnerTree3 implements WinnerTree
{
   // data members
   int lowExt;           // lowest-level external nodes
   int offset;           // 2^log(n-1) - 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");

      player = thePlayer;
      tree = new int [2 * n];
   
      // compute  s = 2^log (n-1)
      int s;
      for (s = 1; 2 * s <= n - 1; s += s);
   
      lowExt = 2 * (n - s);
      offset = 2 * s - 1;
   
      // initialize nodes that lie between players and match nodes
      for (int i = 1; i <= lowExt; i ++)
         tree[i + offset] = i;
      for (int i = lowExt + 1; i <= n; i++)
         tree[i - lowExt + n - 1] = i;

      // play matches
      for (int i = n - 1; i >= 1; i--)
         tree[i] = player[tree[2 * i]].winnerOf(player[tree[2 * i + 1]]) ?
                          tree[2 * i] : tree[2 * i + 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);
   
      // set p to be first match node
      int p;
      if (i <= lowExt)
         p = (i + offset) / 2;
      else
         p = (i - lowExt + n - 1) / 2;

      // play matches from p to root
      for (; p >= 1; p /= 2)
         tree[p] = player[tree[2 * p]].winnerOf(
             player[tree[2 * p + 1]]) ? tree[2 * p] : tree[2 * p + 1];
   }
}

(b)

A test program and sample input and output are given in the files CompleteWinnerTree3.*

(c)

Even though the code for the new implementation is considerably simpler than that for the implementation of the text, we do not expect any noticable difference in run time. This is because the loops that perform the bulk of the work remain unchanged. Therefore, the new implementation takes twice the space but yields little or no run time reduction. The tradeoff here is between a simple implementation and a more complex implementation that takes half as much data space. Since we implement the class only once and use it many times over many applications, it is preferable to put in the extra effort in developing the implementation that uses less space.

Of course, if we are dealing only with a small number of small trees, then the extra space needed by the code of the text will exceed the extra space needed for the trees when the implementation of this exercise is used. Our recommendation in favor of the space saving implementation is based on the assumption that we want to support the largest size trees possible with little or no loss in run time performance.