2019-05-31

红黑树

缘起

为了解决【3】中数据倾斜的问题，我们引入了足够精妙的AVL（【1】），但是AVL保持的是绝对平衡. 尽管它可以保证单次查询的速度最坏依旧在O(logn)，但是删除操作之后的重平衡可能需做多达(logn)次旋转，从而频繁地导致全树整体拓扑结构的大幅度变化。于是人们引入了Splay(【2】). Splay 实现简便、无需修改节点结构(AVL需要修改节点的bf因子)、分摊复杂度低，但可惜最坏情况下的单次操作需要O(n)时间，故难以适用于核电站、医院等对可靠性和稳定性要求极高的场合。有没有一种数据结构介于splay和AVL中间呢? 红黑树就此诞生了.红黑树可保证：在每次插入或删除操作之后的重平衡过程中，全树拓扑结构的更新仅涉及常数个节点。尽管最坏情况下需对多达O(logn)个节点重染色，但就分摊意义而言仅为O(1)个 (所谓分摊意义就是指这种最坏情形不会每次都出现，而是多次操作之后才会出现一次，那么每次操作分摊到的时间就是O(1)). 红黑树在AVL树“绝对平衡”的基础上，进一步放宽条件。实际上，红黑树所采用的“适度平衡”标准，可大致表述为：任一节点左、右子树的高度，相差不得超过两倍（可以理解为下面红黑树的第四条定义）。

那么红黑树的定义是什么呢?

红黑树是一棵BST（【3】），每个节点都有红色或者黑色两种颜色属性

每个节点不是红色就是黑色
根节点是黑色
叶子节点的2个孩子一定是黑色的（叶子节点的子节点称为NIL节点）.

上图中father的左节点也是NIL节点.
红色节点的2个孩子一定是黑色的.
从每个节点出发，到达NIL节点的每条路径上的黑色节点（包括自己，也包括NIL节点）数目相等.

其中，我们在运行算法的时候只需要考察 4、5两条性质即可.

分析

#include "stdafx.h"
#include <iostream>
#pragma warning(disable:4996)
//#define LOCAL
using namespace std;

typedef enum {RED, BLACK} COLOR; // 颜色的枚举值

typedef struct RBNode // 红黑树节点的数据结构
{
	int data;
	RBNode *lchild, *rchild, *parent;
	COLOR color; // 节点的颜色

	RBNode(int key):data(key),parent(0),color(RED){} // 默认红色

	RBNode() // NIL 节点（红黑树规定NIL节点是黑色的）
	{
		color = BLACK;
		lchild = rchild = 0;
	}
}RBNode, *RBTree;

RBTree leftrotate(RBTree root) // 左旋root为根的RB树，参见图1  注意，和AVL的左旋是一样别扭的——明明旋转的轴是r，但是入参是root, splay的旋转就比较符合直观
{
	RBTree r = root->rchild; // 对应y节点
	RBTree father = root->parent;
	root->rchild=r->lchild;
	r->lchild->parent = root;
	r->lchild = root;
	r->parent = father;
	if (father) // 如果root不是整棵RB树的根节点的话, 则还要对接原本root的父节点
	{
		if (root ==father->lchild) father->lchild = r;
		else father->rchild = r;
	}
	root->parent = r;
	return r; // 返回取代root的新的节点
}

RBTree rightrotate(RBTree root) // 右旋root为根的RB树，参见图1
{
	RBTree l = root->lchild; // 对应x节点
	RBTree father = root->parent;
	root->lchild=l->rchild;
	l->rchild->parent = root;
	l->rchild = root;
	l->parent = father;
	if (father)
	{
		if (root ==father->lchild) father->lchild = l;
		else father->rchild = l;
	}
	root->parent = l;
	return l;
}

