Not Only Algorithm,不仅仅是算法,关注数学、算法、数据结构、程序员笔试面试以及一切涉及计算机编程之美的内容 。。
你的位置:NoAlGo博客 » 数据结构 » , ,

红黑树

二叉查找树可以方便地维护一个动态集合,实现快速的添加、删除以及查询操作。但仅仅当树的高度较低时执行速度较快,当树的高度增加甚至变得极度不平衡时,各种操作的性能急剧下降。红黑树(Red-Black Tree,RBT)是一种平衡的二叉查找树,能在最坏情况下仍然获得较好的时间复杂度。目前C++ STL中包括set、multiset、map、multimap等多种数据结构内部都使用了红黑树或者其变体进行实现。
本文参考算法导论中红黑树章节,将详细介绍红黑树的原理及其在C/C++中的具体实现代码。注意,红黑树的思想及实现跟普通的二叉查找树关系非常大,如果你对二叉查找树还不是非常熟悉,建议先阅读此文:二叉查找树 http://noalgo.info/603.html

简介

红黑树是一种二叉查找树,但在每个节点上增加一个存储位表示节点的颜色,可以是红色或黑色。红黑树的节点包括五个域:color、key、left、right和parent。如果某个节点没有儿子或父亲节点,则该节点的相应域设为NIL。这里NIL是一个特殊节点的地址,是为了代码实现方便而用来代替普通NULL的指针。于是,在红黑树中,所有节点都是以NIL节点结尾,而根节点父亲也是NIL节点。与普通叶子节点的定义不同,这里称NIL节点为叶子节点,而其他带关键字的节点为树的内节点。

除了一般二叉查找树的要求外,红黑树还必须满足以下5个红黑性质:

  1. 每个节点或是红的,或是黑的。
  2. 根节点是黑的。
  3. 每个叶子节点(NIL)是黑的。
  4. 如果一个节点是红的,则它的两个儿子都是黑的。
  5. 对每个节点,从该节点到其子孙节点的所有路径上包含相同数目的黑节点。

根据红黑树的这个性质,可以很容易知道为什么红黑树是一种接近平衡的二叉查找树。从根节点到所有叶子节点上包含的黑色节点个数相同(记为h),由因为一个红色节点的儿子必须是黑色的,不可能有连续相邻的两个红色节点,则路径最长的情况是路径上红黑节点交错出现,此时树的高度为2h,而路径最短的情况是路径上全部均为黑色节点,此时树的高度为h。于是,红黑树中最长路径不会超过最短路径的2倍,于是红黑树是接近平衡的。

只要在红黑树的操作中保持红黑树的红黑性质,则在任意情况下红黑树的操作复杂度均为O(h),即O(lg n)。

节点数据结构

红黑树使用二叉树实现,其节点包括关键字及四个指针域,为了使用时方便,还提供了带默认参数的构造函数。
为了提高代码可读性,使用了枚举类型表示红、黑两种颜色。
另外定义了红黑树的类,包含一个根节点的指针和一个特殊的指针NIL,用来表示空节点。
以下是其C++代码实现,其中使用struct定义,可以让成员默认拥有public属性。

//颜色枚举类型
typedef enum { RED = 0, BLACK} color_t;

//树节点
struct Node
{
	int key;                     //关键字
	color_t color;               //颜色
	Node *left, *right, *parent; //左儿子、右儿子、父亲

	//默认构造函数
	Node (int k, color_t c, Node *l, Node *r, Node *p):
		key(k), color(c), left(l), right(r), parent(p) {}
};

//红黑树
struct Tree
{
	Node *NIL;  //树统一的空节点
	Node *root; //树根

	//默认构造函数,初始化红黑树,初始化表按定义的顺序初始化(先NIL后root)
	Tree(): NIL(new Node(0, BLACK, NULL, NULL, NULL)), root(NIL) {} 
};

遍历红黑树

