CSE 373: Data Structures and Algorithms

Autumn 1994

Programming Assignment 1

UPDATED 10/23

  
Due at the start of class on Monday October 31.
  
  You're to write two programs, one that implements unbalanced
  binary search trees and one that implements splay trees, and
  compare their performance as indicated by the number of
  comparisons that each makes in processing the same test data
  streams.
  
  The data objects will be integers.  I'll provide test data, in
  the following format:
  
     e         # make the tree empty
     i [int]   # insert [int] into the tree; ignore if already there
     d [int]   # delete [int] from the tree; print error if not there
     f [int]   # find [int] in the tree; print error if not there
     p         # print tree in in-order
     c         # print counter of number of comparisons made
     r         # zero counter of number of comparisons made
     
  You'll need to turn in the source code of your programs, and the
  result of running your programs on the test datasets.
  
  The test datasets can be found on the MSCC cluster in
  ~c373/tree/test1,test2,test3,test4.  Here's a look at
  test3 just so you can check out the format.