直接貼代碼，純算法網(wǎng)上教程一大堆，我又不想費(fèi)勁巴拉地寫復(fù)雜度分析。

Splay:

#include <cstdio> #include <iostream> using namespace std; const int SIZE = 2e6 + 6; const int INF = 2147483647;namespace Splay { struct Infomat {int value, num; } cont[SIZE]; int parent[SIZE], child[SIZE][2]; int siz[SIZE]; int root, cnt;void updat(int v) {siz[v] = cont[v].num + siz[child[v][0]] + siz[child[v][1]]; }void rotat(int v) {int p = parent[v], is_rightchild = v == child[p][1];if (parent[p])child[parent[p]][p == child[parent[p]][1]] = v;parent[v] = parent[p];child[p][is_rightchild] = child[v][is_rightchild ^ 1];if (child[p][is_rightchild])parent[child[p][is_rightchild]] = p;child[v][is_rightchild ^ 1] = p;parent[p] = v;updat(p);updat(v); }void splay(int v, int goal, int& root) {int p, g;updat(v);while (parent[v] != goal) {p = parent[v], g = parent[p];if (g != goal && (v == child[p][1]) == (p == child[g][1]))rotat(p);rotat(v);}if (!goal)root = v; }int search_by_value(int vl, int& root) {int v = root;while (1) {if (cont[v].value == vl)break;if (cont[v].value < vl) {if (child[v][1])v = child[v][1];elsebreak;} else {if (child[v][0])v = child[v][0];elsebreak;}}return v; }int search_by_rank(int rk, int& root) {int v = root;while (1) {if (siz[child[v][0]] >= rk)v = child[v][0];else if (siz[child[v][0]] + cont[v].num < rk)rk -= siz[child[v][0]] + cont[v].num, v = child[v][1];elsebreak;}return v; }int get_prev_element(int v) {v = child[v][0];while (child[v][1])v = child[v][1];return v; }int get_succ_element(int v) {v = child[v][1];while (child[v][0])v = child[v][0];return v; }void insert_element(int vl, int& root) {if (!root) {int u = ++cnt;cont[u].value = vl, cont[u].num = 1;splay(u, 0, root);return;}int v = search_by_value(vl, root);if (cont[v].value == vl) {++cont[v].num;splay(v, 0, root);return;}int u = ++cnt;cont[u].value = vl, cont[u].num = 1;if (cont[v].value < vl) {parent[u] = v;child[v][1] = u;splay(u, 0, root);} else {parent[u] = v;child[v][0] = u;splay(u, 0, root);} }void delet_element(int vl, int& root) { // eraseint v = search_by_value(vl, root);--cont[v].num;splay(v, 0, root);if (!cont[v].num) {if (child[v][0]) {int u = get_prev_element(v);splay(u, v, root);child[u][1] = child[v][1];if (child[u][1])parent[child[u][1]] = u;parent[u] = 0;splay(u, 0, root);} else {int u = child[v][1];if (u) {parent[u] = 0;splay(u, 0, root);} else {root = 0;}}} }int get_rank(int vl, int& root) {int v = search_by_value(vl, root);splay(v, 0, root);if (cont[v].value >= vl)return siz[child[v][0]] + 1;if (!child[v][1])return siz[root] + 1;int u = get_succ_element(v);splay(u, 0, root);return siz[child[u][0]] + 1; }int get_value(int rk, int& root) {int v = search_by_rank(rk, root);splay(v, 0, root);return cont[v].value; }int a_redundant_operat(int vl, int& root) {if (!root)return -INF;int v = search_by_value(vl, root);splay(v, 0, root);if (cont[v].value < vl)return cont[v].value;if (!child[v][0])return -INF;int u = get_prev_element(v);splay(u, 0, root);return cont[u].value; }int lower_bound(int vl, int& root) {if (!root)return INF;int v = search_by_value(vl, root);splay(v, 0, root);return cont[v].value; }int upper_bound(int vl, int& root) {if (!root)return INF;int v = search_by_value(vl, root);splay(v, 0, root);if (cont[v].value > vl)return cont[v].value;if (!child[v][1])return INF;int u = get_succ_element(v);splay(u, 0, root);return cont[u].value; } } // namespace Splayusing namespace Splay;namespace Splay_for_array { int root, cnt, parent[N], child[N][2], reverse_flag[N], siz[N];void refresh_flag(int v) {if (reverse_flag[v]) {if (child[v][0] != -1)reverse_flag[child[v][0]] ^= 1;if (child[v][1] != -1)reverse_flag[child[v][1]] ^= 1;swap(child[v][0], child[v][1]);reverse_flag[v] = 0;} }void updat(int v) { siz[v] = siz[child[v][0]] + siz[child[v][1]] + 1; }void rotat(int v) {refresh_flag(parent[v]);refresh_flag(v);int p = parent[v], w = (v == child[p][1]);if (parent[p] != -1)child[parent[p]][p == child[parent[p]][1]] = v;parent[v] = parent[p];child[p][w] = child[v][w ^ 1];if (child[p][w] != -1)parent[child[p][w]] = p;parent[p] = v;child[v][w ^ 1] = p;updat(p);updat(v); }void splay(int v, int gl) {int p, g;updat(v);while (parent[v] != gl) {p = parent[v];g = parent[p];refresh_flag(g);refresh_flag(p);if (g != gl && (v == child[p][1]) == (p == child[g][1]))rotat(p);rotat(v);}if (gl == -1)root = v; }int build(int l, int r, int p) {if (l > r)return -1;int mid = (l + r) >> 1;siz[mid] = r - l + 1;parent[mid] = p;child[mid][0] = build(l, mid - 1, mid);child[mid][1] = build(mid + 1, r, mid);return mid; }void init(int l, int r) {cnt = 0;root = build(l, r, -1); }int search_by_rank(int x) {int v = root;refresh_flag(v);while (x != siz[child[v][0]] + 1) {if (siz[child[v][0]] >= x)v = child[v][0];else {x -= siz[child[v][0]] + 1;v = child[v][1];}refresh_flag(v);}return v; }void reverse_interv(int x, int y) {x = search_by_rank(x);y = search_by_rank(y + 2);splay(x, -1);splay(y, x);reverse_flag[child[y][0]] ^= 1; }void trav_interv(int v, int x, int y) {refresh_flag(v);if (child[v][0] != -1)trav_interv(child[v][0], x, y);if (x <= v && v <= y)printf("%d ", v);if (child[v][1] != -1)trav_interv(child[v][1], x, y); }void print_for_debug(int l, int r) {trav_interv(root, l, r);printf("\n"); } } // namespace Splay_for_arrayint main() {int n, m, last = 0, ans = 0;scanf("%d%d", &n, &m);for (int i = 0; i < n; i++) {int x;scanf("%d", &x);insert_element(x, root);}for (int i = 0; i < m; i++) {int opt, x;scanf("%d%d", &opt, &x);x ^= last;if (opt == 1) {insert_element(x, root);}if (opt == 2) {delet_element(x, root);}if (opt == 3) {ans ^= last = get_rank(x, root);}if (opt == 4) {ans ^= last = get_value(x, root);}if (opt == 5) {ans ^= last = a_redundant_operat(x, root);}if (opt == 6) {ans ^= last = upper_bound(x, root);}}printf("%d\n", ans);return 0; }

