颓死了

佚名 6年前 (2019-05-10) 随笔 1704人围观抢沙发百度已收录

Binary Search Tree

实现功能：插入，删除，查询排名，求前驱，求后缀。

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

性质：对于每一个节点，左子树包含所有节点的值都小于这个节点的值，右子树包含所有节点的值都小于这个节点的值。

　　　then，从根节点中序遍历这棵树，可以得到一个有序序列。

没了，先学一下。

------------------------分割 line ---------------------------------------------------------------

感觉splay不错，熟悉一下，为以后的学习作个铺垫吧

代码是抄的，不完全，来自：

https://tiger0132.blog.luogu.org/slay-notes

不得不说代码风格很赞，容易理解且简短。

rotate朗朗上口啊！

 1 #include<iostream>
 2 #include<cstdio>
 3 using namespace std;
 4 const int N = 100001;
 5 int ch[N][2], par[N], size[N], val[N], cnt[N], q, ncnt;
 6 
 7 inline bool chk(int x) {
 8     return x == ch[par[x]][1];
 9 }
10 
11 void pushup(int x) {
12     size[x] = size[ch[x][0]] + size[ch[x][1]] + cnt[x];
13 }
14 
15 void rotate(int x) {
16     int k = chk(x), y = par[x], z = par[y], w = ch[x][k^1];
17     ch[y][k] = w; par[w] = y;
18     ch[z][chk(y)] = x; par[x] = z;
19     ch[x][k^1] = y; par[y] = x;
20     pushup(x); pushup(y);
21 }
22 
23 void splay(int x, int goal = 0) {
24     while(par[x] != goal) {
25         int y = par[x], z = par[y];
26         if(z != goal) {
27             if(chk(x) == chk(y)) rotate(y);
28             else rotate(x);
29         }
30         rotate(x);
31     }
32     if(!goal) root = x;
33 }
34 
35 void find(int x) {
36     if(!root) return;
37     int cur = root;
38     while(ch[cur][x > val[cur]] && x != val[cur]) {
39         cur = ch[cur][x > val[cur]];
40     }
41     splay(cur);
42 }
43 
44 void insert(int x) {
45     int cur = root, p = 0;
46     while(cur && x != val[cur]) {
47         p = cur;
48         cur = ch[cur][val[cur] < x];
49     }
50     if(cur) cnt[cur]++;
51     else {
52         cur = ++ncnt;
53         if(p) ch[p][x > val[p]] = cur;
54         ch[cur][0] = ch[cur][1] = 0;
55         val[cur] = x; par[cur] = p;
56         cnt[cur] = size[cur] = 1;
57     }
58     splay(cur);
59 }
60 
61 int main() {
62     int oper = 0, x = 0;
63 
64     scanf("%d", &q);
65     for(int i = 1; i <= q; ++i) {
66 
67     }
68 }