bool search(RBTree root, int key, RBTree &save) // 红黑树的查找操作——在以root为根的RB树中查找关键字key,查找成功,返回true，并且save指向存储着这个关键字key的节点，否则返回false，并且save指向应该插入的位置,注意，这个函数的参数不需要写&root，因为root不需要改变
{ // 算法与BST是完全一样的,就是纯的BST的插入
	if (!root)
	{
		save = 0;
		return false;
	}
	RBTree p = root; // 下探指针
	while(p->lchild&&p->data!=key) // 只要p不是NIL节点（注意，RB树的叶子下面挂了两个NIL节点，所以RB树的叶子节点的lchild与rchild都不是NULL，而判定一个节点是不是NIL的充要条件就是根据它的rchild,lchild是不是NULL,当然只需要一个就行了）
	{
		if (key < p->data) p = p->lchild;
		else p = p->rchild;
	} // 要么 p是NIL要么找到了
	if (!p->lchild) // 如果p是NIL的话， 说明查找不成功
	{
		save = p->parent; // save指向的节点是要插入位置的父节点
		return false;
	}
	save = p; // 找到了
	return true;
}

void insert_fixup(RBTree &root, RBTree newRBNode) // 以root为根的RB树插入了红色的newRBNode，然后需要调整RB树使得满足红黑树的定义(因为这会导致违背红黑树的第四条性质)
{
	RBTree father = newRBNode->parent;
	if (newRBNode == root) goto id; // 表明这是构造红黑树的初始, 即插入根节点的时候, 则只需要将根节点简单变成黑色即可（红黑树的定义第二条，要求每个根节点是黑色的）不要排斥goto, 可以简化编码
	while(father && father->color == RED) // 红黑树的第四条性质是：如果节点是红色的, 那么他的两个子节点一定是黑色的
	{ // 只要 newRBNode 不是根节点 并且其父节点颜色是红色(则祖父G的颜色一定是黑色, 因为插入之前是一棵合法的红黑树)，就要继续循环，但是现在newRBNode是红色的, 这就与红黑树的第四条定义违背了, 所以要while循环调整
		RBTree U, G = father->parent; // 叔叔和祖父
		if (father == G->lchild)
		{
			U = G->rchild;
			if (U->color == RED) // 如果叔叔的颜色也是红色，注意，父亲（以及叔叔）的颜色是红色  参见 图2
			{
				U->color = father->color = BLACK; // 将父亲节点变成黑色是为了红黑树定义第四条, 而一旦变成黑色的话, 则祖父G沿着父亲这条路径到达NIL节点的黑色节点个数+1，为了不违反红黑树定义第五条, 我们必须将叔叔也变成黑色. 这样的话, 所有经过祖父的道路上的黑色节点个数+1，为了不违反红黑树定义第五条, 必须将G的颜色变成红色（G与U、father之间也不违反第四条）
				G->color = RED;
				newRBNode = G; // G以下已经调整完毕, 要往上继续调整了(因为新的祖父节点变成了红色, 所以可能会对上面构成影响(违法第四条定义), 所以要继续while循环)
				father = newRBNode->parent;
			}
			else // 如果叔叔的颜色是黑色的话（叔叔可能是NIL节点）参见图3
			{
				if (newRBNode == father->rchild) // 如果新增节点是father的右孩子, 则需要左旋，为G的右旋腾出位置来
				{
					father = leftrotate(father); // 则father指向了newRBNode, newRBNode成为了父节点,而原先的父节点成为了newRBNode的左孩子
				}
				G->color = RED;
				father->color = BLACK;
				G = rightrotate(G);
				if (!G->parent) // 如果G就是根节点
				{
					root = G;
				}
				break; // 因为新的父节点是黑色的（参见图3），所以不会影响上面的, 所以至此, 红黑树新增节点的算法结束
			}
		}
		else // 与上面完全对称的操作
		{
			U = G->lchild;
			if (U->color == RED)  // 参见图4
			{
				U->color = father->color = BLACK;
				G->color = RED;
				newRBNode = G; 
				father = newRBNode->parent;
			}
			else // 参见图5
			{
				if (newRBNode == father->lchild)
				{
					father = rightrotate(father); 
				}
				G->color = RED;
				father->color = BLACK;
				G = leftrotate(G);
				if (!G->parent)
				{
					root = G;
				}
				break;
			}
		}
	}
id: root->color = BLACK;
}