红黑树的遍历与普通二叉树遍历一样,可以使用递归算法按照前序、中序、后序等不同顺序进行遍历。如果使用中序遍历,根据二叉搜索树的特定,遍历的顺序会按照节点关键字的大小关系从小到大依次进行。
为了观察方便,这里使用前序遍历打印红黑树各个节点的关键字和颜色,同时打印出该节点左右儿子的关键字。注意,这里的实现中,NIL节点被默认赋予了关键字0,所以输出中的0表示空节点。以下是其递归的代码实现。

//前序遍历,输出红黑树
void preorder(Tree *tree, Node *x)
{
	if (x == tree->NIL) return;

	printf("%-2d:%-5s  left:%2d  right:%2d\n", 
		x->key, x->color == RED ? "RED" : "BLACK", x->left->key, x->right->key); //根节点
	preorder(tree, x->left);      //左子树
	preorder(tree, x->right);     //右子树
}

查询二叉查找树

红黑树中查找某个关键字的操作和二叉查找树一样,除了普通的search之外,其还能支持minimum、maximun、successor、predecessor等查询,对于高度为h的树,它们都可以在O(h)时间内完成。因为具体思想和二叉查找树类似,这里不再进行详细介绍,具体可以参考二叉查找树一文。

这里仅提供部分参考代码,主要是后面的插入、删除操作需要依赖的代码。
首先是非递归查找某个元素的代码:

//非递归查找元素,找到返回关键字的结点指针,没找到返回NIL
Node* searchNode(Tree *tree, int key)
{
	Node *p = tree->root;
	while (p != tree->NIL && key != p->key)
	{
		if (key < p->key) p = p->left;
		else p = p->right;
	}
	return p;
}

然后是查找最小关键字的代码:

//查找最小关键字
Node* searchMin(Tree *tree, Node *x)
{
	//空树时返回NULL
	if (x == tree->NIL) return tree->NIL;

	//一直往左儿子找,直到没有左儿子
	while (x->left != tree->NIL) x = x->left;
	return x;
}

最后是查找某个节点后继的代码:

//查找某个结点的后继
Node* searchSuccessor(Tree *tree, Node *x)
{
	//空树
	if (x == tree->NIL) return tree->NIL;

	//有右子树,右子树中最小的那个
	if (x->right != tree->NIL) return searchMin(tree, x->right);

	//无右子树,则为最低的祖先,其左儿子也是祖先
	Node *y = x->parent; //p向上搜索,q为p的父亲
	while (y != tree->NIL &&  x == y->right)
		x = y, y = y->parent;
	return y;
}

树旋转

在红黑树上使用类似于普通二叉查找树的插入、删除操作后可能会违反红黑树的性质,为了保持这些性质,需要改变树中某些节点的颜色以及指针结构。指针结构的修改通过旋转来完成,这是一种能够保持二叉查找树性质的查找树局部操作。

树的旋转包括两种:左旋和右旋。当在某个节点x上做左旋时,我们假设它的右儿子y不是NIL节点,于是这里的x可以是树中任意右儿子不是NIL的节点。如下图所示,左边的树经过左旋操作后变成后边的树。左旋以x和y之间的链为支轴进行,它使y成为该子树新的根,x成为y的左儿子,而y的左儿子则成为x的右儿子。

   x                 y
 /   \             /   \
a     y           x     c
     / \         / \
    b   c       a   b

以下是左旋操作的代码实现,其中如果x的右儿子是NIL节点时直接退出。

//左旋
int leftRotate (Tree *tree, Node *x)
{
	//x的右儿子不能为空
	if (x->right == tree->NIL) return 1;

	//记录图中标识的y节点
	Node *y = x->right;

	//修正x和y的左儿子b之间的链接
	x->right = y->left;
	if (y->left != tree->NIL) y->left->parent = x;

	//修正x的父亲和y之间的链接
	y->parent = x->parent;
	if (x->parent == tree->NIL)   //x为树根
		tree->root = y;
	else if(x == x->parent->left) //x为左儿子
		x->parent->left = y;
	else                          //x为右儿子
		x->parent->right = y;

	//修正x和y之间的链接
	y->left = x;
	x->parent = y;

	return 0;
}

