No description, website, or topics provided.
Python
Switch branches/tags
Nothing to show
Clone or download
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Failed to load latest commit information.
README
delete.txt
insert.txt
license.txt
scapegoat.py
tree.txt

README

##########
# Author # 
##########
Matt Johnson <matt.johnson@email.wsu.edu>

###############
# Description #
###############
This program implements a scapegoat tree as described in the following paper:
http://cg.scs.carleton.ca/~morin/teaching/5408/refs/gr93.pdf

Input to the program is a file called tree.txt. You can also specify a different
file on the command line. The first line of the file must be:
    BuildTree alpha key
where .5 <= alpha < 1, and key is an integer. Each line of the rest of the file
must contain one of the following commands:
    Insert key - inserts the integer key into the tree
    Search key - finds the specified key in the tree if it exists or gives an
                 error message 
    Delete key - delete the specified key from the tree
    Print - prints the tree structure in *pre-order* (i.e. the root is the first
            node displayed)
    Done - exits the program
key must be a unique integer.

################
# How to Build #
################
No installation is required. The program runs through the python interrepter.

##############
# How to Use #
##############
Without arguments, the program assumes there is a file called tree.txt in the
current working directory, and uses that for input:
python scapegoat.py

With an argument, the program uses it as the input file;
python scapegoat.py input_file.txt

#########
# Files #
#########
delete.txt - Sample input file with inserts and deletes
insert.txt - Sample input file with inserts
README - This file
scapegoat.py - Python implementation of a scapegoat tree
tree.txt - Large sample input file for inserts