首页 > 其他分享 >红黑树学习笔记

红黑树学习笔记

时间：2022-10-22 10:03:29浏览次数：80  
标签：int tr 笔记 son 学习 红黑树 id 节点 col

代码的红黑树部分138行。

本文的图中，红/黑点代表红/黑色节点，蓝点代表无关点（或者子树），绿点代表无所谓颜色的点。

红黑树的性质：

  1. 是一颗二叉搜索树
  2. 每个节点是红色或者黑色
  3. 根和NULL节点是黑色节点
  4. 红色节点的儿子一定是黑色节点
  5. 根到每个NULL节点的路径上的黑色节点个数相等（叫做黑高度）

根据这些性质可以推出，树深度小于等于二倍黑高度，是\(O(\log n)\)级别

旋转

图中从左到右是右旋，从右到左是左旋，不细说了。

旋转

inline void rotate(int x) {
	static int y,z,k,w;
	y=tr[x].fa,z=tr[y].fa,k=tr[y].son[1]==x,w=tr[x].son[k^1];
	if(w)tr[w].fa=y;
	tr[y].son[k]=w,tr[x].son[k^1]=y,tr[z].son[tr[z].son[1]==y]=x,tr[y].fa=x,tr[x].fa=z;
	push_up(y),push_up(x);
}

插入

当原树为空时，直接将根节点赋值为一个新黑色节点即可

其余情况考虑插入一个红色节点，这样就只有可能和性质4发生冲突（即有可能出现双红节点）

之后对这个节点进行双红修正即可。

inline int push(int x) {
	if(!rt)return rt=newnode(x,0);
	for(int i=rt,id=0; 1; i=tr[i].son[id]) {
		++tr[i].siz;
		if(tr[i].val==x) //值相同的点合并
			return ++tr[i].cnt,i;
		id=tr[i].val<x;
		if(!tr[i].son[id]) {
			tr[i].son[id]=newnode(x,1),tr[tr[i].son[id]].fa=i;
			solve_double_red(tr[i].son[id]);
			return tr[i].son[id];
		}
	}
}

双红修正

用一个函数solve_double_red(x)来解决

这个函数的意义是：\(x\)的子树内已经修正完毕，但\(x,fa(x)\)有可能是双红，需要接着修正。

首先当\(x\)为根或\(x\)的父亲为根时，直接将根节点染为黑色即可。

记得在函数里判断不是双红的情况（直接return）

记函数\(id(x)\)：\(id(x)=0\)时\(x\)是其父亲的左儿子，\(id(x)=1\)时\(x\)是其父亲的右儿子。

设现在要修正的节点为\(x\)，其父亲节点为\(y\)，\(y\)的节点（\(x\)的祖父）为\(z\)，\(z\)的另一个儿子（\(x\)的叔父）为\(w\)

当\(w\)为黑色节点（或为空）时：（可以发现这两种都是以中间值为根）

  1. 若\(id(x)=id(y)\)，那么rotate(y)之后把\(y\)染成黑色，\(z\)染成红色

  2. 若\(id(x)\not=id(y)\)，那么rotate(x),swap(x,y)可以转换为情况\(1\)

双红修正

当\(w\)为红色节点时：将\(y,w\)染为黑色，\(z\)染为红色，递归solve_double_red(z)即可。

双红修正（2）

void solve_double_red(int x) {
	if(x==rt||tr[x].fa==rt) {
		tr[rt].col=0;
		return;
	}
	if(!tr[tr[x].fa].col) return;//判断双红
	static int y,z,w;
	y=tr[x].fa,z=tr[y].fa,w=tr[z].son[tr[z].son[0]==y];
	if(!tr[w].col) {//w是黑点
		if((tr[y].son[1]==x)^(tr[z].son[1]==y))//id(x)!=id(y)
			rotate(x),swap(x,y);
		rotate(y),tr[z].col=1,tr[y].col=0;//id(x)=id(y)
		return;
	}
	tr[y].col=tr[w].col=0,tr[z].col=1;
	return solve_double_red(z);//尾递归优化
}

删除

首先肯定要找到删除的数对应的节点\(x\)

如果\(x\)是唯一的点，直接删除后将根赋值为\(0\)，其余情况下：

找到当前数的真后继对应的节点\(y\)，可以交换\(x,y\)的数据，转化为删除节点\(y\)

这样我们删除的节点一定在最后一层。

考虑删除一个在最后一层的节点\(x\)：