右旋操作可以对称地进行,如下图所示,右旋以x和y之间的链为支轴进行,它使y成为该子树新的根,x成为y的右儿子,而y的右儿子则成为x的左儿子。

     x             y
   /   \         /   \
  y     c       a     x
 / \                 / \
a   b               b   c

其代码实现如下:

//右旋
int rightRotate (Tree *tree, Node *x)
{
	//x的左儿子不能为空
	if (x->left == tree->NIL) return 1;

	//记录图中标识的y节点
	Node *y = x->left;

	//修正x和y的右儿子b之间的链接
	x->left = y->right;
	if (y->right != tree->NIL) y->right->parent = x;

	//修正x的父亲和y之间的链接
	y->parent = x->parent;
	if (x->parent == tree->NIL)   //x为树根
		tree->root = y;
	else if(x == x->parent->left) //x为左儿子
		x->parent->left = y;
	else                          //x为右儿子
		x->parent->right = y;

	//修正x和y之间的链接
	y->right = x;
	x->parent = y;

	return 0;
}

插入节点

在红黑树中插入节点的操作跟在普通的二叉查找树中插入节点的方法类似,这里直接上代码:

//插入节点
void insertNode(Tree *tree, int key)
{
	//新建节点,节点颜色为红色
	Node *z = new Node(key, RED, tree->NIL, tree->NIL, tree->NIL);

	// 向下查找待插入的位置,x为当前节点(最终为空节点),y为其父亲
	Node *x = tree->root, *y = tree->NIL;
	while (x != tree->NIL)
	{
		y = x;
		if (z->key == x->key) return;
		else if (z->key < x->key) x = x->left;
		else x = x->right;
	}

	// 把新节点z插入到y的下面,修正连接关系
	z->parent = y;
	if (y == tree->NIL) tree->root = z;
	else if (z->key < y->key) y->left = z;
	else y->right = z;

	insertFixup(tree, z);
}

其中跟普通二叉查找树的插入不同的地方在于:

  1. 代码中所有判断空节点的语句由NULL指针变成了NIL指针,前者是C语言规定的空指针,后者是我们人为定义的一个表示空节点的指针。
  2. 新插入的节点的儿子指针域相应为NIL指针,并且着为红色。
  3. 代码最后需要调用辅助函数来保持红黑树的性质。

这里关键的地方就是如何调整红黑树的颜色及指针关系,使得新插入节点后仍然能满足红黑性质。
我们把新插入的节点(记为z)着成红色,唯一可能破坏的性质是性质4,因为如果z的父亲是红色时,此时树中存在连续的两个红色节点。性质1、2、3显然不会破坏,而对于性质5,因为新节点z插入到原先的空节点NIL的位置,同时z的两个儿子成为了新的两个NIL节点,而z的颜色是红色的,于是根节点到这两条路径上的黑色节点的个数是不变的,由于原先从根节点到叶子节点的所有路径黑节点个数都是一样的,所以插入之后所有这些路径上黑节点个数仍然一样。

        11                   11                      11                7
      /    \               /    \                  /    \             /  \
    2        14          2      14(y)            7      14(y)     2(z)     11
  /   \       \        /   \       \           /   \       \      / \     /  \
1      7      15     1     7(z)      15     2(z)    8      15    1   5   8    14
      / \                  / \              / \                     /           \
     5  8(y)              5   8            1   5                   4              15
    /                    /                    /                  
  4(z)                  4                    4                   

于是,只有当z的父亲是红色时才需要对红黑树进行修正。下面假设z的父亲是其父亲的左儿子,然后根据z的叔叔(记为y)的颜色是红色还是黑色进行分情况讨论。

