Last update: April 3, 1999

Explore the following idea: construct a tournament tree by mimicking a tennis tournament. The largest element (best tennis player) ends up at the top. Can you translate this into a data structure, and can you insure that insert and deletemin can be carried out in O(log n) worst-case time? Do not assume that n is a power of 2. Illustrate your work with one or more drawings.

A tennis tournament is formed in the following way:
1. Competitors are randomly chosen and paired off. If there are not enough players to make a power of 2, "byes" are also entered into the draw (random space) until there are. These "byes" or empty spots, may be paired up with players, thus giving these lucky players the first round off, and an automatic advancement to the second round.
2. Once all players are paired off, these pairs form the first round. The first round plays, and the winners advance to the next round. The losers drop out.
3. The winners of the first round are then paired off and form the second round. They play. The winner advances. The loser drops out.
4. This repeats, with the winners of the last round pairing off and forming the next round, until there is only the tournament winner remaining.

Here is an example of the basic tennis tournament with 12 players:

Now what makes tennis really interesting is the concept of seeding. Since the first round is chosen by random, it is possible for the two best players to play each other in the first round, thus knocking one out right away. This is fustrating for the loser, as he or she does not get to play the rest of the tournament, and it tends to make the tournament a bit anti-climatic as the remaining player is now the best player in the tournament, and proceeds to clean house for the remainder of the tournament.

To prevent this, seeding was introduced. The top players, usually the top 4 to 16 depending on the number of competitors, are placed in specific positions in the first round. The top two players are put as far away from each other as possible, i.e. the edge of the tree. What this accomplishes is to make it so that the only place that the top two players will possibly meet, is in the finals.

One final little detail. Byes are usually given to the top seeded competitors. This is to give them a break as they will be playing much more difficult games against the better competitors. Why waste energy on the little people since the outcome is known.

Here is an example of a seeded tournament with 12 competitors:
The seeded player are in red.

So how does one turn a tennis tournament into a data structure? And what will it buy us?

We can turn a tennis tournament into a data structure called (surprise, surprise!) a tournament tree. You build a tournament tree in a way similar to how you build a tennis tournament. Take all the elements that you have and put them on the bottom of the tree. Pair up the elements. For each pair, choose a winner and make the winner the parent of pair. This creates a second layer of element, for which you repeat the process. Keep repeating until you have a complete binary tree.

Of course this is only really useful if you have a systematic way of choosing the winner. By having each node have a key, you can create a minimum tournament tree, or a maximum tournament tree, by choosing the respective element of each pair as the winner.

Now you may have problems if you do not have 2^N nodes for some integer N. You cannot make a complete binary tree without 2^N nodes at the lowest level. So we will solve the problem in the same way as with a tennis tournament. We fill up the rest of the space with blanks. The blanks will always lose when they come up against a real node. So for a minimum tournament tree, the blanks would be infinity, and for the maximum tournament tree, the blanks would be negative infinity.

Here is an example of a minimum tournament tree:

Notice that nodes are repeated.

Tournament trees have the following operations on them:

• MAKETREE(S) S a set of elements
  1. if (number of elements in S) not equal a power of 2
  2. then for i <-- 1 to [(closest power of 2) - (number of elements in S)]
  3. do add infinity node to S end for
  4. end if
  5. make a new empty set Q
  6. for i <-- 1 to [(number of element in S) / 2]
  7. do
  8. remove two elements from S, call them A and B
  9. compare two elements and choose smallest, call it C
  10. LEFT[C] <-- A
  11. RIGHT[C] <-- B
  12. PARENT[A] <-- C, PARENT[B] <-- C
  13. put C in set Q
  14. end for
  15. if (sizeof[Q] > 1)
  16. then MAKETREE(Q)
  17. else return the single element of Q as the root of the tree.

This takes O(n) comparisons

