0

Hello, I've been looking at this problem for a few hours, and I can't figure it out. We had to test this code and fix it if we find errors (it's a splay tree):

```
public class SplayBST {
Node root;
int count;
int level = 0;
public SplayBST() {
root = null;
count = 0;
}
//assumes no duplicates
public void add(String x) {
root = splayInsert(root, x);
count++;
}
// moves node containing x to the root
public Node search(String x) {
System.out.println("Search");
return root = splaySearch(root, x);
}
Node splayInsert(Node h, String x) {
if (h == null) {
return new Node(x);
}
if (x.compareTo(h.value) < 0) {
if (h.left == null) {
h.left = new Node(x);
return rotateRight(h);
}
if (x.compareTo(h.left.value) < 0) {
h.left.left = splayInsert(h.left.left, x);
h = rotateRight(h);
} else {
h.left.right = splayInsert(h.left.right, x);
h.left = rotateLeft(h.left);
}
return rotateRight(h);
} else { //x.compareTo(h.value)>0
if (h.right == null) {
h.right = new Node(x);
return rotateLeft(h);
}
if (x.compareTo(h.right.value) > 0) {
h.right.right = splayInsert(h.right.right, x);
h = rotateLeft(h);
} else {
h.right.left = splayInsert(h.right.left, x);
h.right = rotateRight(h.right);
}
return rotateLeft(h);
}
}
Node splaySearch(Node h, String x) {
return h;
//tbd
}
Node rotateLeft(Node h) {
Node x = h.right;
h.right = x.left;
x.left = h;
return x;
}
Node rotateRight(Node h) {
Node x = h.left;
h.left = x.right;
x.right = h;
return x;
}
void displayMe() {
String[][] output = new String[count * 2][count * 4];
output = putNode(1, (count * 4) / 2, root, output);
for (int i = 0; i < output.length; i++) {
String line = "";
for (int j = 0; j < output[i].length; j++) {
if (output[i][j] == null) {
output[i][j] = " ";
}
line += output[i][j];
}
System.out.println(line);
}
}
private String[][] putNode(int level, int pos, Node root, String[][] output) {
if (root == null) {
return output;
}
output[level][pos] = root.value;
if (root.left != null) {
output[level + 1][pos - 1] = "/";
}
if (root.right != null) {
output[level + 1][pos + 1] = "\\";
}
putNode(level + 2, pos - 2, root.left, output);
putNode(level + 2, pos + 2, root.right, output);
return output;
}
class Node {
Node left;
Node right;
String value;
int pos;
public Node(String x) {
left = null;
right = null;
value = x;
}
}
}
```

I managed to test it for a few cases:

adding 1,2,3,4,5

adding 5,4,3,2,1

adding 0,4,8,2,3

These all provided correct output. However, adding 9,3,2,8,4,0 provided incorrect output, and I can't figure out why or how to fix it. Any hints are appreciated.

Thanks!