PLEASE READ THE REQUIREMENT CAREFULLY. Thank You.

IF you Don't want to re-write the code, you can copy paste a part of the requirement, then you can find the code. But please give me your own solution, but not copy others. Thank you so much

node.rightChild = new BinaryTreeNode(entry, node);

splayNode(node.rightChild);

} else {

insertHelper(entry, key, node.rightChild);

}

}

}

public Entry find(Object key) {

BinaryTreeNode node = findHelper((Comparable) key, root);

if (node == null) {

return null;

} else {

return node.entry;

}

}

private BinaryTreeNode findHelper(Comparable key, BinaryTreeNode node) {

if (node == null) {

return null;

}

if (key.compareTo(node.entry.key())

if (node.leftChild == null) {

splayNode(node); // Splay the last node visited to the root.

return null;

}

return findHelper(key, node.leftChild);

} else if (key.compareTo(node.entry.key()) > 0) { // "key" > "node"'s key

if (node.rightChild == null) {

splayNode(node); // Splay the last node visited to the root.

return null;

}

return findHelper(key, node.rightChild);

} else { // "key" == "node"'s key

splayNode(node); // Splay the found node to the root.

return node;

}

}

no entry contains the specified key.

**/

public Entry remove(Object key) {

// Not implemented.

return null;

}

/**

* Convert the tree into a string.

**/

public String toString() {

if (root == null) {

return "";

} else {

return root.toString();

}

}

private static void makeUnbalancedTree(SplayTree tree) {

tree.insert(new Integer(10), "A");

tree.insert(new Integer(9), "B");

tree.insert(new Integer(8), "C");

tree.insert(new Integer(7), "D");

tree.insert(new Integer(6), "E");

tree.insert(new Integer(5), "F");

tree.insert(new Integer(4), "G");

tree.insert(new Integer(3), "H");

tree.insert(new Integer(2), "I");

tree.insert(new Integer(1), "J");

}

/**

* main() tests the splay tree.

*

* DO NOT CHANGE THE FOLLOWING TEST CODE!

**/

public static void main(String[] args) {

SplayTree tree = new SplayTree();

System.out.println(" PART I: Testing zigZig() ");

String shouldBe = null;

System.out.println("Inserting 1G, 3O, 2O, 5J, 4D, 7B, 6O into Tree 1.");

tree.insert(new Integer(1), "G");

tree.insert(new Integer(3), "O");

Entry testEntry = tree.insert(new Integer(2), "O");

BinaryTreeNode testNode =

tree.findHelper((Comparable) testEntry.key, tree.root);

tree.insert(new Integer(5), "J");

tree.insert(new Integer(4), "D");

tree.insert(new Integer(7), "B");

tree.insert(new Integer(6), "O");

System.out.println("Tree 1 is: " + tree);

if (tree.toString().equals("(((((1G)2O)3O)4D)5J)6O(7B)")) {

System.out.println("Skipping the rest of Part I.");

} else if (tree.toString().equals("(((1G)2O(3O))4D(5J))6O(7B)")) {

System.out.println(" Performing zig-zig on node with key 2.");

tree.zigZig(testNode);

System.out.println("Tree 1 is now: " + tree);

shouldBe = "(1G)2O((3O)4D((5J)6O(7B)))";

if (tree.toString().equals(shouldBe)) {

System.out.println(" Zig-zig successful.");

} else {

System.out.println(" ERROR: SHOULD BE " + shouldBe);

}

System.out.println(" Attempting to balance an unbalanced tree using only zig():");

SplayTree unbalanced = new SplayTree();

makeUnbalancedTree(unbalanced);

System.out.println(" Inserting 10A, 9B, 8C, 7D, 6E, 5F, 4G, 3H, 2I, 1J");

System.out.println("tree is: " + unbalanced);

shouldBe = "1J(2I(3H(4G(5F(6E(7D(8C(9B(10A)))))))))";

if (!unbalanced.toString().equals(shouldBe)) {

System.out.println(" ERROR: SHOULD BE " + shouldBe);

}

unbalanced.testFind(10, "A");

System.out.println("Tree 1 is now: " + unbalanced);

shouldBe = "(1J(2I(3H(4G(5F(6E(7D(8C(9B)))))))))10A";

if (!unbalanced.toString().equals(shouldBe)) {

System.out.println(" ERROR: SHOULD BE " + shouldBe);

} else {

System.out.println("As you can see, the tree is still unbalanced. " +

"If there are no errors, go on to Part II.");

}

} else {

System.out.println("ERROR: splayNode() is returning incorrect results.");

}

System.out.println(" PART II: Testing splayNode()");

System.out.println(" Calling splayNode() on the unbalanced tree: ");

System.out.println("Inserting 10A, 9B, 8C, 7D, 6E, 5F, 4G, 3H, 2I, 1J");

SplayTree splayTest = new SplayTree();

makeUnbalancedTree(splayTest);

System.out.println("tree is: " + splayTest);

splayTest.testFind(10, "A");

System.out.println("The tree should be better balanced now: " + splayTest);

shouldBe = "(1J((2I)3H((4G)5F((6E)7D((8C)9B)))))10A";

if (!splayTest.toString().equals(shouldBe)) {

System.out.println(" ERROR: SHOULD BE " + shouldBe);

}

System.out.println(" Some find() operations on a new tree to test splayNode(): ");

System.out.println("Inserting 3A, 7B, 4C, 2D, 9E, 1F");

SplayTree tree2 = new SplayTree();

tree2.insert(new Integer(3), "A");

tree2.insert(new Integer(7), "B");

tree2.insert(new Integer(4), "C");

tree2.insert(new Integer(2), "D");

tree2.insert(new Integer(9), "E");

tree2.insert(new Integer(1), "F");

System.out.println("Tree 2 is: " + tree2);

shouldBe = "1F((2D(3A((4C)7B)))9E)";

if (!tree2.toString().equals(shouldBe)) {

System.out.println(" ERROR: SHOULD BE " + shouldBe);

}

tree2.testFind(7, "B");

System.out.println("Tree 2 is: " + tree2);

shouldBe = "(1F((2D)3A(4C)))7B(9E)";

if (!tree2.toString().equals(shouldBe)) {

System.out.println(" ERROR: SHOULD BE " + shouldBe);

}

tree2.testFind(4, "C");

System.out.println("Tree 2 is: " + tree2);

shouldBe = "((1F(2D))3A)4C(7B(9E))";

if (!tree2.toString().equals(shouldBe)) {

System.out.println(" ERROR: SHOULD BE " + shouldBe);

}

}