void insert(RBTree &root, int key) // 在以root为根节点RB树中插入key关键字
{
	RBTree save;
	if (search(root, key, save)) 
	{
		puts("要插入的关键值已经存在, 插入失败!");
		return;
	}
	RBTree newRBNode = new RBNode(key); // 新建红颜色的节点
	RBTree leftNil = new RBNode;
	RBTree rightNil = new RBNode;
	leftNil->parent = rightNil->parent = newRBNode;
	newRBNode->lchild = leftNil;
	newRBNode->rchild = rightNil;  // newRBNode(红节点上挂两个黑色的NIL节点)
	if (!root) root = newRBNode; // 如果原本就是空树, save亦是null
	else if (key < save->data) // 接到save的左孩子处
	{
		save->lchild = newRBNode;
		newRBNode->parent = save;
	}
	else
	{
		save->rchild = newRBNode;
		newRBNode->parent = save;
	}

	insert_fixup(root, newRBNode); // 上面的代码已经完成了插入工作（其实就是一个单纯的BST的插入工作）,下面就要进行调整（因为插入的节点的颜色是红色，仅仅可能导致红黑树第四条性质不满足, 注意, 不会导致红黑树的第五条不满足, 因为相当于替换掉了原先的NIL节点）
}

void del_fixup(RBTree &root, RBTree q) // root是根节点, q是继任者.
{
	while(q!=root &&q->color==BLACK) // 只要q不是根节点并且颜色是黑色, 注意, 如果q的颜色是红色的话, 表明被删掉的节点p是黑色（看del中对此del_fixup的调用），但是继任者是红色, 则我简单的将q的颜色变成黑色即可（本程序结束while之后的第一句代码）. 就可以满足红黑树的定义（参见图6） 但是如果继任者本身就是黑色的话, 则表明图6中father->q这一路少了一个黑色, 所以下面的while循环做的事情就是调整红黑树使得重新满足红黑树定义
	{
		RBTree sibling,father = q->parent;
		if (q == father->lchild)
		{
			sibling = father->rchild;
			if (sibling->color == RED) // 说明father一定只能是黑色, 否则违背了红黑树的定义. 这种情形我们可以化归为sibling是黑色的情况——通过旋转，那为什么要执意将q的sibling变成黑色呢? 因为如果sibling是黑色的话, 我们可以将其变成红色来达到图6中father->q一路少一个黑色的问题,但是如果本身是红色的话, 就没办法通过这样做到这一点了
			{ // 这个调整过程参见图7, 注意，如果sibling的颜色是黑色的话, 则就不需要做此调整（则father的颜色既可能是红色，也可能是黑色）, 而对于sibling颜色是红色的情形, 最后father是红色, 所以我们得知经过这次调整, father颜色可能是红色也可能是黑色，但是他两个孩子的颜色都是黑色, 但是还有一个问题需要回答——经过这次调整, 我们达到了图7中的终态（即图7的第三幅）. 那么图7的第三幅的路1和路2的黑色节点个数是一样的, 这是一个简单的数学推导, 因为图7的第二幅中q(B)比右边少一个黑色的节点, 所以图7的路1、路2、路3黑色节点的个数是一样的, 而图7的father是红色的, 不会增加黑色节点个数, 所以图7的第三幅的路1和路2黑色节点个数相等. 所以为了不违反红黑树定义的话，只需要图7第三幅的框框满足红黑树定义, 所以问题就被化归了图8 的问题
				sibling->color = BLACK;
				father->color = RED;
				father = leftrotate(father); // father将指向sibling节点, 即黑色节点
				if (!father->parent) // 如果father就是根节点的话 则要更新root的指向
				{
					root = father;
				}
				sibling = q->parent->rchild; // sibling保持是q的兄弟, 此时sibling就是黑色的, 所以我们化归为了sibling是黑色的情形.
			}
			if (sibling->lchild->color == BLACK && sibling->rchild->color == BLACK) // 如果sibling（经过上面的转换, sibling已经变成黑色的了）的左右孩子都是黑色的话（可能sibling的左右孩子都是NIL），则可以将sibling变成红色简单了事, 因为首先sibling变成红色不违反sibling和他的两个黑孩子的关系, 其次, 因为黑变红,所以少了一个黑色节点，这样就解决了图8中提出的左边的q(B)一路少一个黑色节点的问题.但是随之带来的问题是，如果图8中的father是红色的话, 则只需要将father的颜色改成黑色就可以了(因为sibling的颜色变成了红色，为了不违反红黑树定义,father必须改成黑色)，而且father变成黑色的话, 则father往上的问题也解决了，因为至此我们解决"因为删除的节点是黑色，插入的节点也是黑色导致左路少了一个黑色" 这个问题的方法是右路也少一个黑色（通过sibling黑变红），那么father的父亲如果走father这一路就少了一个黑色，但是如果father本身就是红色，则我们可以将他改成黑色来解决这一问题，则father的父节点走father这一路就不会少黑色，则整个调整算法就结束了
			{
				sibling->color = RED; // 改成红色
				q = q->parent; // q跳到其父节点上，如果father的颜色本身是红色，则q的颜色就变成了红色，则将跳出while循环，将q的颜色赋为黑色即可结束调整算法（结束的原因见上三行注释），如果father的颜色本身就是黑色，则father以下的红黑树定义问题已解决, 但是father的父节点走father这一路黑色就少了一个，则q要继续往上走（即q=q->parent），其实你想想看，这不就是图8的问题 提高了一层吗? 
			}
			else // 如果sibling的两个孩子不全是黑色, 即要么左红右黑，要么左黑右红，我们首先将左红右黑的情形转换为左黑右红.
			{
				if (sibling->rchild->color == BLACK) // 左红右黑, 要转换为左黑右红, 这个过程参见图10, 而且要说明的是，这样处理之后，问题没有变化, 即依旧是要解决图10第一幅的路1少一黑的问题. 因为路1少一黑, 所以我们知道路1=路2=路3=路4, 所以你看看图10最后一幅就知道要解决的问题依旧没变，但是我们已经将问题转换为了左黑右红
				{
					sibling->lchild->color = BLACK;
					sibling->color = RED;
					sibling = rightrotate(sibling);
				}
				// 下面的过程参见 图11，注意抓住我们要解决的根本问题——图11第一幅的q(B)少一黑，怎么办? 关注图11第三幅，解决的方式是增一黑, 所以也不会继续往father的父节点去传播. 则调整算法就结束了
				sibling->color = father->color; // 因为father马上就要左旋,sibling指向的节点将成为新的father， 所以为了不影响father上层,所以将sibling的颜色变成father的颜色（注意，father既可能是红色也可能是黑色）.
				father->color = BLACK;
				sibling->rchild->color = BLACK; // 原本是红色
				father = leftrotate(father);
				q = root; // 结束算法,跳出while循环
			}
		}
		else // 完全对称的
		{
			sibling = father->lchild;
			if (sibling->color == RED)
			{ 
				sibling->color = BLACK;
				father->color = RED;
				father = rightrotate(father); 
				if (!father->parent) 
				{
					root = father;
				}
				sibling = q->parent->lchild; 
			}
			if (sibling->lchild->color == BLACK && sibling->rchild->color == BLACK) 
			{
				sibling->color = RED; 
				q = q->parent; 
			}
			else 
			{
				if (sibling->lchild->color == BLACK) 
				{
					sibling->rchild->color = BLACK;
					sibling->color = RED;
					sibling = leftrotate(sibling);
				}
				sibling->color = father->color; 
				father->color = BLACK;
				sibling->lchild->color = BLACK; 
				father = rightrotate(father);
				q = root;
			}
		}
	}
	q->color = BLACK; // 直接改成黑色完事
}

