Chat with us, powered by LiveChat 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 ints. For example, yo | Wridemy

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 ints. For example, yo

 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. 

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() { }

}

  • Computer Science 282

,

/* * insertion tests. fred-0 (fred-1)joanie-0 ((fred-2)joanie-1)lynn-0 (((fred-3)joanie-2)lynn-1)peter-0 (fred-1)helen-0((joanie-2)lynn-1(peter-2)) (((((((fred-7)helen-6)hope-5)ian-4)joanie-3)john-2)kelly-1((lynn-3)miki-2))nichole-0(peter-1(tom-2)) search tests. Found. (((((((fred-7)helen-6)hope-5)ian-4)joanie-3)john-2)kelly-1((lynn-3)miki-2))nichole-0(peter-1(tom-2)) Found. ((fred-2)helen-1)hope-0(((ian-3(joanie-4))john-2(kelly-3((lynn-5)miki-4)))nichole-1(peter-2(tom-3))) Found. (((fred-3)helen-2)hope-1((ian-3(joanie-4))john-2(kelly-3((lynn-5)miki-4))))nichole-0(peter-1(tom-2)) Not in the tree. ((((fred-4)helen-3)hope-2(ian-3(joanie-4)))john-1(kelly-2))lynn-0((miki-2)nichole-1(peter-2(tom-3))) Not in the tree. ((((fred-4)helen-3)hope-2)ian-1)joanie-0(john-1((kelly-3)lynn-2((miki-4)nichole-3(peter-4(tom-5))))) Not in the tree. (((fred-3)helen-2)hope-1)ian-0(joanie-1(john-2((kelly-4)lynn-3((miki-5)nichole-4(peter-5(tom-6)))))) */ public class Test0 { public static void main(String[] args) { SplayBSTXtra0 t = new SplayBSTXtra0(); System.out.println("insertion tests."); System.out.println(t); t.insert("fred"); System.out.println(t); t.insert("joanie"); System.out.println(t); t.insert("lynn"); System.out.println(t); t.insert("peter"); System.out.println(t); t.insert("helen"); System.out.println(t); t.insert("joanie"); t.insert("hope"); t.insert("ian"); t.insert("tom"); t.insert("miki"); t.insert("john"); System.out.println("b4 kel " + t); t.insert("kelly"); System.out.println(t);t.insert("nichole"); System.out.println(t); System.out.println(); System.out.println();/* System.out.println("search tests."); if (t.search("nichole") == null) System.out.println("Not in the tree."); else System.out.println("Found."); System.out.println(t); if (t.search("hope") == null) System.out.println("Not in the tree."); else System.out.println("Found."); System.out.println(t); if (t.search("nichole") == null) System.out.println("Not in the tree."); else System.out.println("Found."); System.out.println(t); if (t.search("larry") == null) System.out.println("Not in the tree."); else System.out.println("Found."); System.out.println(t); if (t.search("jack") == null) System.out.println("Not in the tree."); else System.out.println("Found."); System.out.println(t); if (t.search("jack") == null) System.out.println("Not in the tree."); else System.out.println("Found."); System.out.println(t);*/ } } class SplayBSTXtra0 extends SplayBST { public SplayBSTXtra0() { super(); } public StringNode getRoot() { return root; } // for output purposes — override Object version public String toString() { return toString(root, 0); } private static String toString(StringNode l, int x) { String s = ""; if (l == null) ; // nothing to output else { if (l.getLeft() != null) // don't output empty subtrees s = '(' + toString(l.getLeft(), x + 1) + ')'; s = s + l.getString() + "-" + x; if (l.getRight() != null) // don't output empty subtrees s = s + '(' + toString(l.getRight(), x + 1) + ')'; } return s; } }

,

Splay trees balance trees in a different way from AVL trees. An AVL tree always has height O(log n) meaning that every operation will require O(log n) time which is as good as you can possibly expect fro a BST. Splay trees allow some operations to take much longer, but the slow operations are balanced out by a sufficient number of faster ones. This is referred to as amortized complexity where over a total of n operations on a splay tree the average amount of time spent on each operation is O(log n). You will see an example of this later.

Pretty much everything you need to know about splay trees is here. You only need to read the first 3 sections. Some important points you will read are: (1) It is possible to have a splay tree with height O(n) but on average the height will be O(log n). (2) Splay trees require no extra storage so they are space efficient. AVL trees require a balance factor in each node, so this less true for AVL trees. (3) Somewhat surprisingly, an element after insertion is moved (splayed) to the root of the tree. His may sound inefficient but it is during this splaying process that the tree is balanced. (4) The main operations performed while balancing a splay tree are zig-zig and zig-zag. It’s also possible for there to be a single zig when the element moves to the root of the tree.

Looking at section 3 on operations, the simple zig step should look familiar to you. It is a simple right or left rotation. So, looking at the zig step diagram you can see that moving x to the root is just a right rotation.

When splaying up from further down the tree we always go two steps at once. If the node being splayed up is either left–left or right–right of its grandparent then a zig-zig splay is performed. Looking at the zig-zig diagram you can see to accomplish this you must first rotate g to the right, then rotate p to the right, bringing x two levels higher in the tree. If you do it in the other order you will not end up with the same tree. I suggest you try it to confirm what I say.

If when splaying up a node it is either left–right or right–left of the grandparent then a zig-zag is performed. Looking at the zig-zag diagram we this this is done by rotating p left, then g right. Even though both of these were two separate single rotations, to help remember the algorithm I suggest you think of them both as different but easy to remember double rotations – just as you should have done with AVL trees.

Here is an example with some explanations.

Start with an empty tree.

Now insert 10. This is a 1-node tree, 10 is already at the root so no splaying necessary.

10

Insert 20. First insert as you would with any BST, giving

10

20

Now splay 20 to the root. It is just one step away, so a zig brings it to the root.

20

10

Now insert 30.

20 10 30

Again, it is one step from the root, so zig it up.

30

20

10

Now insert 40, 50, 60, 70, 80 and it is easy to see that the resulting splay tree will be

80

70

60

50

40

30

20

10

This takes us to one of the fundamental facts of splay trees. Notice this is a worst case tree. If we continued this process for n insertions we would have a tree of height n. But the good news is that is was very fast to build this tree. Each insertion only took 1 step instead of O(log n). This means we’re way ahead of the game. We’ve been averaging constant time instead of O(log n). Now let’s insert something under 10. This is a worst case insertion so it will hurt our average, but something else good happens, too. Inserting 15 will give us this tree before we do any splaying.

80

70

60

50

40

30

20

10

15

Now we must splay 15 to the root. We will do this step by step. Look at the grandparent of 15, 20. 15 is left–right under 20, so we perform a zig-zag.

80

70

60

50

40

30

15

10 20

Now look at the grandparent of 15 to figure out the next splay step. It is 40, 15 is left–left so we perform a zig-zig.

80

70

60

50

15

10 30

20 40

Similarly, the grandparent is 60, so another zig-zig step.

80

70

15

10 50

30 60

20 40

And now one more ziz-zig step to the root, gives us this.

15

10 70

50 80

30 60

20 40

This demonstrates the other fundamental fact of splay trees, i.e., bad splay trees do not stay bad for long. Even though the tree we started with was bad and insertion took a long time, the new tree is half the height of the original one. So even in the worst case the next insertion will only take half as long as the previous one. The mathematical details are a bit complicated, but this example should help convince you that splay trees really do behave as I promised.

One more example. Let’s insert 35 into the previous tree and watch how it splays to the root. Insert 35.

15

10 70

50 80

30 60

20 40

35

Zig-zag to where 30 is.

15

10 70

50 80

35 60

30 40

20

Zig-zig to where 70 is.

15

10 35

30 50

20 40 70

60 80

No grandparent. Just zig to the root.

35

15 50

10 30 40 70

20 60 80

Try some on your own to be sure you understand. You can check your work by using the following helpful animation: https://www.cs.usfca.edu/~galles/visualization/SplayTree.html

  • Splay trees balance trees in a different way from AVL trees. An AVL tree always has height O(log n) meaning that every operation will require O(log n) time which is as good as you can possibly expect fro a BST. Splay trees allow some operations to take much longer, but the slow operations are balanced out by a sufficient number of faster ones. This is referred to as amortized complexity where over a total of n operations on a splay tree the average amount of time spent on each operation is O(log n). You will see an example of this later.

Our website has a team of professional writers who can help you write any of your homework. They will write your papers from scratch. We also have a team of editors just to make sure all papers are of HIGH QUALITY & PLAGIARISM FREE. To make an Order you only need to click Ask A Question and we will direct you to our Order Page at WriteDemy. Then fill Our Order Form with all your assignment instructions. Select your deadline and pay for your paper. You will get it few hours before your set deadline.

Fill in all the assignment paper details that are required in the order form with the standard information being the page count, deadline, academic level and type of paper. It is advisable to have this information at hand so that you can quickly fill in the necessary information needed in the form for the essay writer to be immediately assigned to your writing project. Make payment for the custom essay order to enable us to assign a suitable writer to your order. Payments are made through Paypal on a secured billing page. Finally, sit back and relax.

Do you need an answer to this or any other questions?

About Wridemy

We are a professional paper writing website. If you have searched a question and bumped into our website just know you are in the right place to get help in your coursework. We offer HIGH QUALITY & PLAGIARISM FREE Papers.

How It Works

To make an Order you only need to click on “Order Now” and we will direct you to our Order Page. Fill Our Order Form with all your assignment instructions. Select your deadline and pay for your paper. You will get it few hours before your set deadline.

Are there Discounts?

All new clients are eligible for 20% off in their first Order. Our payment method is safe and secure.

Hire a tutor today CLICK HERE to make your first order

Related Tags

Academic APA Writing College Course Discussion Management English Finance General Graduate History Information Justify Literature MLA