《算法导论》笔记－－红黑树（二）

 

红黑树的节点删除

 

从红黑树上删除一个节点，可以先用普通二叉搜索树的方法，将节点从红黑树上删除掉，然后再将被破坏的红黑性质进行恢复。

我们回忆一下普通二叉树的节点删除方法：Z指向需要删除的节点，Y指向实质结构上被删除的结点，如果Z节点只有一个子节点或没有子节点，那么Y就是指向Z指向的节点。如果Z节点有两个子节点，那么Y指向Z节点的后继节点（其实前趋也是一样的），而Z的后继节点绝对不可能有左子树。因此，仅从结构来看，二叉树上实质被删除的节点最多只可能有一个子树。

现在我们来看红黑性质的恢复过程：

如果Y指向的节点是个红色节点，那么直接删除掉Y以后，红黑性质不会被破坏。操作结束。

如果Y指向的节点是个黑色节点，那么就有几条红黑性质可能受到破坏了。首先是包含Y节点的所有路径，黑高度都减少了一（第５条被破坏）。其次，如果Y的有红色子节点，Y又有红色的父节点，那么Y被删除后，就出现了两个相邻的红色节点（第４条被破坏）。最后，如果Y指向的是根节点，而Y的子节点又是红色的，那么Y被删除后，根节点就变成红色的了（第２条被破坏）。

其中，第５条被破坏是让我们比较难受的。因为这影响到了全局。这样动作就太大太复杂了。而且在这个条件下，进行其它红黑性质的恢复也很困难。所以我们首先解决这个问题：如果不改变含Y路径的黑高度，那么树的其它部分的黑高度就必须做出相应的变化来适应它。所以，我们想办法恢复原来含Y节点的路径的黑高度。做法就是把Y节点的黑色，推到它的子节点X上去。（X可能是NIL节点）。这样，X就可能具有双重黑色，或是同时具有红黑两色，也就是第１条性质被破坏了。

但第１条性质是比较容易恢复的：一、如果X是同时具有红黑两色，那么好办，直接把X涂成黑色，就行了。而且这样把所有问题都解决了。因为将X变为黑色，２、４两条如果有问题的话也会得到恢复。二、如果X是双黑色，那么我们希望把这种情况向上推一直推到根节点（调整树结构和颜色，X的指向新的双黑色节点，X不断向上移动），让根节点具双黑色，这时，直接把X的一层黑色去掉就行了（因为根节点被包含在所有的路径上，所以这样做所有路径同时黑高减少一，不会破坏红黑特征）。

下面就具体地分析如何恢复1、２、４三个可能被破坏的红黑特性：我们知道，如果X指向的节点是有红黑两色，或是X是根节点时，只需要简单的对X进行一些改变就行了。要对除X节点外的其它节点进行操作时，必定是这样的情况：X节点是双层黑色，且X有父节点P。由知可知，X必然有兄弟节点W，而且这个W节点必定有两个子节点。（因为这是原树满足红黑条件要求而自然具备的。X为双黑色，那么P的另一个子节点以下一定要有至少两层的节点，否则高黑度不可能和X路径一致）。所以我们就分析这些节点之间如何变形，把问题限制在比较小的范围内解决。另一个前提是：X在一开始，肯定是树底的叶节点或是NIL节点，所以在递归向上的过程中，每一步都保证下一步进行时，至少 X的子树是满足红黑特性的。因此子树的情况就可以认为是已经正确的了，这样，分析就只限制在X节点，X的父节点P，X的兄弟节点W，以及W的两个子节点。这些个节点中。

W以及W的两个子节点C1和C1的一共有五种组合，便有两种情况的处理是一致的，因此调整的过程可以分以下四个情况：

第一种情况：W是红色节点

 