void del(RBTree &root, int key) // 删除root为根节点的红黑树中key的关键字
{
	RBTree save,p; // save指向要删除的节点, p是最后真正被删除的节点（这个要是了解BST的删除过程, 就不会觉得奇怪，BST的删除从来都是删除某个叶子类型的替死鬼，这个替死鬼就是该待删除节点在BST意义上的前驱或者后继）
	if (!search(root, key, save))
	{
		puts("该关键字不存在, 删除失败!");
		return;
	}
	// 如果关键字存在, 并且save保存的是指向待删除节点的指针
	if (!save->lchild->lchild || !save->rchild->lchild) // 如果待删除节点的左右孩子中至少一个是NIL节点
	{
		p = save; // 则真正删除的就是save
	}
	else // 如果save的左右孩子均不是NIL，就要找save中序意义上的后继，所有BST系的删除都是这个套路
	{
		p = save->rchild;
		while(p->lchild->lchild) p = p->lchild; // 找到save的以右孩子节点为根的子树上的极左非NIL节点
	} 
	// 至此, 我们已经得到了真正需要删除的节点p, p的左孩子或者右孩子是NIL
	RBTree q;
	if (!p->lchild->lchild) // 如果p左孩子是NIL（注意，这里其实综合考虑了上面左右孩子至少一个是NIL节点和左右都不是NIL节点的情形）
	{
		q = p->rchild; // 被删掉的p的继任者就是p的右子树
	}
	else
	{
		q = p->lchild; // 被删掉的p的继任者就是p的左子树
	} // 至此得到继任者q
	q->parent = p->parent; // 继任者的父亲修改为p的父亲
	if (!p->parent) // 如果真正删除的节点是整棵树的根节点的话，这种情况只可能是待删除的节点是整棵RB树的根节点并且它至少一个左右子树为NIL,则真正删除的节点就是根节点(即save=root=p)
	{
		if (!q->lchild) // 如果q是NIL, 则表明save=p 就是根节点, 并且根节点还只是一个叶子节点（即左右孩子都是NIL）
		{
			delete q;
			q = 0;
			delete root;
			root = 0;
			return; // 树被删干净了
		}
		else root = q; // 说明继任者q不是NIL, 就可以将root的位置禅让给q了
	}
	else // 如果真正删除的节点不是根节点, 则做好嫁接工作
	{
		if (p == p->parent->lchild) p->parent->lchild = q;  // 接上去
		else p->parent->rchild = q;
	}
	if (p!=save) // 说明 save 的左孩子与右孩子都不是NIL节点，注意, 对于p=save的情形, 也就是save左孩子或者右孩子至少一个是NIL的情形, 则通过上面嫁接的方式已经完成了删除(save都从树上消失了) 根本不需要替换就删除了. 而对于p!=save的情形,p会通过上述嫁接的方式被抹杀 但是save依旧存在，而且而且save上的值没有变化. 所以要换成替死鬼的值
	{
		save->data = p->data; // p是替死鬼
	} // 至此，已经完成了bst意义上的删除工作
	if (p->color == BLACK) // 如果删除掉的节点是黑色,则需要调整, 如果删掉的是红色的话, 不需要调整,因为不会影响红黑树的定义
	{
		del_fixup(root, q);
	}
	delete p; // 最后释放这个真正被删除的节点p
	p = 0;
}

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in","r",stdin);
#endif
	RBTree root = 0;
	// 测试数据的过程参见图12开始的图示
	int a[20]={12, 1, 9, 2, 0, 11, 7, 19, 4, 15, 18, 5, 14, 13, 10, 16, 6, 3, 8, 17};
	for (int i = 0; i < 20; i++)	
		insert(root,a[i]);
	//Delete模块的测试
	for (int i = 0; i < 20; i++)	
		del(root,a[i]);	
	return 0;
}