CSC 216/s08/be gentle

Binary Speed Tree

What is a binary search tree?

A binary search tree is a data structure that can be arranged so that the data it contains can be added and deleted easily. It has the following properties:

---each node (item in the tree) has a value

---a total order (linear order) is defined on these values

---the left subtree of a node contains only values less than the node's value

---the right subtree of a node contains only values greater than or equal to the node's value

The problem

The concept of binary search trees in Java is one that can be difficult to grasp. The goal of this exercise is to help students visualize how a binary search tree is created. It does this by actively involving them in sorting their own search tree using a deck of cards. By seeing how a random set of numbers are placed into a tree, students will better understand how binary search trees are sorted and be given a visual example of the efficiency of these trees.

Participants and props

The only prop required for this exercise will be a single deck of cards. The participants will be four teams of about five students each.

The script

1. The deck of cards will be split into the four different suits (hearts, spades, clubs, diamonds) and the face cards, as well as the aces will be removed from the deck. The participants will be divided into four teams, one for each suit.

2. Each member of the group will receive one card from their pile face down, so they cannot see the value of the card.

3. Each team will select a team leader who will show their card. This card will represent the first card in the binary search tree, and the leader will stand at the top of the list.

4.The professor will say "go," and the other members of each group will flip over their card. The group will then decided the best way to organize themselves in a correct binary search tree by standing in the correct corresponding position to the preceding cards.

5. Once they believe they have the tree sorted correctly, the leader yells "finished," and the professor will check to make sure the group has sorted themselves correctly. The first group to finish and be checked for correctness wins the game.

Also provided is a video that demonstrates the format of this exercise.