Math 188 - Winter 2001 - Prof. Tesler
Majority Tree


Links:     Description     Animation instructions     Animation     Math 188 home

Consider a tree of depth d in which all internal nodes have three children, and all leaves are on level d. At every leaf, we assign a value 0 or 1.  At every internal node, the value 0 or 1 is computed by taking the majority of the values at its three children (if two or three children have value x, the node is assigned x too). Here is such a tree with d=2:

Picture of full tree

We want to find the value assigned to the root.  An upper bound on the number of leaves that we have to examine to compute this is 3d (that is, all of them).  However, if we are lucky, we may be able to examine fewer: if in any group of three sibling nodes, the first two examined have the same value, that value propagates up to the parent, and there is no need to look at the third node or any of its descendants; they are rendered irrelevant.

For example, in the tree shown above, if we read the leaves from left to right, skipping irrelevant ones, then we would first examine leaf [1]

Read leaf 1
and leaf [2]
Read leaf 2
In their group of siblings [1-3], they give two 0's, so there is no need to examine leaf [3]; we just propagate the value 0 up a level, and mark [3] as "irrelevant" with an "X." Then we examine leaf [4]


and leaf [5]

and still do not have a majority in the sibling group [4-6]. We read leaf [6]


and the majority value of leaves [4-6] is 0, so we set their parent to 0. This makes two of the siblings on level 1 have value 0, so the root has value 0 too; there is no need to examine the third node on level 1, or its children [7-9], so mark them irrelevant. Examining the leaves in this order required seeing the values of 5 leaves.

If instead of reading the leaves left to right, we chose the order by some other rule, and we happened to start out [1] [2] [4] [6], we would know the value of the root is 0 after examining just 4 leaves.


We can turn this into a 2-player (mathematical) game.  For each round of play,

Then play another round.  Eventually, the value of the root will be determined.

The applet below demonstrates this game.


Here are some questions about how many leaves the solver must examine. See the problem set and solutions.


Instructions

The applet below has several strategies for the two players:

The play may be step-by-step; animated; or all at once:
<|  |>    Do one step forwards or backwards.
<  ||  > Animate the steps.
<<  >> Clear the game, or jump to the end of the game.
The node values are displayed as follows:
0,1    The value assigned to the leaf, or calculated as the majority value of the children of a node.
? Not assigned a value yet.
X The value is irrelevant because an ancestor's value could already be determined without knowing this node.   The solver will not waste time choosing irrelevant leaves.
If Node View is set to Counts, then the order in which the leaves are assigned 0/1 values is indicated in parentheses after the 0 or 1; if the 10th leaf given a 0/1 value is given the value 0, it is shown as "0 (10)".  If this value is propagated up to ancestors, the order the ancestor nodes are assigned in is denoted "0 (10+1)", "0 (10+2)", etc.  Unassigned descendants of those ancestors are marked irrelevant "X", and the order is denoted in the same sequence, "X (10+3)", etc.

This generalizes to finite trees with all nodes having an odd number of children. The demonstration has all leaves at a specified depth, and has a specified downward degree (odd).

Your browser is not java enabled.
 
©2001, Glenn Tesler