如上图，如果W是红色的，那么B和D节点进行一次左旋，并把D（也就是原来的W）着为黑色，B节点（X的父节点）着为红色。然后让W指向X的新兄弟。这样，就把这种情况转化为了W为黑色的情况来解决。在这个变形中，这五个节点之间保持了红黑性质不变，而X指向的双黑色节点的位置和颜色特性都没有变化。变形后的情况如何解决呢？下面的都是W为黑色的问题，因此下面三种中总有一种会合适。

PS：有没有其它变形呢？有，比如C和D进行右旋，B节点变为红色，变形后五个节点红黑正确的，但是这五个节点与树的其它部分相接处可能会产生问题，这样要考虑的因素就太多了。

 

第二种情况：W以及W的两个子节点都是黑色的

 

 

如上图，注意，B即可以是红色也可以是黑色。

这种情况下，把D节点着成红色。然后把X的一个黑色推到父节点B中去，这时X就指向B节点了。变形前后，这五个节点间的黑高是没有变化的。

唯一可能产生问题的就是如果B原来是红色，那么B和D两个红色相邻就破坏了第４个性质，这样新X的子树就有问题了。这本来不符合我们向上递归的假设。但正好在这种情况下递归就可以结束了。因为B节点原来是红色，现在双加一层黑色，那么X现在指向的这个节点就是红黑两色的，直接把X（也就是B）着为黑色。问题就已经完整解决了。

如果B节点现在是双层黑色，那就以B为新的X进行向上的下一次的递归。

 

第三种情况：W的左子节点是红色的且右子节点是黑色。

 

 

  如上图，B即可以是黑色也可以是红色。

  把C和D进行一次旋转，改变C和D的颜色变形成新的结构。把问题转化成W的右子节点为红色的情况来解决。注意，原来C是红色的，所以C的子节点一定是黑色的，所以旋转中C节点的一个子树挂到之后着为红色的D节点上不会破坏红黑性质。变形后黑高度不变。

 

  第四种情况：W的右子节点是红色（左子节点可以是红色或黑色）

 

 

  如上图，B节点可以是红色或是黑色。

  将B和D进行一次左旋，并交换两者的颜色。再将E着为黑色。这时，只要将X的一层黑色脱去，整个问题也得到了解决。递归结束。（在代码上，为了标识递归结束，我们把X指向根节点）

 

  因此，只要按上面四种情况一直递归处理下去，X最终总会指向根结点或一个红色结点，这时我们就可以结束递归并把问题解决了。

  以上就是红黑色的节点删除过程。

 

 

  以下的简单的代码实现：

// -------------------------------------------------------
// FileName : BinarySearchTree.cpp
// Date     : 2009-1-14 
// Summary  : 红黑树的简单实现，节点中除了红黑树结构本身需要的信息之外，只
//            包含一个int域作为节点的key
// CopyLeft : 李诒雯
// -------------------------------------------------------

#include <stdio.h>

// 定义节点颜色
enum COLOR {
	BLACK = 0,
	RED
};

// 红黑树节点
typedef struct tagRBTreeNode {
	int key;
    struct tagRBTreeNode *left;
	struct tagRBTreeNode *right;
	struct tagRBTreeNode *parent;
	unsigned char color;
}RBTreeNode, *PRBTreeNode;

// 红黑树，包含一个指向根节点的指针
typedef struct tagRBTree {
	PRBTreeNode root;	
}RBTree, *PRBTree;

// 红黑树的NIL节点
static RBTreeNode NIL = {0, 0, 0, 0, BLACK};

#define PNIL (&NIL)   // NIL节点地址

// 生成一个红黑树节点，缺省的节点颜色是红黑。
PRBTreeNode CreateRBTreeNode(int keyVal)
{
	PRBTreeNode p = (PRBTreeNode)malloc(sizeof(RBTreeNode));
	p->color = RED;
	p->left = PNIL;
	p->right = PNIL;
	p->parent = PNIL;
	p->key = keyVal;
	return p;
}

// 释放一个节点的内存
void DeleteRBTreeNode(PRBTreeNode pDel)
{
	if (PNIL != pDel) {
		free(pDel);
	}	
}

