|
Due
Sunday 11:59 PM, April 16 2001
In this lab we will explore using binary trees and a their
algorithms. To do so, we will set up a "tournament" tree that
will simulate a sports playoff tournament. This will
involve creating classes that represent teams, and the associated
algorithms to insert the teams into the tournament tree and to play one
"round" of the playoffs, advancing the winning team to the next
level.
This lab will involve some tricky and involved
algorithms, so proceed slowly, methodically and
carefully. The first thing you want to do is to review
the documentation for BRStructure package.
The Structure
The Classes
The main classes involved here are
- ATeam -- an abstract team. Has a
name that is given when toString() is called. Has a Visitor
design pattern execute() method.
- Team -- has a user definable name. Represents an actual team.
- NullTeam -- has
a fixed name of "???". Represents a lack of a team or a
spot in the tournament tree where a winning team hasn't yet been decided.
- ITeamAlgo -- The Visitor design pattern
algorithm that an ATeam can execute. It has a method for each
concrete sub-class.
- InsertTeamAlgo -- the algorithm to insert
a team into a BRStruct
- PlayRoundAlgo -- the algorithm to play one round of the tournament.
- BRStructure
package -- defines the classes for a binary tree.
- BRStruct -- a State+Visitor design pattern binary tree.
- IBRSAlgo -- the Visitor design pattern
algorithms that the BRStruct
can execute.
- Graphics classes -- needed to display the
BRStruct on a JPanel.
- BRSDisplayAdapter -- An MVC adapter
that will connect a BRStruct to a JPanel view.
- BRSGetMaxDepthVisitor
-- Used by
BRSDisplayAdapter to find the depth of the tree.
- BRSShowVisitor -- A simple
non-recursive BRStruct visitor that enables
the displaying of a tree to be treated as an external algorithm on the
tree.
Inserting Teams
Fundamentally the idea here is to insert Team objects into a binary tree (BRStruct). The Team objects should end
up in "leaf" nodes in the tree. That is, the nodes they are in
always have null trees as the sub-trees. A Team's "opponent" is the team held as the root data
of the team's sibling tree. The interior (non-null,
non-leaf) nodes should contain NullTeams. Note that this does not
preclude Teams from having "bye's". In fact,
this capability will insure that a Team
never has a null tree as an opponent.
Thus if a Team is inserted
into a null tree, the Team will be attached
as the root data right there. But when the tree being inserted
into is non-null, thre are two possibilities.
- The data held is a NullTeam: Just randomly pick one
side (left or right) and recursively add the new Team
to that side. See the "?" operator
discussion below
for a nice easy way of doing this.
- The data held is a Team
: Insert the existing Team to
the left side, insert the new Team on the right
side and replace the data at this node with a NullTeam
.
To accomplish this, simply execute an ITeamAlgo on the ATeam held at
the node. Using this anonymous inner class will
polymorphically distinguish between the two cases above. Pass the
new Team in as the param, so be sure to make it
final so that the inner class can access it (or pass
it as the param of the inner ITeamAlgos too -- no
need for final
then -- why?).
Playing Teams
When a "round" of the tournament is
"played", a Team plays it's opponent in its
sibling sub-tree. The "winner" then replaces the NullTeam in the parent tree's root. If
a Team's opponent is a NullTeam(i.e. it had a bye), then it must wait for the
lower level Teams to play
first. Another way to think about it is to say that, in the
case of a bye, the winner is always NullTeam
.
Thus, unless the root data of a tree is a Team, the algorithm must check the left and right
sub-trees to determine how to play the round at this
level. Plus, playing a round at this level might entail
recursively playing rounds at the lower levels of the
tree. For a more detailed description of the
process flow for the algorithm, see the sub-section to the left.
The Order
- While in lab, go
over the InsertTeamAlgo and PlayRoundAlgo classes and understand how
they work.
- Download the BRStructure
and BRSVisitor packages from the CS151 FTP site.
- Create the Team classes (see the docs to
the left).
- Get a test frame up and running (suggestion:
display your tree on a JPanel in a ScrollPane).
Put NullTeams and Teams into the tree by hand and make sure that
the tree displays properly.
Note: After running BRSDisplayAdapter.showTree(), be sure to validate and repaint the ScrollPane
if you are using one.
- Write the InsertTeamAlgo and get it
working.
- Finally, attempt to write the much more difficult
PlayRoundAlgo.
The ? Operator
Java's "?" operator is like an if statement that returns gives you
choices of values rather than code blocks. The basic syntax
is:
[conditional statement] ? [value1] : [value2]
If the conditional statement evaluates to true, then the entire
statement evaluates to
value1. If the conditional statement evaluates to false, then the entire statement evaluates
to value2. Note: value1 and value2 must have the same
type.
Examples:
x = ( a< b) ? y : z; // x = y if
a<b, otherwise x = z
// Obj1 & Obj2 are of the same type and have a doIt()
method:
((Math.random()<0.5) ? Obj1 : Obj2 ).doIt(); //
randomly executes the doIt() method on either Obj1 or
Obj2.
|