BBST implementation

treap.cpp

#include <cstdint>
#include <cstdio>
#include <initializer_list>

// Xoshiro256** 32bit
static uint64_t rotl(const uint64_t x, int k) {
	return (x << k) | (x >> (64 - k));
}
static uint32_t rng() {
	static uint64_t s[4] = {123456789, 987654321, 999778844, 99999999};
	const uint64_t ret = rotl(s[1] * 5, 7) * 9;
	const uint64_t t = s[1] << 17;
	s[2] ^= s[0]; s[3] ^= s[1]; s[1] ^= s[2]; s[0] ^= s[3];
	s[2] ^= t; s[3] = rotl(s[3], 45);
	return ret >> 32;
}

// Treap
struct node {
	node *l, *r;
	int val;
	uint32_t t;

	node() = default;
	node(int v) : val(v) {
		l = r = nullptr;
		t = rng();
	}
	~node() {
		delete l;
		delete r;
	}
};
typedef node *pnode;

pnode treap_merge(pnode left, pnode right) {
	if (!left) return right;
	if (!right) return left;
	if (left->t > right->t) {
		left->r = treap_merge(left->r, right);
		return left;
	}
	right->l = treap_merge(left, right->l);
	return right;
}

void treap_split(pnode root, int k, pnode &left, pnode &right) {
	if (!root) {
		left = nullptr;
		right = nullptr;
	} else if (root->val < k) {
		treap_split(root->r, k, root->r, right);
		left = root;
	} else {
		treap_split(root->l, k, left, root->l);
		right = root;
	}
}

void printAll(pnode a) {
	if (!a) return;
	printAll(a->l);
	printf("%d ", a->val);
	printAll(a->r);
}

class Treap {
	pnode root = nullptr;
public:
	void insert(int p) {
		pnode left, right;
		treap_split(root, p, left, right);
		root = treap_merge(treap_merge(left, new node(p)), right);
	}

	void remove(int p) {
		pnode left, mid, right;
		treap_split(root, p, left, mid);
		treap_split(mid, p + 1, mid, right);
		root = treap_merge(left, right);
		delete mid;
	}

	void print() {
		printf("[ ");
		printAll(root);
		printf("]");
	}
};

int main() {
	Treap tr;

	for (const auto& x : {1, 9, 3, 4, 7, 6, 8, 2}) tr.insert(x);
	for (const auto& x : {7, 3}) tr.remove(x);
	tr.print(); // [ 1 2 4 6 8 9 ]
}