void InitRBTree(PRBTree pTree) // 初始化一棵红黑树
{
	pTree->root = PNIL;
}

// 顺序遍历一棵红黑树，并对每个节点执行指定的操作
void INORDER_RBTREE_WALK(PRBTreeNode pRoot, void (*Action)(PRBTreeNode ))
{
	// 就是一个二叉树的中序遍历
	if (PNIL != pRoot) {
		INORDER_RBTREE_WALK(pRoot->left, Action);
		Action(pRoot);
		INORDER_RBTREE_WALK(pRoot->right, Action);
	}
}

// 查找指定键值的节点
PRBTreeNode RBTREE_SEARCH(PRBTreeNode pRoot, int val_key)
{
	while ((PNIL != pRoot) && (val_key != pRoot->key)) {
		pRoot = (val_key < pRoot->key ? pRoot->left : pRoot->right);	
	}
	return pRoot;
}

// 查找最大键值节点
PRBTreeNode RBTREE_MAX(PRBTreeNode pRoot)
{
	while (PNIL != pRoot->right) {
		pRoot = pRoot->right;	
	}
	return pRoot;
}

// 查找最小键值节点
PRBTreeNode RBTREE_MIN(PRBTreeNode pRoot)
{
	while (PNIL != pRoot->left) {
		pRoot = pRoot->left;	
	}
	return pRoot;
}

// 查找指定节点的后继节点
PRBTreeNode RBTREE_SUCCESSOR(PRBTreeNode pRoot)
{
	if (PNIL != pRoot->right) {
		return RBTREE_MIN(pRoot->right);
	}
	PRBTreeNode pParent = pRoot->parent;
	while((PNIL != pParent) && (pRoot == pParent->right)) {
		pRoot = pParent;
		pParent = pRoot->parent;			
	} 
	return pParent;
}

// 查找指定节点的前趋节点
PRBTreeNode RBTREE_PREDECESSOR(PRBTreeNode pRoot)
{
	if (PNIL != pRoot->left) {
		return RBTREE_MAX(pRoot->left);
	}
	PRBTreeNode pParent = pRoot->parent;
	while((PNIL != pParent) && (pRoot == pRoot->left)) {
		pRoot = pParent;
		pParent = pRoot->parent;			
	} 
	return pParent;
}

// 对指定节点进行左旋
static void LEFT_ROTATION(PRBTree pTree, PRBTreeNode pNode)
{
	PRBTreeNode pRight = pNode->right;
	pRight->parent = pNode->parent;
	if(pNode->parent->left == pNode){
		pRight->parent->left = pRight;
	}
	else {
		pRight->parent->right = pRight;
	}

	if (PNIL == pRight->parent) {
		pTree->root = pRight;
	}
	if (PNIL != pRight->left) {
		pRight->left->parent = pNode;
	}
	pNode->right = pRight->left;
	pNode->parent = pRight;
	pRight->left = pNode;
}

// 对指定节点进行右旋
static void RIGHT_ROTATION(PRBTree pTree, PRBTreeNode pNode)
{
	PRBTreeNode pLeft = pNode->left;
	pLeft->parent = pNode->parent;
	if(pNode->parent->left == pNode){
		pLeft->parent->left = pLeft;
	}
	else {
		pLeft->parent->right = pLeft;
	}

	if (PNIL == pLeft->parent) {
		pTree->root = pLeft;
	}
	if (PNIL != pLeft->right) {
		pLeft->right->parent = pNode;
	}	
	pNode->left = pLeft->right;
	pNode->parent = pLeft;
	pLeft->right = pNode;
}

