Splay Tree Search Implementation

Question

I have been trying to learn the ins and outs of some data structures and I am trying to get a binary splay tree to work properly. Every time I run the following code and the node I am looking for is more than one past the root it tells me it is there and then just deletes that whole side from the root down. It works fine if the node is only one level down from the top.

I am not sure what is going wrong but I suppose it has something to do with my rotate functions. I got it to work properly for the insert function which is what I modeled this after.

public class SplayBST {
    Node root;
    int count;
    int level = 0;
    boolean found = false;
    public SplayBST() {
        root = null;
        count = 0;
    }

public String searchIt(String x) {
    //after finishing search method I need to check if splaySearch exists then don't insert just splay it
    splaySearch(root, x);
    if (this.found == true) {
        this.found = false;
        return x;
    }
    else {
        return null;
    }
}


    Node splaySearch(Node h, String x) {
        if (h == null) {
            return null;
        }
        if (x.compareTo(h.value) < 0) {
            try {
            if (x.compareTo(h.left.value) < 0) {
                h.left.left = splaySearch(h.left.left, x);
                h = rotateRight(h);
            } else if (x.compareTo(h.left.value) > 0) {
                h.left.right = splaySearch(h.left.right, x);
                h.left = rotateLeft(h.left);
            }
            else {
                this.found = true;
                return h.left;
            }
            return rotateRight(h);
            } 
        catch (NullPointerException ex) {
            return null;
            }
        }

        else { //basically x.compareTo(h.value)>0
            try {
            if (x.compareTo(h.right.value) > 0) {
                h.right.right = splaySearch(h.right.right, x);                
                h = rotateLeft(h);
            } else if (x.compareTo(h.right.value) < 0) {
                h.right.left = splaySearch(h.right.left, x);
                h.right = rotateRight(h.right);
            }
            else {
                this.found = true;
                return h.right;
            }
            return rotateLeft(h);
            }
            catch (NullPointerException ex) {
                return null;
            }
        }
    }


    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;
    }


    class Node {
        Node left;
        Node right;
        String value;
        int pos;
        public Node(String x) {
            left = null;
            right = null;
            value = x;
        }
    }
}

Answer 1

Your problem is that when you rotate, you update the reference to node H in the function "SplaySearch", but you do not update the parent node in the original "searchIt" function. Thus, the program "thinks" that the original parent node remains the parent, even though the rotated node should be the parent. Thus, when you run whatever method you use to print your tree, you print from a node that is not actually the parent node of the tree, but a child (the level it is on depends on how many times your program called rotateLeft and rotateRight).

To fix this, I suggest implementing search as in a normal binary tree, and then making a "splay" function completely separate from the search function that splays a node to the top of the tree. You would call this splay function at the end of every search, making sure to properly update your reference. This is the traditional way to implement splay trees, and I suggest you take a look at it (maybe look at the wikipedia article on splay trees or do a Google search). Also, you may want to know that your rotate functions are not complete. In terms of splay trees, you also have 2 separate types of double rotations which are very different from single rotations. Again, I suggest looking up splay trees to learn about them more in depth.

Answer 2

I second Tristan Hull's approach to creating a regular BST with a "working" search method. Once you get that working, adding a splay method is rather trivial. I've actually done the same thing when I implemented a Splay Tree in Java. It's a better software design and a simpler implementation.