数据结构-平衡二叉树的基本操作 （C++代码）

        Splay，以及所有基础操作

参考代码:

#ifndef LOCAL
	#include <bits/stdc++.h>
#endif
constexpr auto Inf = 0X3F3F3F3F;
typedef long long LL;
using namespace std;

namespace IO {
	inline LL read() {
		LL o = 0, f = 1; char c = getchar();
		while (c < '0' || c > '9') { if (c == '-') f = -1; c = getchar(); }
		while (c > '/' && c < ':') { o = o * 10 + c - '0'; c = getchar(); }
		return o * f;
	}
	inline char recd() {
		char o; while ((o = getchar()) != 'C' && o != 'D'); return o;
	}
}
using namespace IO;

const int SIZE = 1E4 + 7;

struct Node {
	int son[2], F, w, sze, p;
} Node[SIZE << 1]; int Root, Ind;

inline int which(int now) {
	return now == Node[Node[now].F].son[1];
}

inline void pushup(int now) {
	Node[now].sze = Node[Node[now].son[1]].sze + Node[Node[now].son[0]].sze + Node[now].p;
}

void Rot(int now) {
	int F = Node[now].F, FF = Node[F].F, w = which(now);
	Node[Node[now].son[!w]].F = F, Node[F].son[w] = Node[now].son[!w];
	Node[now].F = FF, Node[FF].son[which(F)] = now;
	Node[now].son[!w] = F, Node[F].F = now; pushup(F), pushup(now);
}

void splay(int now, int pos) {
	for (int F = Node[now].F; F != pos; Rot(now), F = Node[now].F)
		if (Node[F].F != pos)
			which(now) ^ which(F) ? Rot(now) : Rot(F);
	if (!pos) Root = now;
}

int Ins(int& now, int F, int w) {
	if (!now) {
		now = ++Ind; Node[now].w = w, Node[now].F = F, Node[now].sze = Node[now].p = 1; return now;
	}
	if (w == Node[now].w) { Node[now].p++, Node[now].sze++; return now; }
	int pos = Ins(Node[now].son[Node[now].w < w], now, w); pushup(now);
	return pos;
}

void Ins(int w) {
	splay(Ins(Root, 0, w), 0);
}

int Fnd(int w) {
	int pos = Root;
	while (Node[pos].w != w && Node[pos].son[Node[pos].w < w])
		pos = Node[pos].son[Node[pos].w < w];
	return pos;
}

int Pre(int w) {
	splay(Fnd(w), 0);
	if (Node[Root].w < w) return Root;
	int pos = Node[Root].son[0];
	while (Node[pos].son[1]) pos = Node[pos].son[1];
	return pos;
}

int Suf(int w) {
	splay(Fnd(w), 0);
	if (Node[Root].w > w) return Root;
	int pos = Node[Root].son[1];
	while (Node[pos].son[0]) pos = Node[pos].son[0];
	return pos;
}

void Rem(int w) {
	int pre = Pre(w), suf = Suf(w);
	splay(pre, 0), splay(suf, pre);
	int pos = Node[Node[Root].son[1]].son[0];
	if (Node[pos].p > 1) {
		Node[pos].p--, Node[pos].sze--; pushup(Node[Root].son[1]), pushup(Root); return;
	}
	Node[Node[Root].son[1]].son[0] = 0;
	pushup(Node[Root].son[1]), pushup(Root);
}

int Kth(int now, int K) {
	if (Node[Node[now].son[0]].sze + 1 <= K && K <= Node[Node[now].son[0]].sze + Node[now].p) return now;
	if (Node[Node[now].son[0]].sze >= K) return Kth(Node[now].son[0], K);
	return Kth(Node[now].son[1], K - Node[Node[now].son[0]].sze - Node[now].p);
}

int Kth(int w) {
	splay(Kth(Root, w), 0); return Node[Root].w;
}

int Rnk(int w) {
	splay(Fnd(w), 0); return Node[Node[Root].son[0]].sze;
}

int main() {
	Ins(Inf), Ins(-Inf);
	int N = read(), K = read(), w;
	for (int pos = 1; pos <= N; pos++) Ins(read());
	while (K--) {
		w = read();
		splay(Fnd(w), 0);
		printf("%d%c", Node[Root].w == w ? 1 : 0, !K ? '\n' : ' ');
	}
}