AVL

#include <cstdio> #include <iostream> using namespace std;class Node { public:int data, hight;int num, siz;Node* left_child;Node* right_child;Node(int a = 0): data(a), hight(1), num(1), siz(1), left_child(NULL), right_child(NULL) {}~Node() {} };Node* root;int get_siz(Node* p) {if (p == NULL)return 0;return p->siz; }int get_hight(Node* p) {if (p == NULL)return 0;return p->hight; }void updat(Node*& p) {p->siz = get_siz(p->left_child) + get_siz(p->right_child) + p->num;p->hight = max(get_hight(p->left_child), get_hight(p->right_child)) + 1; } //左旋，這里我忘了是zig還是zag了 void zig(Node*& p) {Node* q;q = p->left_child;p->left_child = q->right_child;q->right_child = p;updat(p);updat(q);p = q; }void zag(Node*& p) {Node* q;q = p->right_child;p->right_child = q->left_child;q->left_child = p;updat(p);updat(q);p = q; }void zigzag(Node*& p) {zag(p->left_child);zig(p); }void zagzig(Node*& p) {zig(p->right_child);zag(p); }void rebuild_34(Node*& p) {// 3,4-重構(gòu)//這種實(shí)現(xiàn)非常繁瑣，希望有人能給他簡(jiǎn)化一下Node *a, *b, *c;Node *A, *B, *C, *D;if (get_hight(p->left_child) > get_hight(p->right_child)) {c = p;D = c->right_child;if (get_hight(p->left_child->left_child) >get_hight(p->left_child->right_child))b = p->left_child, a = b->left_child, A = a->left_child,B = a->right_child, C = b->right_child;elsea = p->left_child, b = a->right_child, A = a->left_child,B = b->left_child, C = b->right_child;} else {a = p;A = a->left_child;if (get_hight(p->right_child->left_child) >get_hight(p->right_child->right_child))c = p->right_child, b = c->left_child, B = b->left_child,C = b->right_child, D = c->right_child;elseb = p->right_child, c = b->right_child, B = b->left_child,C = c->left_child, D = c->right_child;}p = b;b->left_child = a;b->right_child = c;a->left_child = A;a->right_child = B;c->left_child = C;c->right_child = D;updat(a);updat(c);updat(b); }void insert_element(Node*& p, int x) {if (p == NULL) {p = new Node(x);return;}if (p->data == x) {++(p->num);updat(p);return;}if (p->data > x) {insert_element(p->left_child, x), updat(p);if (get_hight(p->left_child) - get_hight(p->right_child) == 2) {/*可以替換下面單個(gè)語句if (x < p->left_child->data)zig(p);elsezigzag(p);*/rebuild_34(p);}} else {insert_element(p->right_child, x), updat(p);if (get_hight(p->right_child) - get_hight(p->left_child) == 2) {/*if (x > p->right_child->data)zag(p);elsezagzig(p);*/rebuild_34(p);}}updat(p); }void delet_element(Node*& p, int x) {if (p == NULL)return;if (p->data > x) {delet_element(p->left_child, x), updat(p);if (get_hight(p->right_child) - get_hight(p->left_child) == 2) {if (get_hight(p->right_child->right_child) >=get_hight(p->right_child->left_child))zag(p);elsezagzig(p);}} else if (p->data < x) {delet_element(p->right_child, x), updat(p);if (get_hight(p->left_child) - get_hight(p->right_child) == 2) {if (get_hight(p->left_child->left_child) >=get_hight(p->left_child->right_child))zig(p);elsezigzag(p);}} else {if (p->num > 1) {--(p->num);updat(p);return;}if (p->left_child && p->right_child) {Node* q = p->right_child;while (q->left_child)q = q->left_child;p->num = q->num;p->data = q->data, q->num = 0;delet_element(p->right_child, q->data);updat(p);if (get_hight(p->left_child) - get_hight(p->right_child) == 2) {if (get_hight(p->left_child->left_child) >=get_hight(p->left_child->right_child))zig(p);elsezigzag(p);}} else {Node* q = p;if (p->left_child)p = p->left_child;else if (p->right_child)p = p->right_child;elsep = NULL;delete q;q = NULL;}}if (p)updat(p); }int search_by_value(Node* p, int val) {if (p == NULL)return 1;if (p->data == val)return get_siz(p->left_child) + 1;if (p->data > val)return search_by_value(p->left_child, val);return search_by_value(p->right_child, val) + get_siz(p->left_child) +p->num; }int search_by_rank(Node* p, int rank) {if (get_siz(p->left_child) >= rank)return search_by_rank(p->left_child, rank);if (get_siz(p->left_child) + p->num >= rank)return p->data;return search_by_rank(p->right_child,rank - get_siz(p->left_child) - p->num); }int get_lower(int val) {Node* p = root;int ans = -2147483648;while (p) {if (p->data == val) {if (p->left_child) {p = p->left_child;while (p->right_child)p = p->right_child;ans = p->data;}break;}if (p->data < val && p->data > ans)ans = p->data;p = p->data < val ? p->right_child : p->left_child;}return ans; }int get_upper(int val) {Node* p = root;int ans = 2147483647;while (p) {if (p->data == val) {if (p->right_child) {p = p->right_child;while (p->left_child)p = p->left_child;ans = p->data;}break;}if (p->data > val && p->data < ans)ans = p->data;p = p->data < val ? p->right_child : p->left_child;}return ans; }void clear(Node*& p) {if (p->left_child)clear(p->left_child);if (p->right_child)clear(p->right_child);delete (p); }int main() {int n;scanf("%d", &n);for (int i = 0; i < n; i++) {int opt, x;scanf("%d%d", &opt, &x);switch (opt) {case 1:insert_element(root, x);break;case 2:delet_element(root, x);break;case 3:printf("%d\n", search_by_value(root, x));break;case 4:printf("%d\n", search_by_rank(root, x));break;case 5:printf("%d\n", get_lower(x));break;case 6:printf("%d\n", get_upper(x));break;}}clear(root);return 0; }

B樹

未完待續(xù)

總結(jié)

以上是生活随笔為你收集整理的【】平衡树！的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。