情况一:z的叔叔y是红色的。
如下第一到第二幅图所示。此时z的父亲和y均是红色的,而根据性质4,z的父亲的父亲必然是黑色的,那么我们可以把z的父亲和叔叔都变为黑色(此时z和z的父亲不再是连续的红色,但该路径上黑色节点的个数增加了1),再把z的父亲的父亲变为红色(此时该路径上的黑色节点个数保存不变)。现在我们可以把z的父亲的父亲当成新的z,因为其父亲仍然可能是红色的,于是又出现连续两个红色节点的问题。但此时z的高度在树中上移了两层,是一个稍微简单的子问题,可以通过递归或循环进行解决。

当z的叔叔y是黑色时,我们再根据y是右儿子还是左儿子分情况讨论。

情况二:z的叔叔y是黑色的,而且z是右儿子。
如图中第二到第三幅图所示。对于这种情况,我们简单地把z变成z的父亲,然后对z做一次左旋操作,转化为情况三进行处理。

情况三:z的叔叔y是黑色的,而且z是左儿子。
如图中第三到第四幅图所示。此时z和z的父亲是红色的,而z的父亲的父亲肯定是黑色的,我们把z的父亲变成黑色,z的父亲的父亲变成红色,这样对性质5不会有影响,然后再对z的父亲的父亲做一次右旋操作,此时彻底解决了z上存在两个连续红色节点的问题,修正完毕。

可以看到,修正所涉及的旋转操作最多只有两次,分别是在情况二、三种进行。
当z的父亲是其父亲的右儿子时,具体思想是一样的,只需要把上述操作中涉及到的左、右互换即可,具体参考代码实现:

//插入修正
void insertFixup(Tree *tree, Node *z)
{
	while (z->parent->color == RED)
	{
		if (z->parent == z->parent->parent->left)
		{
			Node *y = z->parent->parent->right;
			if (y->color == RED)                      //情况一
			{
				z->parent->color = y->color = BLACK;
				z->parent->parent->color = RED;
				z = z->parent->parent;
			}
			else
			{
				if (z == z->parent->right)            //情况二(转化为情况三)
				{
					z = z->parent; leftRotate(tree, z);
				}
				z->parent->color = BLACK;             //情况三
				z->parent->parent->color = RED;
				rightRotate(tree, z->parent->parent);
			}
		}
		else //上述的对称情况
		{
			Node *y = z->parent->parent->left;
			if (y->color == RED)
			{
				z->parent->color = y->color = BLACK;
				z->parent->parent->color = RED;
				z = z->parent->parent;
			}
			else
			{
				if (z == z->parent->left)
				{
					z = z->parent; rightRotate(tree, z);
				}
				z->parent->color = BLACK;
				z->parent->parent->color = RED;
				leftRotate(tree, z->parent->parent);
			}
		}
	}
	tree->root->color = BLACK;
}

删除节点

在红黑树中删除节点的操作跟在普通的二叉查找树中删除节点的方法也是类似的,其代码为:

//删除节点
void deleteNode(Tree *tree, int key)
{
	//查询待删除的节点p,并判断是否为空
	Node *z = searchNode(tree, key); 
	if (z == tree->NIL) return;

	//查找真正删除的节点y及其儿子x
	Node *y = (z->left==tree->NIL || z->right==tree->NIL) ? z : searchSuccessor(tree, z);
	Node *x = (y->left != tree->NIL) ? y->left : y->right;

	//修正删除节点y后,y的父亲和y的儿子之间的链接
	x->parent = y->parent;
	if (y->parent == tree->NIL) tree->root = x;
	else if(y == y->parent->left) y->parent->left = x;
	else y->parent->right = x;

	if (y != z) z->key = y->key;

	if (y->color == BLACK)
		deleteFixup(tree, x);

	delete(y);
}

跟普通的二叉查找树的删除不同的地方在于:

  1. 代码中所有判断空节点的语句由NULL指针变成了NIL指针。
  2. 第5句代码中直接把x的父亲置为y的父亲,这样,如果x是空节点NIL,则其父亲就指向了被删除的节点y的父亲。
  3. 最后当删除的节点y是黑色时,调用辅助函数来保持红黑树的性质。

