Splay Tree Homework Help

[PtblDuffy]

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!

[Taywin]

Your code is not completed as you know that the splaySearch() is missing. Also, when you are asked to verify a code, you should start from verifying methods which do not call any other method first. Then keep going up the tier. If you are not sure about the correctness of a method, write down an input and its supposed to be correct result, and then check the result from the method against the correct result. You may look at splay tree algorithm too.

[PtblDuffy]

Thanks, figured it out!