Блог пользователя saichandu6

Автор saichandu6, история, 9 лет назад, По-английски

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());
}
  • Проголосовать: нравится
  • -5
  • Проголосовать: не нравится

»
9 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится
Treap merge(Treap l, Treap r) {
	if (l == null) return r;
	if (r == null) return l;
	push(l);
	push(r);
	Treap t;
	if (l.priority > r.priority) {
		t = l;
		t.right = merge(l.right, r);
	} else {
		t = r;
		t.left = merge(l, t.left);
	}
	update(t);
	return t;
}

Treap[] split(Treap t, int key) {
	Treap[] res = new Treap[2];
	if (t == null) return res;
	push(t);
	if (key <= t.key) {
		Treap[] leftSplit = split(t.left, key);
		res[0] = leftSplit[0];
		res[1] = t;
		res[1].left = leftSplit[1];
	} else {
		Treap[] rightSplit = split(t.right, key);
		res[0] = t;
		res[0].right = rightSplit[0];
		res[1] = rightSplit[1];
	}
	update(res[0]);
	update(res[1]);
	return res;
}