java splay tree program

Computer Science 282 Programming Assignment #2

In addition to requiring you to get splay trees to work, I also want you to learn some basic things about Java Strings, so you will build trees of Strings instead of int’s. For example, you will need to use compareTo (or compareToIgnoreCase – we will need to discuss which) to compare two Strings.

Add whatever is necessary so that the three classes below behave correctly. Leave all variables, method names, and code fragments exactly as they appear. Only add code to make the methods work. Do not add a setString method in the StringNode class.

Insert is easier than search so I recommend you work on that first. You will find reference to “top- down” algorithms when you scan the Web. Do not do that. Use the algorithm as described in class and in the Week 5 posting. In terms of implementing backtracking it is really nothing more than what you do after making a recursive call. With insert, for example, you will make the usual recursive calls to insert and then after the call you will have to deal with the splay. There are two cases. (1) If the element you inserted is a child of the current node then it is not time to splay since we always splay two levels. (2) If the element is not a child you need to determine (a) if it’s to the left or right of the current node and (b) whether to do a zig- zig or a zig-zag. Make appropriate calls to the rotate methods to get the job done.

You might also have to do a final zig at the root if the splaying came out odd. This is best done in the driver program.

Search is more complicated because if the element is not found you still must splay something to the root. You will splay the last node visited before landing on null. For example, looking at the last tree drawn in week5-lecture.pdf, if searching for 65, 60 will be splayed to the root. If searching for 5, 10 will be splayed.

But there is an additional complication. While backtracking, how do you tell your method what is being splayed? You passed in a value to search and if it wasn’t found you must splay a different value. This means you need to be able to change the parameter value so that when backtracking the parameter has changed from the value being searched for to the value being splayed. That is why WrapString is used in the recursive search (and only there). You will then be able to use a statement like this in your recursive search to change the value of the String being searched to the String being splayed:

str.string = t.getString();

As always, I’d love to see some questions and conversations on Discussion.

Submission and other details. Many of you did not follow rules 2 – 4 from the last assignment despite my pleas and threats to take off points. I will be less lenient this time. Of course this time the name of your file should be prog2.java. This should not be the name of your class. Also do not use the word package anywhere. I spent a lot of time editing “package” out of your programs, fixing class names, and numerous other changes. Please don’t make me do that this time. Also, as some of you are aware, if you submit multiple times Canvas tacks a suffix onto your file name. I can live with that. Just make sure the base part of the file name is prog2.java. Finally, though it should go without saying, the program you turn in must be your own work. Do not copy code from someone else. Do not share your own code.

class StringNode {

private String word; private StringNode left, right;

// The only constructor you will need public StringNode(String w) { }

public String getString() { }

public StringNode getLeft() { }

public void setLeft(StringNode pt) { }

public StringNode getRight() { }

public void setRight(StringNode pt) { }

} // StringNode

// So that a String can change. There is nothing you need to add // to this class class WrapString {

// Yes, I am allowing (and encouraging) direct access to the String // in this class

public String string;

public WrapString(String str) { this.string = str;

} }

class SplayBST {

// member variable pointing to the root of the splay tree // It really should be private but I need access to it for the test program StringNode root;

// default constructor public SplayBST() { root = null; }

// copy constructor // Be sure to make a copy of the entire tree // Do not make two pointers point to the same tree

public SplayBST(SplayBST t) { }

// like last time public static String myName() { }

// This is the driver method. You should also check for and perform // a final zig here, not in the recursive method // You will also have to write the 2-parameter recursive insert method

public void insert(String s) { }

// The 2-parameter recursive method private static StringNode insert(String d, StringNode t) {

// if s is not in the tree, splay the last node visited // final zig, if needed, is done here // Return null if the string is not found public StringNode search(String s) { }

// recursive search method // if str not in the tree str backtracks with value of last node visited

public StringNode search(WrapString str, StringNode t) { }

public static StringNode rotateLeft(StringNode t) { }

public static StringNode rotateRight(StringNode t) { }

// How many leaves in the splay tree? public int leafCt() { }

// What is the height the splay tree? public int height() { }

// How many nodes have exactly 1 non-null children public int stickCt() { }

}