这里的z是待删除的节点,y是真正删除的节点,而x是y的儿子(可能为NILL,但此时x的父亲仍然指向了y的父亲)。

注意到这里只有当删除的节点y是黑色时才需要进行修正,而当删除红色节点则不需要修正。原因是显然的,因为如果删除了红色节点:

  1. 根的叶子的所有路径上的黑色节点的个数保存不变。
  2. 不存在两个相邻的红色节点。
  3. 红色的节点不可能是根,所以根还是黑色的。

如果删除的节点y是黑色的,则会产生三个问题:

  1. 如果y是根节点,而y的一个红色儿子成为了新的根,则违反了性质1。
  2. 如果x和y的父亲都是红色的,则违反了性质4。
  3. 删除了黑色节点y,导致包含y的任何路径上黑色节点个数少一,违反了性质5。

补救问题3的一个办法是把节点x看成还有一重额外的黑色,也就是说,把任意包含节点x的路径上的黑色节点个数加1,则此时能够保持性质5。现在问题是节点x可能是既是红色又是黑色,或者两重黑色,违反了性质1。

下面我们假设x是左儿子,根据x的兄弟(记为w)是红色还是黑色进行分情况讨论。

情况一:x的兄弟w是红色的。
如下图所示。此时w是红色的,则w肯定有黑色的儿子,而w的父亲也是黑色的,我们把w变成黑色,把w的父亲变成红色,再对w的父亲做一次左旋,这能够保持红黑性质,并且x的兄弟变成了之前w的儿子,其颜色为黑色,转化成为了下面的情况之一。

       B                          D
    /     \                     /   \
 A(x)     D(w)               B        E
 / \      /   \            /  \      / \
a   b   C      E        A(x)  C(w)  e   f
       / \    / \       / \    / \
      c  d   e   f     a   b  c   d

当w的颜色为黑色时,我们根据w的两个儿子的颜色进行分情况讨论。

情况二:x的兄弟w是黑色的,而且w的两个儿子都是黑色的。
如下图所示(蓝色表示可以是红色也可以是黑色)。此时w是黑色的,我们把x和w上去掉一重黑色,此时w变成红色(因为w的儿子都是黑色的,不会违反性质4),而x只有一重黑色。为了补充从x和w上去掉的一重黑色,我们在原来是红色或者黑色的x的父亲上新增加一重额外黑色。现在我们可以把x变成x的父亲来递归或循环解决这个问题。
注意,如果新的x(原来x的父亲)是红色的,增加一重额外的黑色只需要把它变成黑色即可,此时就修正好了整棵红黑树,算法可以终止。可以看到循环条件就是x的颜色是黑色,原因就是这里。
而当新的x仍然是黑色时,则需要重新进行同样的工作。

       B                     B(x)
     /   \                  /   \
 A(x)     D(w)           A        D
 / \      / \           / \      / \
a   b   C     E        a   b   C     E
       / \   / \              / \   / \
      c   d e   f            c   d e   f

情况三:x的兄弟w是黑色的,w的左儿子是红色,右儿子是黑色的。
如下图所示。此时,把w变成红色,w的左儿子变成黑色,并对w进行一次右旋,保持红黑性质并且把情况转化为情况四。因为现在x的新兄弟w是黑色的(原w的变成黑色的左儿子),并且有一个红色的右儿子(变成红色的原w)。

       B                      B
     /   \                  /   \
 A(x)     D(w)          A(x)     C(w)
 / \      / \           / \      / \
a   b   C     E        a   b   c     D
       / \   / \                    / \
      c   d e   f                  d   E
                                      / \
                                     e   f

情况四:x的兄弟是黑色的,而且w的右儿子是红色的。
如下图所示(蓝、绿色表示可以是红色也可以是黑色)。。此时我们把w的颜色变为x父亲的颜色,把w和w的右儿子变成黑色,然后对x的父亲做一次左旋,于是,x额外的一重黑色转移到了其现在的父亲身上了,并且对于其他的节点来说红黑性质仍然能够保持,修正完成。

       B                         D
     /   \                     /   \
 A(x)     D(w)              B        E
 / \      / \             /  \      / \
