• 【平衡树】splay伸展树

    目录

    一.定义

    二.数据存储方式  && main函数

    三. insert

    四.splay

    五.rotate

    六.前驱后继

    七.delete

    八.查排名

    九.查排第几

    十.AC代码

    一.定义

     伸展树（Splay Tree）是一种自调整二叉搜索树，它通过不断进行伸展（splay）操作，将最近访问的节点移动到树的根节点，以提高对这些节点的访问效率。伸展树的主要特点是在插入、查找和删除操作时，都会执行伸展操作，使得最近访问的节点位于根节点，从而实现了一种局部性原理，即频繁访问的节点更容易被快速访问。

    伸展树的基本伸展操作有三种：

    1. 伸展到根（Splay to Root）：将某个节点x伸展到树的根节点，通过一系列旋转操作实现，使得x成为新的根节点。

    2. 伸展到左子树的最右节点（Splay to Right Child's Leftmost Descendant）：将某个节点x伸展到其左子树的最右节点，同样通过一系列旋转操作实现。

    3. 伸展到右子树的最左节点（Splay to Left Child's Rightmost Descendant）：将某个节点x伸展到其右子树的最左节点，同样通过一系列旋转操作实现。

    伸展树的操作包括插入、查找和删除。在每次操作之后，都会对相关的节点进行伸展，以保持树的平衡性和局部性原理。这种自调整性质使得伸展树在一般情况下表现出良好的性能，但最坏情况下的性能可能较差，因为它不保证平衡。

    总之，伸展树是一种简单而有效的自平衡二叉搜索树，适用于需要频繁访问最近使用节点的场景。在实际应用中，可以根据具体需求选择合适的自平衡数据结构，如AVL树、红黑树等。

    二.数据存储方式  && main函数

    1. struct node{
    2. 	int val,cnt; //它的值 ,值有几个 
    3. 	int fa,son[2]; // 它的father和它的两个son
    4. 	int siz; //它的子树个数 （即<=它的数有几个） 
    5. }tree[maxn];
    1. int main(){
    2. 	insert(-2147483647);
    3.     insert(+2147483647);
    4. 	scanf("%d",&n);
    5. 	int ops,x;
    6. 	for(int i=1;i<=n;i++){
    7. 		scanf("%d%d",&ops,&x);
    8. 		if(ops==1) insert(x);
    9. 		else if(ops==2) del(x);
    10. 		else if(ops==3) Find(x),printf("%d\n",tree[tree[root].son[0]].siz);
    11. 		else if(ops==4) printf("%d\n",kth(x+1));
    12. 		else if(ops==5) printf("%d\n",tree[pre(x)].val);
    13. 		else printf("%d\n",tree[nxt(x)].val);
    14. 	}
    15. 	return 0;
    16. }

    三. insert

    1. void insert(int x){
    2. 	int u=root,fa=0;
    3. 	while(u && tree[u].val!=x){
    4. 		fa=u;
    5. 		u=tree[u].son[x>tree[u].val];
    6. 	}
    7. 	//已经有这个数字 
    8. 	if(u){
    9. 		tree[u].cnt++;
    10. 	}else{
    11. 		u=++cnt;
    12. 		if(fa){
    13. 			tree[fa].son[x>tree[fa].val]=u;
    14. 		}
    15. 		tree[u].fa=fa;
    16. 		tree[u].son[0]=tree[u].son[1]=0;
    17. 		tree[u].val=x;
    18. 		tree[u].cnt=tree[u].siz=1;
    19. 	} 
    20. 	splay(u,0);
    21. }

    四.splay

    • 若共线要先转一下父节点，再转x
    • 不共线，转两下x即可
    • 重复上面操作，直到到达目标 
      1. void splay(int x,int goal){
      2. 	while(tree[x].fa!=goal){
      3. 		int fa=tree[x].fa,gfa=tree[fa].fa;
      4. 		if(gfa!=goal){
      5. 			//同ture意思是都为左孩子,异或为0；同false都为右孩子，异或为0 
      6. 			((tree[fa].son[0]==x)^(tree[gfa].son[0]==fa))==0 ? rotate(fa) : rotate(x);
      7. 		}	
      8. 		rotate(x);
      9. 	}
      10. 	if(goal==0) root=x;
      11. }

    五.rotate

    注意：这边使用了异或和判断孩子的功能，固左转和右转通用

    1. void updata(int x){
    2. 	tree[x].siz=tree[ tree[x].son[0] ].siz+
    3. 				tree[ tree[x].son[1] ].siz+
    4. 				tree[x].cnt;
    5. }
    6. void rotate(int x){
    7. 	//预处理 
    8. 	int fa=tree[x].fa,gfa=tree[fa].fa;
    9. 	int k=(tree[fa].son[1]==x); //左右孩子 
    10. 	//继承fa为gfa的孩子
    11. 	tree[gfa].son[ tree[gfa].son[1]==fa ] = x;
    12. 	tree[x].fa=gfa;
    13. 	//调整fa的son，即找人代替x为fa的k儿子 
    14. 	tree[fa].son[k]=tree[x].son[k^1];
    15. 	tree[ tree[x].son[k^1] ].fa = fa;
    16. 	//风水轮流转，爸爸成儿子
    17. 	tree[x].son[k^1]=fa;
    18. 	tree[fa].fa=x; 
    19. 	//fa和x子树有变动，要更新 
    20. 	updata(fa);
    21. 	updata(x);
    22. }

    六.前驱后继

    1. int pre(int x){
    2. 	Find(x);
    3. 	if(tree[root].valreturn root; //特判
    4. 	//左子树中找最右的点
    5. 	int u=tree[root].son[0];
    6. 	while(tree[u].son[1]) u=tree[u].son[1];
    7. 	return u; 
    8. }
    9. int nxt(int x){
    10. 	Find(x);
    11. 	if(tree[root].val>x) return root; //特判 
    12. 	//右子树中找最左的点
    13. 	int u=tree[root].son[1];
    14. 	while(tree[u].son[0]) u=tree[u].son[0];
    15. 	return u; 	
    16. }

    七.delete

    1. void del(int x){
    2. 	int p=pre(x),s=nxt(x);
    3. 	splay(p,0);
    4. 	splay(s,p);
    5. 	int del=tree[s].son[0];
    6.     if(tree[del].cnt>1){
    7.     	tree[del].cnt--;//存在多个这个数字，直接减去一个 
    8.         splay(del,0);
    9. 	}else{
    10. 		tree[s].son[0]=0;//清除掉节点 
    11. 	}   
    12. }

    八.查排名

    1. int kth(int x){
    2. 	int u=root;
    3. 	if(tree[u].sizreturn false;
    4. 	while(1){
    5. 		int y=tree[u].son[0];
    6. 	
    7. 		if(x>tree[y].siz+tree[u].cnt){	//排在u的后面 
    8. 			x-=tree[y].siz+tree[u].cnt;
    9. 			u=tree[u].son[1];
    10. 		}else if(tree[y].siz>=x){  //在u的前面 
    11. 			u=y;
    12. 		}else{
    13. 			return tree[u].val;
    14. 		}
    15. 	}
    16. }

    九.查排第几

    将其变成根，看看左子树有多少个即可

    十.AC代码

    1. #include
    2. using namespace std;
    3. const int maxn=1e5+5;
    4. int n;
    5. int root,cnt;
    6. struct node{
    7. 	int val,cnt; //它的值 ,值有几个 
    8. 	int fa,son[2]; // 它的father和它的两个son
    9. 	int siz; //它的子树个数 （即<=它的数有几个） 
    10. }tree[maxn];
    11. void updata(int x){
    12. 	tree[x].siz=tree[ tree[x].son[0] ].siz+
    13. 				tree[ tree[x].son[1] ].siz+
    14. 				tree[x].cnt;
    15. }
    16. void rotate(int x){
    17. 	//预处理 
    18. 	int fa=tree[x].fa,gfa=tree[fa].fa;
    19. 	int k=(tree[fa].son[1]==x); //左右孩子 
    20. 	//继承fa为gfa的孩子
    21. 	tree[gfa].son[ tree[gfa].son[1]==fa ] = x;
    22. 	tree[x].fa=gfa;
    23. 	//调整fa的son，即找人代替x为fa的k儿子 
    24. 	tree[fa].son[k]=tree[x].son[k^1];
    25. 	tree[ tree[x].son[k^1] ].fa = fa;
    26. 	//风水轮流转，爸爸成儿子
    27. 	tree[x].son[k^1]=fa;
    28. 	tree[fa].fa=x; 
    29. 	//fa和x子树有变动，要更新 
    30. 	updata(fa);
    31. 	updata(x);
    32. }
    33. void splay(int x,int goal){
    34. 	while(tree[x].fa!=goal){
    35. 		int fa=tree[x].fa,gfa=tree[fa].fa;
    36. 		if(gfa!=goal){
    37. 			//同ture意思是都为左孩子,异或为0；同false都为右孩子，异或为0 
    38. 			((tree[fa].son[0]==x)^(tree[gfa].son[0]==fa))==0 ? rotate(fa) : rotate(x);
    39. 		}	
    40. 		rotate(x);
    41. 	}
    42. 	if(goal==0) root=x;
    43. }
    44. void insert(int x){
    45. 	int u=root,fa=0;
    46. 	while(u && tree[u].val!=x){
    47. 		fa=u;
    48. 		u=tree[u].son[x>tree[u].val];
    49. 	}
    50. 	//已经有这个数字 
    51. 	if(u){
    52. 		tree[u].cnt++;
    53. 	}else{
    54. 		u=++cnt;
    55. 		if(fa){
    56. 			tree[fa].son[x>tree[fa].val]=u;
    57. 		}
    58. 		tree[u].fa=fa;
    59. 		tree[u].son[0]=tree[u].son[1]=0;
    60. 		tree[u].val=x;
    61. 		tree[u].cnt=tree[u].siz=1;
    62. 	} 
    63. 	splay(u,0);
    64. }
    65. void Find(int x){
    66. 	int u=root;
    67. 	if(!u) return;
    68. 	//若x不存在，则u一定有误差，但在pre or nxt函数中已经特判了 
    69. 	while(tree[u].son[x>tree[u].val] && x!=tree[u].val){
    70. 		u=tree[u].son[x>tree[u].val];
    71. 	}
    72. 	splay(u,0);
    73. }
    74. int pre(int x){
    75. 	Find(x);
    76. 	if(tree[root].valreturn root; //特判
    77. 	//左子树中找最右的点
    78. 	int u=tree[root].son[0];
    79. 	while(tree[u].son[1]) u=tree[u].son[1];
    80. 	return u; 
    81. }
    82. int nxt(int x){
    83. 	Find(x);
    84. 	if(tree[root].val>x) return root; //特判 
    85. 	//右子树中找最左的点
    86. 	int u=tree[root].son[1];
    87. 	while(tree[u].son[0]) u=tree[u].son[0];
    88. 	return u; 	
    89. }
    90. void del(int x){
    91. 	int p=pre(x),s=nxt(x);
    92. 	splay(p,0);
    93. 	splay(s,p);
    94. 	int del=tree[s].son[0];
    95.     if(tree[del].cnt>1){
    96.     	tree[del].cnt--;//存在多个这个数字，直接减去一个 
    97.         splay(del,0);
    98. 	}else{
    99. 		tree[s].son[0]=0;//清除掉节点 
    100. 	}   
    101. }
    102. int kth(int x){
    103. 	int u=root;
    104. 	if(tree[u].sizreturn false;
    105. 	while(1){
    106. 		int y=tree[u].son[0];
    107. 	
    108. 		if(x>tree[y].siz+tree[u].cnt){	//排在u的后面 
    109. 			x-=tree[y].siz+tree[u].cnt;
    110. 			u=tree[u].son[1];
    111. 		}else if(tree[y].siz>=x){  //在u的前面 
    112. 			u=y;
    113. 		}else{
    114. 			return tree[u].val;
    115. 		}
    116. 	}
    117. }
    118. int main(){
    119. 	insert(-2147483647);
    120.     insert(+2147483647);
    121. 	scanf("%d",&n);
    122. 	int ops,x;
    123. 	for(int i=1;i<=n;i++){
    124. 		scanf("%d%d",&ops,&x);
    125. 		if(ops==1) insert(x);
    126. 		else if(ops==2) del(x);
    127. 		else if(ops==3) Find(x),printf("%d\n",tree[tree[root].son[0]].siz);
    128. 		else if(ops==4) printf("%d\n",kth(x+1));
    129. 		else if(ops==5) printf("%d\n",tree[pre(x)].val);
    130. 		else printf("%d\n",tree[nxt(x)].val);
    131. 	}
    132. 	return 0;
    133. }

  • 相关阅读:
    JAVA【常见基础知识】
    springboot服务接入nacos注册中心
    VSCode：使用CMakeLists.txt构建C++项目
    一、Prometheus集成Grafana可视化监控安装详解
    C语言实现学生管理系统（顺序表版）
    安卓内部存储不需要申请权限，外部文件需要申请权限
    [OS]11.9.2023 中断
    渗透测试--实战若依ruoyi框架
    RabbitMQ系列【9】过期时间
    【开题报告】基于SSM的化工企业安全培训考试系统的设计与实现
  • 原文地址：https://blog.csdn.net/qq_49705495/article/details/133522495