本文主要是介绍Codeforces 675D Tree Construction (splay)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
转自：https://blog.csdn.net/dreamon3/article/details/51436043
题意
往一个根为a[0]的二叉搜索树里面插数，每插一个数就输出他的父节点。
思路
根据二叉搜索树的性质，我们插进去一个数，他的父节点肯定是比他小的最大的和比他大的最小的数里面的两个，然后这两个节点找最深的那个就是他的父节点，我们可以给这些节点设置一个时间戳就能判断先后顺序了。
在找那两个节点的时候我是直接用的splay找的，实际上我们可以直接用两个set一个储存负数一个储存正数然后两个lower_bound找到这两个数，因为比赛的时候比较捉急调了挺长时间再加上我对我的迭代器操作水平不怎么自信就直接splay找了= =代码
#include <stdio.h> #include <string.h> #include <iostream> #include <algorithm> #include <vector> #include <queue> #include <stack> #include <set> #include <map> #include <string> #include <math.h> #include <stdlib.h> #include <time.h> using namespace std; typedef long long ll; #define MD 1000000007 const int INF = 0x3f3f3f3f; const double eps = 1e-8; const int maxn = 100005; int pre[maxn], key[maxn], ch[maxn][2], root, tot; //父节点，键值，左右孩子0左1右，根节点，节点数量 int n; void NewNode(int &r, int fa, int k) {r = ++tot;pre[r] = fa;key[r] = k;ch[r][0] = ch[r][1] = 0; } void Rotate(int x, int kind) //kind为1时右旋，为0左旋 {int y = pre[x];ch[y][!kind] = ch[x][kind];pre[ch[x][kind]] = y;if (pre[y])ch[pre[y]][ch[pre[y]][1]==y] = x;pre[x] = pre[y];ch[x][kind] = y;pre[y] = x; } void Splay(int r, int goal) {while (pre[r] != goal){if (pre[pre[r]] == goal) Rotate(r, ch[pre[r]][0]==r); //左儿子右旋右儿子左旋else{int y = pre[r];int kind = (ch[pre[y]][0] == y); //y是左儿子时kind是1，y是右儿子时kind是1if (ch[y][kind] == r){Rotate(r, !kind); //r和y左右不同时，之字形Rotate(r, kind);}else{Rotate(y, kind); //r和y是一条线时，一字型Rotate(r, kind);}}}if (goal == 0) root = r; } int Insert(int k) {int r = root;while (ch[r][key[r]<k]){//之前有过不再重复插入if (key[r] == k){Splay(r, 0);return 0;}r = ch[r][key[r]<k];}NewNode(ch[r][key[r]<k], r, k);Splay(ch[r][key[r]<k], 0);return 1; } int get_small(int x) {int temp = ch[x][0];if (temp == 0) return INF;while (ch[temp][1])temp = ch[temp][1];return key[temp]; } int get_big(int x) {int temp = ch[x][1];if (temp == 0) return INF;while (ch[temp][0])temp = ch[temp][0];return key[temp]; } map<int, int> mp;int main() {//freopen("H:\\in.txt","r",stdin);//freopen("H:\\out.txt","w",stdout);while (scanf("%d", &n) != EOF){root = tot = 0;int ans = 0;for (int i = 1; i <= n; i++){int num;scanf("%d", &num);mp[num] = i;if (i == 1){NewNode(root, 0, num);continue;}if (Insert(num) == 0) continue;int a = get_small(root);int b = get_big(root);if (mp[a] > mp[b]) printf("%d ", a);else printf("%d ", b);}}return 0; }
我的代码：
#include<bits/stdc++.h>
using namespace std;
#define dprintf if (debug) printf
#define rep(i, j, k) for (int i=j; i<k; i++)
const int N=100005, INF=0x7fffffff;
const int debug = 0;
int n, x;
struct Splay_Tree {struct Node {int key, son[2];} T[N];int fa[N], root, tot;void Rotate(int x, int kind) {int y=fa[x], z=fa[y];T[y].son[!kind]=T[x].son[kind], fa[T[x].son[kind]]=y;T[x].son[kind]=y, fa[y]=x;T[z].son[T[z].son[1]==y]=x, fa[x]=z;}void Splay(int x, int goal) {if(x==goal) return;while(fa[x]!=goal) {int y=fa[x], z=fa[y];int rx=T[y].son[0]==x, ry=T[z].son[0]==y;if(z==goal) Rotate(x, rx);else {if(rx==ry) Rotate(y, ry);else Rotate(x, rx);Rotate(x, ry);}}if(goal==0) root=x;}int Insert(int num){//dprintf("Insert %d\n", num);int rt = root;if (T[rt].key == num){Splay(rt, 0);return 0;}while (T[rt].son[T[rt].key<num]){//dprintf("rt = %d\n", T[rt].key);if (T[rt].key == num){Splay(rt, 0);return 0;}rt = T[rt].son[T[rt].key<num];}T[rt].son[T[rt].key<num] = ++tot;T[tot] = {num, 0, 0};fa[tot] = rt;//dprintf("before splay root = %d s0 = %d s1 = %d tot = %d\n", root, T[root].son[0], T[root].son[1], tot);Splay(tot, 0);//dprintf("after splay root = %d s0 = %d s1 = %d\n", root, T[root].son[0], T[root].son[1]);//dprintf("0 son0 = %d son1 = %d\n", T[0].son[0], T[0].son[1]);return 1;}int get_small(int rt){//dprintf("get_small rt = %d son0 = %d son1 = %d\n", T[rt].key, T[rt].son[0], T[rt].son[1]);int pos = T[rt].son[0];if (!pos) return INF;while (T[pos].son[1]) pos = T[pos].son[1];return T[pos].key;}int get_big(int rt){//dprintf("get_big rt = %d son0 = %d son1 = %d\n\n", T[rt].key, T[rt].son[0], T[rt].son[1]); int pos = T[rt].son[1];if (!pos) return INF;while (T[pos].son[0])pos = T[pos].son[0];return T[pos].key;}void init() {root = 1; tot = 1;//dprintf("T[1].key = %d\n", T[1].key);}void de(int x){dprintf("No. %d key = %d lson.key = %d rson.key = %d\n", x, T[x].key, T[T[x].son[0]].key, T[T[x].son[1]].key);}
};Splay_Tree hehe;map<int, int> mp;
int main() {scanf("%d", &n);hehe.init();scanf("%d", &x);hehe.T[1] = {x, 0, 0};mp[x] = 0;mp[INF] = -1;rep(i, 1, n){scanf("%d", &x);mp[x] = i;if (hehe.Insert(x)){//hehe.de(hehe.root); //hehe.de(0);int a = hehe.get_small(hehe.root);int b = hehe.get_big(hehe.root);//printf("a = %d b = %d\n mp[a] = %d mp[b] = %d\n ans = %d ", a, b, mp[a], mp[b], mp[a]>mp[b]? a:b);printf("%d ", mp[a]>mp[b]? a:b);}}return 0;
}
这篇关于Codeforces 675D Tree Construction (splay)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