a   b   C     E         A      C   e   f
       / \   / \       / \    / \
      c   d e   f     a   b  c   d

可以看到,修正所涉及到的旋转操作最多只有三次,分别是在情况一、三、四进行。
当x是右儿子时,只需要把以上操作左右互换即可。具体代码为:

//删除修正
void deleteFixup(Tree *tree, Node *x)
{
	while(x != tree->root && x->color == BLACK)
	{
		if (x == x->parent->left)
		{
			Node *w = x->parent->right; //x的兄弟
			if (w->color == RED)                                    //情况一(转为情况二、三、四之一)
			{
				w->color = BLACK;
				x->parent->color = RED;
				leftRotate(tree, x->parent);
				w = x->parent->right;
			}
			if (w->left->color == BLACK && w->right->color == BLACK)//情况二
			{
				w->color = RED;
				x = x->parent;
			}
			else
			{
				if (w->right->color == BLACK)                       //情况三(转为情况四)
				{
					w->left->color = BLACK;
					w->color = RED;
					rightRotate(tree, w);
					w = x->parent->right;
				}
				w->color = x->parent->color;                        //情况四
				x->parent->color = BLACK;
				w->right->color = BLACK;
				leftRotate(tree, x->parent);
				x = tree->root;
			}
		}
		else //上述的对称情况
		{
			Node *w = x->parent->left; //x的兄弟
			if (w->color == RED)                                    //情况一(转为情况二、三、四之一)
			{
				w->color = BLACK;
				x->parent->color = RED;
				rightRotate(tree, x->parent);
				w = x->parent->left;
			}
			if (w->left->color == BLACK && w->right->color == BLACK)//情况二
			{
				w->color = RED;
				x = x->parent;
			}
			else
			{
				if (w->left->color == BLACK)                       //情况三(转为情况四)
				{
					w->right->color = BLACK;
					w->color = RED;
					leftRotate(tree, w);
					w = x->parent->left;
				}
				w->color = x->parent->color;                        //情况四
				x->parent->color = BLACK;
				w->left->color = BLACK;
				rightRotate(tree, x->parent);
				x = tree->root;
			}
		}
	}
	x->color = BLACK;
}

简单测试

最后以插入节点一节的红黑树为例,简单测试一下程序的运行结果。

#include <cstdio>
int main()
{
	Tree rbt;

	int a[] = {2, 14, 7, 15, 1, 5, 11, 8, 4};

	//插入节点
	for (int i = 0; i < 9; i++) insertNode(&rbt, a[i]);
	preorder(&rbt, rbt.root);

	printf("%d\n", searchSuccessor(&rbt, rbt.root)->key);

	//删除节点
	for (int i = 0; i < 4; i++) deleteNode(&rbt, a[i]);
	preorder(&rbt, rbt.root);

    return 0;

	/*运行结果为:
	7 :BLACK  left: 2  right:14
	2 :RED    left: 1  right: 5
	1 :BLACK  left: 0  right: 0
	5 :BLACK  left: 4  right: 0
	4 :RED    left: 0  right: 0
	14:RED    left:11  right:15
	11:BLACK  left: 8  right: 0
	8 :RED    left: 0  right: 0
	15:BLACK  left: 0  right: 0
	8
	8 :BLACK  left: 4  right:11
	4 :RED    left: 1  right: 5
	1 :BLACK  left: 0  right: 0
	5 :BLACK  left: 0  right: 0
	11:BLACK  left: 0  right: 0
	*/
}
上一篇: 下一篇:

我的博客

NoAlGo头像编程这件小事牵扯到太多的知识,很容易知其然而不知其所以然,但真正了不起的程序员对自己程序的每一个字节都了如指掌,要立足基础理论,努力提升自我的专业修养。

站内搜索

最新评论