• REPLAY(N) - Given a node N, replay it's comparisons and alter tree
  1. A <-- PARENT(N)
  2. B <-- LEFT(A)
  3. C <-- RIGHT(A)
  4. if B < C
  5. then do NEWPARENT <-- B
  6. else NEWPARENT <-- C end if
  7. RIGHT[NEWPARENT] <-- C, LEFT[NEWPARENT] <-- B
  8. PARENT[C] <-- NEWPARENT, PARENT[B] <-- NEWPARENT
  9. PARENT[NEWPARENT] <-- PARENT[A]
  10. if NEWPARENT is not root
  11. then REPLAY(NEWPARENT)
  12. else return NEWPARENT as root of altered tree

This takes O(lg n) comparisons.

An example of REPLAY

• DELETEMIN(T)
  1. if ISLEAF[T]
  2. then do T <-- infinity node
  3. REPLAY(T) end do
  4. else if LEFT[T] = T
  5. then DELETEMIN(LEFT[T])
  6. else DELETEMIN(RIGHT[T])

This takes O(lg n) comparisons for the REPLAY. Finding the path is trivial.

An example of DELETEMIN

These are the basic operations on tournament trees. However, one can make a priority queue by adding an operaiton INSERT. This however is a bit more difficult.

• INSERT

  The idea behind INSERT is to put in the inserted element in a empty position, i.e. an infinity node, at the leaf level. Then replay the tree. However, finding an infinity node is a bit more difficult as there is no search algorithm.

  What I think is the best way to implement this is store all the nodes in a 2^N array. This way, if you keep all the infinity nodes at one end and keep track of how many you have, you can easily change one of the infinity nodes into the inserted item. The tournament tree is then a exogenous structure pointing to the elements in the array.

  There is a problem when you insert an element that makes the number of elements go from 2^N - 1 to 2^N. Inserting an element when the power of two does not change takes O(lg n) time due to the REPLAY. However, when the bottom layer of the complete tree is full, and you add another element, you have to rebuilt the tournament tree with the bottom layer of the next power of 2 elements to accomidate the new element. In an endogeneous structure, this would take O(n) time, as you would have to tear down the tree, by deleting repeatedly. This takes O(n lg n) time. Then you have to rebuild the tree, which takes O(n) time.

  This is when the exogenous structure is useful. To insert the crucial element, you just make a new array of 2^(N-1) elements. (The array is the same size as the old array). Put the new element in the array. Make a new tournament tree with only that one element, and the rest blanks. This takes at most O(n) but can probably be done much faster since most of the elements are blanks. Then take the roots of the new tree and the old tree, compare them, take the smallest and make a root node for the new 2^N tournament tree. This takes at most O(n) time since you only have to build the new tree. I think it can be done much faster since building a tree with one element is trivial. The old tree remains intact.

An example of insert over the 2^N barrier

With DELETEMIN, sorting is again trivial. Just run repeated DELETEMINs until all the elements are gone. The order that the elements come out in is the sorted order. This takes O(N lg N) comparisons.

So how can you further mimick a tennis tournament with tournament trees? Well, there really is only one thing left, and that is seeding.

To seed, you just place the top(smallest) elements at specific positions in the bottom of the tree. This again is made much easier with an exogenous data structure. Actually, seeding does very little for our data structure as there is not way for the second smallest element to lose to anyone except the smallest element.

That's it. Tournament trees are a data structure that arise from a real life object. They can be used to implement the priority queue ADT. They also show how exogenous and endogenous data sturctures can have an effect on running time.

Information on tournament trees on the web were quite scarce. Heck, information on how to build a tennis tournament was quite scarce to non-existant on the web. Here are the few web sites that I found.

Sorting algorithms	There is Tournament Sort towards the bottom
Course notes from CS251 1997 on Priority Queues	Explains the tournament tree quite well.
rec.sports.tennis FAQ miscellaneous	Section 6.7 is about professional tournament seeding.

Searching for algorithms in books is a bit difficult and time consuming. I didn't find any books with tournament trees in them. I did need the following books to fill in some of the gaps in my knowledge, like not knowing a thing about tennis tournaments

1. McEnroe, Patrick, et al. Tennis for Dummies. IDG Books Worldwide, 1998.
   Explains enough about tennis so you can play it and watch it.
2. Cormen, Thomas H., Charles E. Leiserson, and Ronald L. Rivest. Introduction to Algorithms. The MIT Press, 1989.
   For information on priority queues.

This web page was created by Marshal Wong ([email protected]).