3
\$\begingroup\$

I wrote an splay search tree using the algorithm description and debug and now I want to find out how I can optimize it, maybe I have some obvious errors and I will be glad if someone shows them to me.

Java code:

private final class SplayTree{

    private Node root;

    private void keepParent(Node v){
        if(v.l != null) v.l.p = v;
        if(v.r != null) v.r.p = v;
    }

    private void rotate(Node parent, Node child){

        Node gparent = parent.p;
        if(gparent != null){
            if(gparent.l != null && gparent.l.k == parent.k)
                gparent.l = child;
            else
                gparent.r = child;
        }

        if(parent.l != null && parent.l.k == child.k){
           Node tmp = child.r;
           child.r = parent;
           parent.l = tmp;
        }else{
            Node tmp = child.l;
            child.l = parent;
            parent.r = tmp;
        }

        keepParent(child);
        keepParent(parent);
        child.p = gparent;
    }

    private Node splay(Node node){

        if(node == null)
            return null;

        while (node.p != null){
            Node parent = node.p;
            Node gparent = parent.p;
            if(gparent == null){
                rotate(parent, node);
            }else{
                if(gparent.l != null && gparent.l.k == parent.k && parent.l != null && parent.l.k == node.k){
                    rotate(gparent, parent);
                    rotate(parent, node);
                }else if(gparent.r != null && gparent.r.k == parent.k && parent.r != null && parent.r.k == node.k){
                    rotate(gparent, parent);
                    rotate(parent, node);
                }else{
                    rotate(parent, node);
                    rotate(gparent, node);
                }
            }
        }

        return node;
    }

    private Node find(int key){

        Node node = root, prev = null;
        while (node != null){
            prev = node;
            if(node.k == key)
                break;
            else if(key < node.k)
                node = node.l;
            else
                node = node.r;
        }
        if(node == null) {
            node = prev;
            if(node != null) this.root = node;
        }
        else
            this.root = node;

        return splay(node);
    }

    public long sum(int l, int r){

        sum = 0;
        Node root = this.root;
        while (root != null){
            if(root.k >= l && root.k <= r)
                break;
            else if(root.k < l)
                root = root.r;
            else
                root = root.l;
        }
        if(root == null)
            return sum;

        Queue<Node> queue = new ArrayDeque<>();
        queue.add(root);
        Node node;
        while ((node = queue.poll()) != null){

            if(node.k >= l && node.k <= r)
                sum += node.k;

            if(node.l != null)
                queue.add(node.l);

            if(node.r != null)
                queue.add(node.r);
        }

        return sum;
    }

    public Node[] split(int key){

        if(this.root == null)
            return new Node[]{null, null};

        Node subRoot = find(key);
        if(subRoot.k < key){
            Node right = subRoot.r;
            if(right != null) right.p = null;
            subRoot.r = null;
            return new Node[]{subRoot, right};
        }else{
            Node left = subRoot.l;
            if(left != null) left.p = null;
            subRoot.l = null;
            return new Node[]{left, subRoot};
        }

    }

    public Node insert(int key){

        if(root == null)
            return this.root = new Node(key);

        Node prev = null;
        while (root != null){
            prev = root;
            if(root.k == key)
                return splay(root);
            else if(key < root.k)
                root = root.l;
            else
                root = root.r;
        }
        root = prev;

        Node node = new Node(key);
        if(key < root.k){
            root.l = node;
            node.p = root;
        }else{
            root.r = node;
            node.p = root;
        }

        return this.root = splay(node);
    }

    public Node merge(Node l, Node r){

        if(r == null)
            return l;
        if (l == null)
            return r;

        l = maximum(l);
        l.r = r;
        r.p = l;

        return l;
    }

    public Node remove(int key){

        Node root = find(key);
        if(root == null || root.k != key)
            return root;

        if(root.l != null) root.l.p = null;
        if(root.r != null) root.r.p = null;

        return this.root = merge(root.l, root.r);
    }

    public Node maximum(Node root){

        while(root.r != null)
            root = root.r;

        return splay(root);
    }

}

private final class Node{
    int k;
    Node l;
    Node r;
    Node p;

    Node(int k) {
        this.k = k;
    }
}

It would also be interesting to know if there are any mistakes in the style of the code. I will be glad to any help

\$\endgroup\$
2
\$\begingroup\$

There's two things that I noticed. This first being a potential change in structure in find. You could handle the else branch instead of (effectively) setting a flag indicating whether you used a break. This keeps similar logic together, but at the cost of introducing another exit point to your function, which can be considered bad in some styles.

private Node find(int key){

    Node node = root, prev = null;
    while (node != null){
        prev = node;
        if(node.k == key)
            this.root = node;
            return splay(node);
        else if(key < node.k)
            node = node.l;
        else
            node = node.r;
    }

    if(prev != null) this.root = prev;
    return splay(prev);
}

The other potential change I want to point out is in splay. You have some inconsistency in your if nesting. You should probably stick to all else ifs, it makes it easier to draw comparisons between the 4 cases, and reduces unnecessary indentation. You should also consider wrapping the two particularly long conditionals, so that you can control where they wrap if they are opened on a 80 character-wide terminal, and can abuse the symmetry within each conditional to help expose any copy/paste errors.

private Node splay(Node node){

    if(node == null)
        return null;

    while (node.p != null){
        Node parent = node.p;
        Node gparent = parent.p;
        if(gparent == null){
            rotate(parent, node);
        }else if(gparent.l != null && gparent.l.k == parent.k
               && parent.l != null &&  parent.l.k == node.k){
            rotate(gparent, parent);
            rotate(parent, node);
        }else if(gparent.r != null && gparent.r.k == parent.k
               && parent.r != null &&  parent.r.k == node.k){
            rotate(gparent, parent);
            rotate(parent, node);
        }else{
            rotate(parent, node);
            rotate(gparent, node);
        }
    }

    return node;
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.