若\(x\)为红色节点，可以直接删除，不会和任何性质有矛盾

若\(x\)为黑色节点，删除后会和性质5矛盾，所以删除前要用双黑修正。

inline void pop(int x) {
	int i=rt;
	for(; tr[i].val^x&&tr[i].son[tr[i].val<x]; i=tr[i].son[tr[i].val<x])
		--tr[i].siz;//先找到值x对应的点
	--tr[i].siz,--tr[i].cnt;
	if(tr[i].cnt) return;
	if(i==rt&&!tr[i].son[0]&&!tr[i].son[1])
		return rt=0,Q.push(i);//删后是空树
	for(x=i; tr[x].son[0]||tr[x].son[1]; ) {//找真后继
		static int y;
		if(!tr[x].son[0]) y=tr[x].son[1];
		else if(!tr[x].son[1]) y=tr[x].son[0];
		else for(y=tr[x].son[1]; tr[y].son[0]; y=tr[y].son[0]);
		swap(tr[x].val,tr[y].val),swap(tr[x].cnt,tr[y].cnt);
		x=y;//可以发现这样删除之后仍满足二叉搜索树的性质
	}
	Q.push(x);//节点回收
	if(!tr[x].col) solve_double_black(x);//删除的节点是黑色，要进行双黑修正
	if(tr[x].fa)tr[tr[x].fa].son[tr[tr[x].fa].son[1]==x]=0;
	for(i=tr[x].fa; i; i=tr[i].fa) push_up(i);//记得push_up
}

双黑修正

用一个函数solve_double_black(x)来解决

这个函数的意义是：\(x\)的子树内的黑高度相等，但\(x\)子树内的黑高度比它兄弟子树内的黑高度小\(1\)，需要接着修正。

当\(x\)为根时（整棵树的黑高度都减去\(1\)），就直接返回。

设\(y\)为\(x\)的父亲，\(z\)为\(x\)的兄弟。

当\(z\)为红色节点：rotate(z)并交换\(z,y\)的颜色，可以转换为\(z\)为黑的情况。
双黑修正

当\(z\)为黑色节点且存在红色儿子\(w\)：（还是中间值做根）

  1. 若\(id(w)=id(z)\)，那么rotate(z)之后把\(z\)染成\(y\)的颜色，\(y,w\)染成黑色
    双黑修正（2）
  2. 若\(id(w)\not=id(z)\)，那么rotate(w),rotate(w)后把\(w\)染成\(y\)的颜色，\(y,z\)染成黑色
    双黑修正（3）

当\(z\)为黑色节点且无红色儿子：

  1. 若\(y\)为红色，染红\(z\)，染黑\(y\)就行。
    双黑修正（4）
  2. 若\(y\)为黑色，染红\(z\)，递归solve_double_black(y)
    双黑修正（5）
void solve_double_black(int x) {
	if(x==rt) {//判根
		tr[x].col=0;
		return;
	}
	static int y,z,w,k;
	y=tr[x].fa,k=tr[y].son[0]==x,z=tr[y].son[k];
	if(tr[z].col) {//z为红点
		tr[z].col=0,tr[y].col=1,rotate(z);
		y=tr[x].fa,k=tr[y].son[0]==x,z=tr[y].son[k];//旋转后要更新值
	}
	w=tr[z].son[k];//优先选id相同的红节点
	if(tr[w].col) {
		tr[z].col=tr[y].col,tr[w].col=tr[y].col=0;
		return rotate(z);
	}
	w=tr[z].son[k^1];
	if(tr[w].col) {
		tr[w].col=tr[y].col,tr[z].col=tr[y].col=0;
		return rotate(w),rotate(w);
	}
	if(tr[y].col) {
		tr[y].col=0,tr[z].col=1;
		return;
	}
	return tr[z].col=1,solve_double_black(y);
}

