Trees as Data Structures
|
Mentor: Here is one more game to play and study. Players roll 3 four-sided dice. Player 1 wins if the sum of the dice numbers is 3, 4, 5, 6 or 12; Player 2 wins if the sum is 7, 8, 9, 10 or 11. Is the game fair? Student: Now I know that there are many possible ways to get the same sum. We used tables to count the possibilities for two dice. We can't use the table anymore, because it only has two... what do you call them? Mentor: Dimensions. We can make a table with three dimensions or more, but it will be hard to use by hand. By the way, computers can deal with tables of hundreds of dimensions. What else can we do? Let me write the first quarter of the list of all the combinations, the part where the first die shows 1. It will be a boring task....
Student: Could we somehow get rid of all the repetitions? I mean, can we write one big fat "1" instead of sixteen little 1's? Mentor: Why not? If we do that, we will obtain a structure called a tree. Can you guess why even before we make the pictures? Here is the picture that shows how this part of the tree for our problem is constructed. There will be 3 more parts for the rest of the possible numbers on the first die. You can build them yourself. 
Mentor: Do you see why it is called a tree? Student: Because it looks like a tree lying on its side. We can add some "leaves" and write stuff on them. I will write the sum of the dice numbers:
Mentor: Do you see how the tree can help us count outcomes? Student: Well, it is useful for counting the total number of outcomes. There are four "trunks" (for the possible numbers on the first die), and each has four "branches" (for the possible numbers on the second die), and each has four "twigs" (for the possible numbers on the third die). An outcome is formed as we go from a trunk to a brunch to a twig. There are as many outcomes as there are twigs: 4*4*4=64. Wow! It sounds like an old puzzle! Mentor: Now look at all the "leaves" and find out if the game is fair. What is the probability of each player winning? Student: Player 1 only has a winning probability of 21/64, whereas Player 2 has a winning probability of 43/64. This game is not fair. Mentor: How many possible outcomes are there if you have three coins? (2*2*2=8) If you have a coin and two six-sided dice? (2*6*6=72) How many outcomes are there if you have four coins?(2*2*2*2=16) Five six-sided dice(6*6*6*6*6)? By the way, if I do not feel like writing the numbers so many times, can I write the same thing much shorter: 6*6*6*6*6=6 5 It reads: "Six to the power of five." Computer folks type it as 6^5, because it is faster than switching to the superscript. Student: I do not want to actually draw all these huge trees! Mentor: A tree for the four coin problem would not be all that bad. Can you draw it? Observe that at each time the tree "branches," there are exactly two branches (for heads and tails on the next coin). Trees of that sort are called binary trees. They are very common in computational science, and even in nature: 
Mentor: Here is a riddle for you. If we have a full binary tree (no branches are cut off) that has 8 smallest branches, how many "levels of branching in two" are there? In other words, if we were playing with coins, how many coins would you need to produce 8 outcomes? Student: Let us see. The last branching happens when 4 branches became 8: 
Student: In the original example with 3 four-sided dice, there were 64 "smallest branches," but each branching was splitting in four. That means: log4 64=3 Mentor: Exactly, and 4^3=64. By the way, where else have you seen trees like that? Student: In NCAA tournaments! Mentor: Now you can easily translate the following question into mathematical language: "If there are 64 teams in a tournament, how many rounds do they need to play to determine a winner?" Student 1: The question is so much shorter in math language! log2 64=? Student 2: The answer is 6. |
