Foreword
This document is the user guide for a data structure algorithm animation
tool I wrote for an independent study project. The program is named DSCATS
(Data Structures -- Computer Animation Tools) pronounced Dis Cats. This
program was written during the months of July and August in 2001. The
following documentation is accurate for DSCATS Version 2.0. This program has
been "common sense" tested. Most common sense errors have been caught and
display error messages. I'm sure there are more errors, which means you
almost certainly can cause all sorts of problems by doing things that are
obviously incorrect. I guess the bottom line is either use common sense or
else buyer (or student) beware.
Justin Cappos (justincappos@hotmail.com)
Table of Contents
I. Introduction
II. Interface
A. Menu Bar
B. Movie Buttons
C. Datafiles
III. Data Structures
A. Binary Tree
B. AVL Tree
C. B-Tree
IV. Intended Additions
V. Conclusion
I. Introduction
This program is intended for use by students to learn the fundamentals of
data structures. The interface is meant to be easy to use, but not "idiot
proof". Please use common sense when using the program. As of this
version the Binary Tree, AVL Tree and B-Tree data structures have been
implemented. If you are interested in implementing another data structure then
please read the DSCATS PROGRAMMER MANUAL (the code has been written is such a way
where this should be fairly easy to do).
II. Interface
The interface is broken down into two major components: the menubar (at the
top of the screen) and the Movie Buttons portion (with the VCR like buttons).
The top portion deals mostly with settings while the bottom portion buttons
perform movie actions.
A. Menu Bar
The menu bar on the top of the screen is the way to change the options for
this tool.
File Menu:
Open -- This opens a Datafile. The default is "TestData.dsdata". Once
you have selected the Datafile you wish to use, click on the
START button to load the commands from that Datafile.
(See also the portion on Datafiles)
Save -- This saves the current commands and settings into a Datafile.
The default is "TestData.dsdata" (See also the portion on
Datafiles)
Exit -- Ends the program
Options Menu:
Speed -- This controls the number of milliseconds to pause on each frame
when using the Play function. Default: 2000 (2 seconds)
Detail Level -- This controls what detail you wish to see (between 1 and
10). Level 10 commands cannot be ignored. The level of
each frame is data structure specific. The ## (displayed
comment) and PAUSE commands in a data file are both level
10 commands (and therefore the frames cannot be ignored).
See the specific data structure for information on which
frames are at which detail level. You will only see the
frames of the movie at the current detail level or higher.
Default: 5
Change Data Structure -- This changes the current data structure to the
data structure you wish to use.
Default: Binary Tree
Data Structure Settings -- This is data structure specific... See the
specific data structure for more information
Help:
General Help -- This asks you to read this file for more information
Data Structure Help -- This is help about the data structure you are
currently using.
About -- This tells the version number and last modification date
B. Movie Buttons
This section only deals with the VCR like buttons on the bottom of the
screen. For help about the other buttons (Insert, etc.) consult the
specific data structure.
Rewind -- This moves the "data structure movie" back one frame
Play -- This begins moving forward frames at the speed set in the Speed Menu
Item (see Speed above)
Pause -- This stops the movie from playing (as everything but play does also)
Stop -- This resets the movie to the first frame and stops playing.
Fast Forward -- This moves the movie forward one frame
Movie bar -- You can click on any section on the movie bar and jump to that
frame of the movie. The current frame is displayed in white.
All frames that have yet to be displayed (future of the movie)
are in black. The previous frames "age" in color and begin as
yellow but then become blue and fade to black with age. Frames
age when any detail level 10 event happens. For example on the
AVL tree only commands (INSERT, DELETE, etc.) age the tree, the
other things (like the actual insertion process or rotations)
are all frames at the same age in the movie. For more
information about what actions age the bar (or are at which
detail level) consult the section on the specific data
structure.
START -- this opens the Datafile you specified using the Open menu (or
TestData.dsdata by default). It also "sets up" the movie so it is
ready to play. You do not need to use this if you are beginning
from scratch (for example inserting all the data from scratch).
When you have already loaded the commands from a Datafile, this
button will not appear.
Command line display -- This isn't actually a button (so doesn't do anything
when clicked on). It shows the command used or
information about what is happening.
C. DataFiles
These files are used so you do not have to retype all of the commands each
time you wish to experiment with the data structure. Every DataFile has the
extension .dsdata to distinguish it from other files. There are a number of
commands that are universally supported:
# -- This is a comment. Anything following this symbol is ignored.
## -- This is a comment that is listed when the user plays the movie. You
can use these to give information about what is happening at a certain
point in the movie.
PAUSE -- This line pauses the data structure if it is playing at this point.
Pressing the play button again causes it to continue playing after
this line.
OPTION -- This sets the options of the program. The suboptions possible are
the following:
DS -- This sets the current data structure. The
possible options are currently BINARYTREE, AVLTREE,
and B-TREE. The default is BINARYTREE.
SPEED -- This sets the play speed of the movie.
The default is 2000.
DETAILLEVEL -- This sets the detail level to be displayed.
The default is 5.
All other commands are data structure specific and are listed in the Datafile
section under the specific data structure. Any commands or options that are
not set will have the current value used for them (in most cases the default).
However, if you set a value then the current value will be changed to that when
the data file is loaded. This is especially important when you wish to allow
a datafile to be used for multiple data structures. In this case you should
keep the default data structure (don't click anything) and then do all of your
insertions and deletions. This way the user may change the data structure and
then reload the file to test the input set on the different data structures.
For example the file:
OPTION DS B-TREE
OPTION SPEED 1000
would force the data structure to be a B-TREE but would allow the user to change
it to a 5-9 tree or a 3-5 tree and still use the same data file. It would also
change the play speed to be 1000 (1 second). The previous setting for detail
level would be retained.
III. The Data Structures
The code for the data structures is separate from the main program. It is
possible for a programmer with minimal knowledge of how the main portion of the
program works to write a new data structure. If you have any problem make sure
you check under the data structure. For more information on how to program a
new data structure read the PROGRAMMER MANUAL.
Each data structure has a section on DataFile commands, Action Buttons, Data
Structure Settings, detail levels, and online help.
A. Binary Tree
A binary tree is a data structure where each node may have two children (a
left and a right child). The type of binary tree implemented is actually a
specialized kind called a binary search tree (which will be referred to in the
rest of this documentation as binary tree). Nodes off of the left child are
always less than the current node and nodes off of the right child are always
greater. A binary tree allows you to find elements quickly if the tree is
balanced. For example, if you had a balanced binary tree with every person in
the world's name (6 billion names) you could find any name in the tree with at
most 33 comparisons. For more information on binary trees read any algorithms
textbook.
The Binary Tree represented by this program has a few limitations that other
binary trees may not. All nodes must have a "key value" of 1 or greater.
Each node must have a different "key value". For best readability, it is best
to use numbers with 2 or fewer digits (although the program will work with
reasonably large key values).
The displayed Binary Tree nodes have the same age as the frame where they
were inserted (and therefore the same color). This allows you to tell at a
glance which nodes are new and which are old.
This data structure supports the following commands from a DataFile:
PRINT -- This performs a traversal and prints the key information and
child information at each node. This data is sent to standard
out (the text window where you are running the program from).
INSERT -- This inserts the node(s) following the word INSERT
(multiple nodes should be separated by spaces).
DELETE -- This deletes the node(s) following the word DELETE
(multiple nodes should be separated by spaces).
DSOPTION DELETETYPE -- This is currently the only option supported
by Binary Tree. The possible values are
Alternating, Predecessor, Successor, and
Random. See the section on Data Structure
Settings for more details.
The detail level of each of the Binary Tree operations is as follows:
Comparison during an insert (level 1)
Adding the node once you figure out where it goes (level 2)
Explaining what will be promoted, etc. during a deletion (level 6)
The request for a command from datafile or a bottom button (level 4)
The result of a command from datafile or a bottom button (level 10)
The Data Structure Settings box has the following options:
Delete Settings
Alternating -- Predecessor one time, successor the next (when the
choice matters, i.e. there are two children of the
deleted node).
Predecessor -- Moves the node with the value closest to it in the tree
but lower than it. See an algorithms book for more
information.
Successor -- Moves the node with the value closest to it in the tree
but higher than it. See an algorithms book for more
information.
Random -- Randomly chooses successor or predecessor each time.
Action Buttons:
View as Root -- This actually does nothing (because a click on a node
automatically changes the view to this by default)
Insert -- This brings up the insert menu and asks what nodes you want to
insert. This will end the movie after the current point.
Delete -- This brings up the Delete menu and asks what nodes you want to
delete. This will end the movie after the current point.
Clicking on a node -- This makes that node "root" of the tree (at least
from your viewpoint). You may use any of the other
functions (Play, Rewind, etc.) while viewing as
root. If you move to a portion of the movie where
your root node no longer exists your view will
automatically change back to normal.
Online Help Menu:
This asks you to refer to this file. At some point I may put useful
information in there.
B. AVL Tree
An AVL tree is a data structure is similar to a binary tree (in most
respects). The main difference is that in an AVL tree each node has a depth
and the tree has a balance property. The balance property says that at each
node the right child depth will be within 2 of the left child depth. If this
is not true then the node is rotated so this becomes true. For more
information about the rotations consult an algorithms textbook.
The AVL Tree represented by this program has the same restrictions that the
Binary Tree does (see above).
The displayed AVL Tree nodes have the same age as the frame where they
were inserted (similar to the Binary Tree). The age may move with the key
during rotations (see the Age Movement Settings below).
This data structure supports the following commands from a DataFile:
PRINT -- This performs a traversal and prints the key information and
child information at each node. This data is sent to standard
out (the text window where you are running the program from).
INSERT -- This inserts the node(s) following the word INSERT
(multiple nodes should be separated by spaces).
DELETE -- This deletes the node(s) following the word DELETE
(multiple nodes should be separated by spaces).