private void testRemove(int n, String shouldBe) {

Integer key = new Integer(n);

System.out.print("After remove(" + n + "): ");

remove(key);

System.out.println(this);

if (!toString().equals(shouldBe)) {

System.out.println(" SHOULD BE " + shouldBe);

}

}

private void testFind(int n, Object truth) {

Integer key = new Integer(n);

Entry entry = find(key);

System.out.println("Calling find(" + n + ")");

if (entry == null) {

System.out.println(" returned null.");

if (truth != null) {

System.out.println(" SHOULD BE " + truth + ".");

}

} else {

System.out.println(" returned " + entry.value() + ".");

if (!entry.value().equals(truth)) {

if (truth == null) {

System.out.println(" SHOULD BE null.");

} else {

System.out.println(" SHOULD BE " + truth + ".");

}

}

}

}

}

Goal: To give you experience with implementing splay tree operations. The fields and methods of the SplayTree class are the same as the BinaryTree class you modified in Lab 11; it even uses the same BinaryTreeNodes and implements the same Dictionary interface. We have provided implementations of the find ) and insert ) methods. (We have omitted the remove ) method) These implementations are similar to those in an ordinary binary search tree, but they always end by splaying a node to the root. However, the splay operation splayNode( does not work correctly, because it does not use the zig-zig operation. Instead, it splays a node to the root by doing a sequence of zig operations. Unfortunately, this improper splaying operation does not rebalance an extremely unbalanced splay tree Your job is to write a method zigZig) that implements the zig-zig step, then fix splayNode( SO that it uses the zig, zig-zag, and zig-ziq steps at the correct times. After you finish each part, use the test code to check your progress Part I Implement ziqZiq () We have provided implementations of tree rotations in the methods rotateLeft () and rotateRight We have also provided implementations of the zig and ziq-zag steps in the methods zig() and zigZag ( we suggest you examine those methods. Then fill in the body of a method zigZiq) that implements the zig-zig step. Refer to the Lecture 36 notes if you need help remembering the difference. Make sure that the test for Part I runs without printing any error messages; it should say " Successfully completed Part I" We suggest that you don't change splayNode () until you have Part I working