// 在红黑树插入动作后进行红黑性质恢复
static void FIX_UP_RB_AFTER_INSERT(PRBTree pTree, PRBTreeNode pNode)
{
	while(RED == pNode->parent->color) {
		if (pNode->parent == pNode->parent->parent->left){
			PRBTreeNode pUncleNode = pNode->parent->parent->right;
			if (RED == pUncleNode->color){
				pNode->parent->color = BLACK;
				pUncleNode->color = BLACK;
				pNode = pUncleNode->parent;
				pNode->color = RED;
			}
			else 
			{
				if (pNode == pNode->parent->right) {
					pNode = pNode->parent;
					LEFT_ROTATION(pTree, pNode);
				}
				pNode->parent->color = BLACK;
				PRBTreeNode TempP = pNode->parent->parent;
				TempP->color = RED;
				RIGHT_ROTATION(pTree, TempP);
			}
		}
		else{
            PRBTreeNode pUncleNode = pNode->parent->parent->left;
			if (RED == pUncleNode->color){
				pNode->parent->color = BLACK;
				pUncleNode->color = BLACK;
				pNode = pUncleNode->parent;
				pNode->color = RED;
			}
			else 
			{
				if (pNode == pNode->parent->left) {
					pNode = pNode->parent;
					RIGHT_ROTATION(pTree, pNode);
				}
				pNode->parent->color = BLACK;
				PRBTreeNode TempP = pNode->parent->parent;
				TempP->color = RED;
				LEFT_ROTATION(pTree, TempP);
			}
		}
	}
	pTree->root->color = BLACK;
}

// 红黑树的节点插入
void RBTREE_INSERT(PRBTree pTree, PRBTreeNode pNode)
{
    PRBTreeNode pNodePosition = pTree->root;
	PRBTreeNode pParent = PNIL;

	while (PNIL != pNodePosition) {
		pParent = pNodePosition;
		pNodePosition = (pNode->key > pNodePosition->key ? 
			pNodePosition->right : pNodePosition->left);
	}
	
	pNode->parent = pParent;
	if (PNIL == pParent) {
        pTree->root = pNode;		
	}
	else {
		if (pNode->key > pParent->key) {
			pParent->right = pNode;
		}
		else {
			pParent->left = pNode;
		}
	}
	FIX_UP_RB_AFTER_INSERT(pTree, pNode);
}

// 在红黑树删除动作后进行红黑性质恢复
static void FIX_UP_RB_AFTER_DELETE(PRBTree pTree, PRBTreeNode pNode)
{
	while ((pNode->color == BLACK) && (pNode != pTree->root)) {
		if (pNode == pNode->parent->left){
			PRBTreeNode pBrother = pNode->parent->right;
			if (RED == pBrother->color) {
				pBrother->color = BLACK;
				pNode->parent->color = RED;
				LEFT_ROTATION(pTree, pNode->parent);
				pBrother = pNode->parent->right;
			}
			if ((BLACK == pBrother->right->color) && (BLACK == pBrother->left->color)) {
				pBrother->color = RED;
				pNode = pNode->parent;
			}
			else {
				if (BLACK == pBrother->right->color) {
					pBrother->color = RED;
					pBrother->left->color = BLACK;
					RIGHT_ROTATION(pTree, pBrother);
					pBrother = pNode->parent->right;
				}
				pBrother->right->color = BLACK;
				pBrother->color = pNode->parent->color;				
				pNode->parent->color = BLACK;
				LEFT_ROTATION(pTree, pNode->parent);
				pNode = pTree->root;
			}
		}
		else{
			PRBTreeNode pBrother = pNode->parent->left;
			if (RED == pBrother->color) {
				pBrother->color = BLACK;
				pNode->parent->color = RED;
				RIGHT_ROTATION(pTree, pNode->parent);
				pBrother = pNode->parent->left;
			}
			if ((BLACK == pBrother->left->color) && (BLACK == pBrother->right->color)) {
				pBrother->color = RED;
				pNode = pNode->parent;
			}
			else {
				if (BLACK == pBrother->left->color) {
					pBrother->color = RED;
					pBrother->right->color = BLACK;
					LEFT_ROTATION(pTree, pBrother);
					pBrother = pNode->parent->left;
				}
				pBrother->left->color = BLACK;
				pBrother->color = pNode->parent->color;				
				pNode->parent->color = BLACK;
				RIGHT_ROTATION(pTree, pNode->parent);
				pNode = pTree->root;
			}
		}
	}
	pNode->color = BLACK;
}

