手撕红黑树

1. 红黑树的使用场景只有两种：
   1.<key,vlaue> 用于查找
   2.利用中序遍历-是顺序的：1）进程调度的cfs(用红黑树存储进程的集合，将调度的时间作为key值，每次从左下角的树开始查找）；2）内存管理 （每申请一块内存将其添加到红黑树，申请的内存为首地址+大小）
2. 红黑树的性质
   1.每个结点是红或黑
   2.根结点是黑色的
   3.每个叶子结点是黑色的
   4.如果一个结点是红的，则它的两个儿子都是黑的
   5.对每个结点，从该结点到其子孙结点的所有路径上包含相同数目的黑结点

#define RED 0;
#define BALCK 1;
typedef int KEY_TYPE;
int KEY_COMPARE(KEY_TYPE a,KEY_TYPE b)
{
//红黑树结点比较，后续可自行实现，目前代码里的还是使用的>比较
}
typedef struct _rbtree_node {
	unsigned char color;
	struct _rbtree_node *left;
	struct _rbtree_node *right;
	struct _rbtree_node *parent;
	KEY_TYPE key;
	void *value;
} rbtree_node;

typedf struct _rbtree{
	rbtree_node * root;
	rbtree_node * nil;
}rbtree;

//左旋
void _left_roate(rbtree *T,rbtree_node *x)
{
	rbtree_node * y= x->right;
	
	x->right = y->left;
	if(y->left != T->nil)
	{
		y->left ->parent = x;
	}

	y->parent = x->parent;
	if(x->parent ==T-> nil)
	{
		T->root = y;
	}else if (x->parent->left == x)
	{
		x->parent->left = y;
	}else if (x->parent->right == x)
	{
		x->parent->right = y;
	}
	
	x->parent = y;
	y->left= x;
}

//右旋
void _right_rotate(rbtree *T,rbtree_node *y)
{
	rbtree_node *x=y->left;

    y->left = x->right;
    if(x->right != T->nil)
    {
  	  x->right->parent = y;
    }
	x->parent = y ->parent;
	if(y->parent == T->nil)
	{
		T->root = x ;
	}else if(y == y->parent->left)
	{
		y->parent->left = x;
	}else
	{
		y->parent->right = x;
	}

	y->parent = x;
	x->right= y;
}
//插入结点
void rbtree_insert(rbtree *T,rbtree_node *z)
{
	rbtree_node *x = T->root;
	rbtree_node *y;
	while(x ! =T->nil)
	{
		//需要在遍历时保存对应挂载的结点
		y=x;
		if(z->key < x->key){
			x=x->left;
		}else if(z->key > x->key){
			x=x->right;
		}else {
			//相同时可以自行处理，例如，对z->key数据+0.01 或者 直接返回
			return;
		}
	}
	z->parent = y;
	if(y == T->nil)
	{
		T->root = z;
	}else if(z->key < y->key){
		y->left = z;
	}else {
		y->right =z;
	}
  	z->left = T->nil;
  	z->right = T-> nil;
  	z->color = RED;
}
/*所有插入的情况
1.插入节点的父节点是黑色的情况有4种
这种情况不需要进行额外处理。
2.插入节点的父节点是红色的情况有8种
这种情况不满足红黑树的性质4，需要进行额外的修复处理。
这8种情况中：
1) 叔父节点不是红色的情况有4种
这些情况都是非上溢，需要通过重新染色和旋转来进行修复
2) 叔父节点是红色的情况有4种
这些情况都是上溢的，只需要通过祖父节点上溢合并和染色即可完成修复
*/
void fix_rbtree(rbtree* T, rbtree_node* z)
{
	//循环处理的时候，确保只对红色结点进行处理
	//只有在父节点为红色的时候，破坏了红黑树的性质才需要调整
	while (z->parent != T->nil && z->parent->color == RED)
	{
		//不满足红黑树的性质，需要进行调整
		//叔父结点不是红色，则表示非上溢
		//首选要确定自己的父节点是左子树还是右子树
		if (z->parent == z->parent->parent->left) {
			//叔父结点在右边
			rbtree_node* y = z->parent->parent->right;
			//父结点在左边
			if (y->color != RED) {
				//这种情况下需要重新染色和旋转
				//判断当前节点是左子树还是右子树，若和父节点在一条线上只要旋转一次，再进行染色
				if (z == z->parent->right)
				{
					_left_rotate(T, z->parent);
				}
				z->parent->color = BLACK;
				z->parent->parent->color = RED;
				_right_rotate(T, z->parent->parent);
				//永远只对红色节点进行操作
				z = z->parent->parent;
			}
			else
			{
				//叔父节点为红色，则表示为上溢插入（2-3-4树最多三个节点）：黑 - 黑红
				if (z->parent !=T->nil)
					z = z->parent->parent;
				z->color = RED;
				z->left->color = BLACK;
				z->right->color = BLACK;
			}
		}
		else
		{
			//插入的情况如上，省略
		}
	}
	T->root->color = BLACK;
}
/*红黑树删除的操作
1.删除红色 - 对红黑树无影响
2.删除黑色
   2.1 有两个红色叶子节点：不可能被直接删除，因为会找它的子节点替代删除，因此不用考虑这种情况
   2.2 只一红色叶子节点：用删除节点的唯一子节点对其进行替代将替代节点染成黑色
   2.3 没有红色叶子节点
   		2.3.1兄弟节点为黑色：这种情况若直接删除，会破会红黑树的平衡
   		        2.3.1.1兄弟节点至少有一个红色的叶子节点，将这个红色叶子节点借过来
   		        -》先删除该黑色节点，若兄弟节点和红色叶子节点是LR排布，则先左旋后，再根据新的兄弟节点进行右旋，最后将旋转后的左右节点改成黑色，保持平衡
   		        2.3.1.2兄弟节点没有红色的叶子节点-需要父节点向下合并进行修复
   		        1.父节点为红色：只需改色，父节点向下合并改为黑色，子节点改为红色
   		        2.父节点为黑色：直接将父节点当成被删除的节点处理，来修复父节点的下溢情况递归处理
   		 2.3.2兄弟节点为红色：通过旋转将需要删除节点的兄弟节点为黑色，再根据2.3.1修复红黑树  
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171

红黑树的平衡
1.红黑树的五条性质，是为了保证红黑树为4阶B树
2.红黑树的最大高度是2*log2(n+1)，依然是 O(logn) 级别，因为高度不会很大进而维持一种相对平衡的状态。相较于AVL树，红黑树的平衡标准相对宽松：没有一条路径会大于其他路径的2倍，这是一种弱平衡，黑高度平衡。
3.搜索的平均时间复杂度：O(logn)；添加的平均时间复杂度：O(logn)，O(1) 次的旋转操作；删除的平均时间复杂度：O(logn)，O(1) 次的旋转操作

红黑树和AVL树对比
1.搜索的次数远远大于插入和删除，选择AVL树；搜索、插入、删除次数几乎差不多，选择红黑树
2.相对于AVL树来说，红黑树牺牲了部分平衡性以换取插入/删除操作时少量的旋转操作，整体来说性能要优于AVL树
3.红黑树的平均统计性能优于AVL树，实际应用中更多选择使用红黑树