剩下的部分其实和普通的二叉查找树是一样的，直接放P6136 【模板】普通平衡树（数据加强版）
完整代码吧：（最慢的点512ms）

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1100005;
inline int read() {
	static int x,c=getchar(),f;
	for(f=1; c<=47||c>=58; c=getchar())f=f&&(c^45);
	for(x=0; c>=48&&c<=57; c=getchar())x=(x<<3)+(x<<1)+(c&15);
	return f?x:-x;
}
struct node {
	int fa,son[2],siz,cnt,val,col;
} tr[MAXN];
queue<int>Q;
int tcnt;
class RBT {
	public:	
		int rt;
		inline int newnode(int v,int c) {
			static int x;
			if(Q.empty()) x=++tcnt;
			else x=Q.front(),Q.pop();
			tr[x]={0,0,0,1,1,v,c};
			return x;
		}
		inline void push_up(int x) {
			tr[x].siz=tr[tr[x].son[0]].siz+tr[tr[x].son[1]].siz+tr[x].cnt;
		}
		inline void rotate(int x) {
			static int y,z,k,w;
			y=tr[x].fa,z=tr[y].fa,k=tr[y].son[1]==x,w=tr[x].son[k^1];
			if(w)tr[w].fa=y;
			if(z)tr[z].son[tr[z].son[1]==y]=x;
			else rt=x;
			tr[y].son[k]=w,tr[x].son[k^1]=y,tr[y].fa=x,tr[x].fa=z;
			push_up(y),push_up(x);
		}
		void solve_double_red(int x) {
			if(x==rt||tr[x].fa==rt) {
				tr[rt].col=0;
				return;
			}
			if(!tr[tr[x].fa].col) return;
			static int y,z,w;
			y=tr[x].fa,z=tr[y].fa,w=tr[z].son[tr[z].son[0]==y];
			if(!tr[w].col) {
				if((tr[y].son[1]==x)^(tr[z].son[1]==y))
					rotate(x),swap(x,y);
				rotate(y),tr[z].col=1,tr[y].col=0;
				return;
			}
			tr[y].col=tr[w].col=0,tr[z].col=1;
			return solve_double_red(z);
		}
		inline int push(int x) {
			if(!rt)return rt=newnode(x,0);
			for(int i=rt,id=0; 1; i=tr[i].son[id]) {
				++tr[i].siz;
				if(tr[i].val==x) 
					return ++tr[i].cnt,i;
				id=tr[i].val<x;
				if(!tr[i].son[id]) {
					tr[i].son[id]=newnode(x,1),tr[tr[i].son[id]].fa=i;
					solve_double_red(tr[i].son[id]);
					return tr[i].son[id];
				}
			}
		}
		inline int rnk(int x) {
			int res=1,i=rt;
			while(i)
				if(tr[i].val==x) return res+tr[tr[i].son[0]].siz;
				else if(x<tr[i].val)i=tr[i].son[0];
				else res+=tr[tr[i].son[0]].siz+tr[i].cnt,i=tr[i].son[1];
			return res;
		}
		inline int kth(int x) {
			int res=0,i=rt;
			while(1)
				if(res+tr[tr[i].son[0]].siz<x&&x<=res+tr[tr[i].son[0]].siz+tr[i].cnt)
					return tr[i].val;
				else if(x<=res+tr[tr[i].son[0]].siz)
					i=tr[i].son[0];
				else res+=tr[tr[i].son[0]].siz+tr[i].cnt,i=tr[i].son[1];
		}
		inline int pre(int x) {
			int res=0,i=rt;
			while(i)
				if(tr[i].val>=x)i=tr[i].son[0];
				else res=tr[i].val,i=tr[i].son[1];
			return res;
		}
		inline int suf(int x) {
			int res=0,i=rt;
			while(i)
				if(tr[i].val<=x)i=tr[i].son[1];
				else res=tr[i].val,i=tr[i].son[0];
			return res;
		}
		void solve_double_black(int x) {
			if(x==rt) {
				tr[x].col=0;
				return;
			}
			static int y,z,w,k;
			y=tr[x].fa,k=tr[y].son[0]==x,z=tr[y].son[k];
			if(tr[z].col) {
				tr[z].col=0,tr[y].col=1,rotate(z);
				y=tr[x].fa,k=tr[y].son[0]==x,z=tr[y].son[k];
			}
			w=tr[z].son[k];
			if(tr[w].col) {
				tr[z].col=tr[y].col,tr[w].col=tr[y].col=0;
				return rotate(z);
			}
			w=tr[z].son[k^1];
			if(tr[w].col) {
				tr[w].col=tr[y].col,tr[z].col=tr[y].col=0;
				return rotate(w),rotate(w);
			}
			if(tr[y].col) {
				tr[y].col=0,tr[z].col=1;
				return;
			}
			return tr[z].col=1,solve_double_black(y);
		}
		inline void pop(int x) {
			int i=rt;
			for(; tr[i].val^x&&tr[i].son[tr[i].val<x]; i=tr[i].son[tr[i].val<x])
				--tr[i].siz;
			--tr[i].siz,--tr[i].cnt;
			if(tr[i].cnt) return;
			if(i==rt&&!tr[i].son[0]&&!tr[i].son[1])
				return rt=0,Q.push(i);
			for(x=i; tr[x].son[0]||tr[x].son[1]; ) {
				static int y;
				if(!tr[x].son[0]) y=tr[x].son[1];
				else if(!tr[x].son[1]) y=tr[x].son[0];
				else for(y=tr[x].son[1]; tr[y].son[0]; y=tr[y].son[0]);
				swap(tr[x].val,tr[y].val),swap(tr[x].cnt,tr[y].cnt);
				x=y;
			}
			Q.push(x);
			if(!tr[x].col) solve_double_black(x);
			if(tr[x].fa)tr[tr[x].fa].son[tr[tr[x].fa].son[1]==x]=0;
			for(i=tr[x].fa; i; i=tr[i].fa) push_up(i);
		}
} T;
int n,m,lst,ans;
int main() {
	n=read(),m=read();
	for(int i=1; i<=n; ++i)T.push(read());
	for(int i=1,op,x; i<=m; ++i) {
		op=read(),x=read()^lst;
		if(op==1)T.push(x);
		else if(op==2)T.pop(x);
		else if(op==3)lst=T.rnk(x),ans^=lst;
		else if(op==4)lst=T.kth(x),ans^=lst;
		else if(op==5)lst=T.pre(x),ans^=lst;
		else if(op==6)lst=T.suf(x),ans^=lst;
	}
	printf("%d\n",ans);
	return 0;
}