// 红黑树的节点删除
PRBTreeNode RBTREE_DELETE(PRBTree pTree, PRBTreeNode pDel)
{
	PRBTreeNode pRelDel;
	if ((PNIL == pDel->left) || (PNIL == pDel->right)) {
        pRelDel = pDel;
	}
	else { //
		pRelDel = RBTREE_SUCCESSOR(pDel);
	}

	PRBTreeNode pChildOfDel;
	pChildOfDel = (pRelDel->left!= PNIL ? pRelDel->left : pRelDel->right);

    //
	pChildOfDel->parent = pRelDel->parent;
	
	if (PNIL == pRelDel->parent) {
		pTree->root = pChildOfDel;
	}
	else {
		if (pRelDel == pRelDel->parent->left){
			pRelDel->parent->left = pChildOfDel;
		}
		else {
			pRelDel->parent->right = pChildOfDel;
		}
	}

	if (pRelDel != pDel) {
		pDel->key = pRelDel->key;
	}

	if (pRelDel->color == BLACK) {
		FIX_UP_RB_AFTER_DELETE(pTree, pChildOfDel);
	}
	return pRelDel;
}

/*=============================================*/
// 测试用函数，打印节点键值。可以传给遍历函数作为第二个参数
void PrintNode(PRBTreeNode p)
{
	if (NULL != p) {
		printf("%2d ", p->key);
	}
	else {
		printf("NULL!");
	}
}

// 打印出红黑树每个节点的各项值。
void RBTREE_STRUCTURE(PRBTreeNode pRoot)
{
#define GetKey(p) (p==PNIL?-1:p->key)
	//
	if (PNIL != pRoot) {
		printf("KeyValue = %d, color = %s, Left = %d, Right = %d, Parent = %d\n",
			pRoot->key, pRoot->color==BLACK?"BLACK":"RED", GetKey(pRoot->left), 
			GetKey(pRoot->right), GetKey(pRoot->parent));
		RBTREE_STRUCTURE(pRoot->left);
		RBTREE_STRUCTURE(pRoot->right);
	}
}

/*=============================================*/
int _tmain(int argc, _TCHAR* argv[])
{
	RBTree bsTree;
	InitRBTree(&bsTree);

#define TEST_NUM_COUNT (10)
	int values[TEST_NUM_COUNT];

	for (int i=0; i<TEST_NUM_COUNT; ++i) {
		values[i] = rand()%(TEST_NUM_COUNT*10);
		PRBTreeNode p = CreateRBTreeNode(values[i]);
        RBTREE_INSERT(&bsTree, p);
	
		
		printf("After Insert %2d:  ", values[i]);
		INORDER_RBTREE_WALK(bsTree.root, PrintNode);	
		printf("RB-Tree Nodes Information\n");
		
		RBTREE_STRUCTURE(bsTree.root);
		printf("-------------------------------\n");
	}

	printf("###############################\n");
	printf("===============================\n");

	for (int i=0; i<TEST_NUM_COUNT; ++i) {
		PRBTreeNode pDel = RBTREE_DELETE(&bsTree, RBTREE_SEARCH(bsTree.root, values[i]));
		DeleteRBTreeNode(pDel);
		printf("After Delete %2d:  ", values[i]);
		INORDER_RBTREE_WALK(bsTree.root, PrintNode);
		printf("RB-Tree Nodes Information\n");
		RBTREE_STRUCTURE(bsTree.root);
		printf("-------------------------------\n");
		
	}

	return 0;
}

 

如有建议，请email至：[e-mail]