Treap Java implementation help

Revision en1, by saichandu6, 2016-02-17 21:01:01

The output of this program should give the treap size which is 5. but it takes latest insert as root and gives size as 1 with last inserted element in the root. In c++ I can pass by reference and thus maintain persistence. In java how can I pass the objects ( Treap Node) by reference or how can I maintain the persistence. Can anyone help me out with this...

class cartesianTree {
    class Node {
        int x, y, cnt;
        Node l, r;

        Node(int _x) {
            x = _x;
            Random rnd = new Random(System.currentTimeMillis());
            int random = rnd.nextInt();
            y = (random << 16) ^ (random);
            cnt = 1;
            l = r = null;
        }

        void recalc() {
            cnt = 1;
            if (l != null) cnt += l.cnt;
            if (r != null) cnt += r.cnt;
        }
    }

    Node merge(Node l, Node r) { // All L keys should be smaller than R keys.
        if (l == null || r == null) return l != null ? l : r;
        if (l.y < r.y) {
            l.r = merge(l.r, r);
            l.recalc();
            return l;
        } else {
            r.l = merge(l, r.l);
            r.recalc();
            return r;
        }
    }

    void split(Node v, int x, Node l, Node r) {
        l = r = null;
        if (v == null) return;
        if (v.x < x) {
            split(v.r, x, v.r, r);
            l = v;
        } else {
            split(v.l, x, l, v.l);
            r = v;
        }
        v.recalc();
    }

    Node root;

    cartesianTree() {
        root = null;
    }

    void insert(int x) {
        Node l = null, r = null;
        split(root, x, l, r);
        root = merge(merge(l, new Node(x)), r);
    }

    void erase(int x) {
        Node l = null, m = null, r = null;
        split(root, x, l, m);
        split(root, x + 1, m, r);
        if (m == null || m.cnt != 1 || m.x != x) throw new NullPointerException();
        root = merge(l, r);
    }

    int size() {
        return root != null ? root.cnt : 0;
    }
}

void solve() throws IOException {
    cartesianTree tree = new cartesianTree();
    tree.insert(1);
    tree.insert(5);
    tree.insert(10);
    tree.insert(7);
    out.println(tree.size());
}
Tags no more treaps, treaps

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English saichandu6 2016-02-17 21:01:01 2596 Initial revision (published)