标签：int,tr,笔记,son,学习,红黑树,id,节点,col
From： https://www.cnblogs.com/mod998244353/p/16815409.html

相关文章

  • 2022-10-21 看李晓军视频笔记不测而测第一讲
    http://www.365chanlun.com/live/playBack_45_2151.html还是2022-07-26这一节课日线笔，可能是30分钟线段，可能是5分钟走势，一定是1分钟走势。现在是只有日线一笔，所以之后的......
  • 20201318李兴昕学习笔记八
    第五章：定时器及时钟服务知识点归纳总结：本章讨论了定时器和定时器服务；介绍了硬件定时器的原理和基于Intelx86的PC中的硬件定时器；讲解了CPU操作和中断处理；描述了Linux......
  • 珂朵莉树学习笔记
    0x00前言0x01关于其命名  最开始出现在CodeforcesRound#449(Div.1)C题上，这位珂学家在题解中用了一种玄学的数据结构解题，开始命名为ODT树（OldDriverTree，老......
  • Newtonsoft.Json笔记 -JToken、JObject、JArray详解
    在原来解析json数据是，一般都是用反序列化来实现json数据的解读，这需要首先知道json数据的结构并且建立相应的类才能反序列化，一旦遇到动态的json数据，这种方法就不使用。为了......
  • Vue笔记3 计算属性 ES6语法、作用域闭包var/let/const、v-if/v-else/v-else-if 、v-sh
              闭包                    事件冒泡 阻止默认事件        key="username"......
  • Python学习三天计划-2
    一、函数函数：是组织好的，可重复使用的，用来实现特定功能的代码段。优点：可供重复利用的代码段提高程序的复用性减少重复性代码提高开发效率1.定义deffunc1():......
  • JodeTime的笔记
    Jode-TimeJode-Time介绍任何企业应用程序都需要处理时间问题。应用程序需要知道当前的时间点和下一个时间点，有时它们还必须计算这两个时间点之间的路径。使用JDK完......
  • 2022-2023-1 20221312 《计算机基础与程序设计》第八周学习总结
    作业信息班级链接：https://edu.cnblogs.com/campus/besti/2022-2023-1-CFAP作业要求：https://www.cnblogs.com/rocedu/p/9577842.html#WEEK08作业目标：面向对象，面向过程，顶点，......
  • Pytorch学习笔记
    两大强大的工具函数：1.dir()，打开一个包，输出包内含有的其他子类2.help()，帮助文档1help(torch.cuda.is_available)2Helponfunctionis_availableinmoduletorch.cuda......
  • 正则表达式笔记
    几次想学但是都没学会……现在作业要用就还是硬着头皮学一下吧部分材料源于这个我一开始还不太能理解这怎么配这么多stars，后面才发现stars给的是这个基本语法开始和结......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99