Summary: CS 2420 Assignment 3 Page 1
CS 2420 Splay Trees
Program 3 20 points Due Oct 1, 2010
Part 1: You are to create a splay tree using a small data set.
For ease it coding, we will do a "top down" splay, in which we start splaying before we ever get to the
node we care about. This makes it a bit easier than what the book shows in Chapter 4 as we don't have to
find the node and look up two levels. We make another simplification. Instead of doing the double
rotation (for a zigzag case), we just go down ONE level and do a left or right rotation (a zig). This makes
the coding easier as we don't have to code a double rotation.
Create a splay tree abstract data type, with the following operations:
printTree(string msg): prints the msg before printing the tree prettily [Print prettily means that
nodes are indented to show their level in the tree]
makeEmpty(): remove all nodes from the tree, recursively
Create a splay tree from tiny3.txt and test the various operations. TestSplay.cpp contains code to do this
checking. (Leave this code in your program so the grader can verify all operations work.)
Part 2: Create a new splay tree from the input dictionary3.txt. Read in search3.txt and count the number