C++ 二叉搜索树（五）红黑树的实现（1）定义与插入操作

用2篇文章实现红黑树，由于红黑树比较复杂，本篇仅说明其基本定义以及插入操作的实现，将删除操作放在下一篇。
看前须知：本文从B树的角度学习红黑树的操作。

希望你已经学过了这些知识：

1. AVL树平衡中使用的旋转操作。
2. 使用3+4重构方法在代码中实现旋转操作（如果你不在乎代码实现，这个可以不用管）
3. B树的定义、上溢和下溢处理的方法

动机：

AVL树在插入、删除数据后的平衡中进行的旋转操作次数如下：

删除操作后的重平衡次数多达$O(logn)$，花费时间太长，而红黑树保证在插入和删除后的旋转（重构）次数为$O(1)$。

基本概念

外部节点：外部节点为虚拟的NULL节点，不含数据，如下图所示，红点标注的节点，即路径上最后的节点为外部节点，外部节点的加入使得树中原来的节点都含有2个孩子，引入外部节点只是为了方便表示。

在后面的实现中外部节点都用这样的红点圆形表示。

红、黑节点：红黑树的节点染为红色或黑色。

黑深度：从根到某节点A的路径中黑节点的个数，为A的黑深度。

黑高度：从某节点A向下到外部节点的路径中黑节点的个数，为A的黑高度，外部节点黑高度0。

红黑树的限制条件：

• 根节点和外部节点均为黑色，形象地说，帽子和鞋子均为黑色
• 红节点的子必为黑节点。
• 任一外部节点到根节点的路径中黑节点个数相等。

上面的限制条件让人一头雾水，简单地说，这些条件是为了让节点的左右子树高度差大约在一倍以内，所以红黑树也可以看作条件放宽的AVL树。
B树是清晰的、直观的，而B树与红黑树关系紧密，因此接下来借用B树理解抽象的红黑树。

红黑树是4阶B树

一个红黑树例子：

你可以检查一下这棵树是否满足限制条件。

可以换个角度看这个红黑树，将红黑树中的红节点摆放到与其祖先中最近的黑节点的同一高度处，然后将同一高度中有连接的节点看成一个大节点：

红黑树中，一个黑节点至多有2个红子节点，所以对应B树的大节点中节点个数不会超过3，而每个大节点至少有1个黑节点，因此大节点中的节点个数为1-3个，满足4阶B树的要求，这就是一个4阶B树。

在B树大节点中：

• 含1个数据的节点必一黑
• 含2个数据的节点必一黑一红
• 含3个数据的节点中间必为红黑红

含有不属于上面3种情况的节点的B树所对应的红黑树必然是不满足限制条件的，因此可借助B树判断红黑树是否合格（判断红黑树转成的B树中是否含有不属于上述3种节点的其他节点）。

代码实现

红黑树的实现基于第一篇中的基本二叉搜索树BST。

API

宏

提供简单功能的一些宏：

// 获得节点的黑高度，若为空节点(外部节点)，则高度为0
#define getHeight(node) ((node) ? (node)->height : 0)
// 定义颜色，提高可读性
#define black 1
#define red 0
// 判断节点的颜色，空节点为黑色
#define isBlack(node) ((!node)||((node)->color == black))
#define isRed(node) (!isBlack(node))

Node

节点类与第一篇中的基本一致，仅修改了如下内容：

• 添加了一个bool color，表示节点的颜色。
• 这里的height不再表示高度，而是黑高度。

下面仅列出了与本篇相关的内容：

class Node
{
	// 为了突出重点，还有一些其他的友元类没有列出，都是之前出现过的
	friend class RBTree;
private:
	int data;
	Node* parent;
	Node* left, * right;
	int height;
	bool color; // 0-red 1-black
public:
	Node(int d = 0, Node* p = NULL, Node* l = NULL, Node* r = NULL, 
         int h = 0, int c = red)
	: data(d), parent(p), left(l), right(r), height(h), color(c) {};

	bool isRight() const;
	bool isLeft() const;
};

函数的具体实现不在这里重复贴出了。

RBTree

继承了之前的BST。

class RBTree : public BST
{
protected:
	void doubleRed(Node* node);
	void doubleBlack(Node* node);
	
	int updateHeight(Node* node);
	
	Node* rotateAt(Node* v);
	Node* connect34(Node* a, Node* b, Node* c,
			   Node* T0, Node* T1, Node* T2, Node* T3);
public:
	Node*& insert(int data);
	bool remove(int data);
};

说明：

• 红黑树的查询操作与普通二叉搜索树完全一致，因此直接调用BST::search方法。

• insert和remove为插入和删除操作。

• updateHeight更新节点的黑高度，而不是高度，红黑树中使用黑高度，这与普通的搜索树不同。

• doubleRed和doubleBlack用于调整不满足限制条件的红黑树。

• rotateAt和connect34为3+4重构方法（具体可以看网上的其他资料或第二篇），用于doubleRed和doubleBlack中。

更新黑高度

updateHeight在这里更新黑高度，而不是高度，比较简单：

int RBTree::updateHeight(Node* node)
{
	// 空节点默认为外部节点，黑高度0
	if (!node) return 0;
	node->height = max(getHeight(node->left), getHeight(node->right));
	if (isBlack(node)) ++node->height;
	return node->height;
}

插入操作与双红现象

insert

插入操作很简单，先用BST::search方法查找插入的位置，如果数据已经有了，就直接返回，否则创建新节点。

注意：除根节点外创建的新节点默认为红节点，因为这样的话，红黑树的限制条件中只有 “红节点的子必为黑节点” 这一条可能不满足。

主方法：

Node*& RBTree::insert(int data) {
	Node*& node = search(data);
	if (node) return node;
	// 若hot_为NULL, 即插入的为树根，颜色为黑，黑高度1
	if (!hot_) node = new Node(data, hot_, NULL, NULL, 1, black);
	// 否则，插入的为树叶，默认颜色为红，黑高度0
	else {
		node = new Node(data, hot_, NULL, NULL, 0, red);
		// 检查是否有双红现象并修正
		doubleRed(node);
	}
	++size_;
	return node;
}

在插入数据后使用doubleRed检查树是否满足限制条件，如果不满足就进行调整。

双红现象及修正

设新插入节点为v，其父节点为p，p的兄弟为u，如果p为黑，显然红黑树的所有条件都满足，不需要额外的处理。

如果p为红节点，那么此时v与p都为红，不满足限制条件。

既然插入之前红黑树合法，那么p之父g必为黑节点，不满足的情况下节点u颜色只有两种：

• u为外部节点(NULL)，即黑节点
• u为红节点

1. 叔叔节点u为黑节点（外部节点）

一种可能（根据v、p、g的左右位置共4种可能）如下图所示：

为了方便理解如何修改，我们可以采用迂回的方法，先将上面的红黑树用B树的形式（省去次要节点）表示如下：

由之前的分析可知，3数据节点必须为红黑红，此时不符合要求，只需修改g与v的颜色，就可以在B树中合格：

将上图大节点转换回红黑树：

新的红黑树也是满足限制条件的，调整完成。

至此，我们可以说，只需将一开始的红黑树转换成上图的红黑树，红黑树就恢复正确了，至于转换的方法，正是AVL树中已经学习过的旋转，就上面的情况来说，使用的是右左旋，然后只需重新染色，就可以得到新树。

v、p、g的相对位置有4种不同的可能，上面只举了一种，对于其他3种，只需根据具体情况使用不同方向的旋转即可。

2. 叔叔节点u为红节点

一种可能（根据v、p、g的左右位置共4种）如下图所示：

将上图红黑树转为B树：

显然大节点发生了上溢（超过了3），那么对该节点进行上溢处理，将g提升至上一层，同时分裂原来的大节点：

此时g被加入了上面一层的大节点中，但只有红节点才可以这样做，因此g应该改为红色，染色如下：

恢复至红黑树：

与一开始比较，仅仅是u、g和p节点的颜色发生了改变，因此该种情况下所做的仅仅是修改节点的颜色，不需要旋转操作。

要注意的是，下面这个节点

可能是这种情况：

在上一层可能会再次发生该情况，因此需要递归的不断向上处理至多logn次。

该种情况下需要的操作如下：

• 染色
• 向上层继续检查，至多logn次。

尽管可能检查$logn$次，但旋转操作的次数仍是$O(1)$的，因为只有第一种情况会发生旋转，而第一种情况修复后红黑树必然已经完全修复，不用再次向上递归了。

doubleRed：

void RBTree::doubleRed(Node* node) {
	Node* parent = node->parent;
	// 如果node父为黑，则不用调整
	if (isBlack(parent)) return;
	Node* grand = parent->parent;
	// 获得node的叔叔节点
	Node* uncle = (parent->isLeft()) ? grand->right : grand->left;
	// 如果uncle为黑, 需旋转和染色
	if (isBlack(uncle)) { // 这种情况下操作后 黑高度与未插入数据前相等
		// 提前记录
		Node* gp = grand->parent;
		// 旋转
		Node* p = rotateAt(node);
		// 统一染色，根为黑，左右都为红
		
        // 更新颜色和高度
		p->left->color = red;
		updateHeight(p->left);
		p->right->color = red;
		updateHeight(p->right);
		p->color = black;
		updateHeight(p);
		
		// 若grand有父节点，即grand不为根
		if (gp) {
			// 则在gp中更新
			if (gp->left == grand) gp->left = p;
			else gp->right = p;
		}
		// 若grand为根，则更新根
		else root_ = p;
	}
	// uncle为红, 需3次染色和向上继续检查
	else {
		uncle->color = black;
		// 黑高度+1
		++uncle->height;
		parent->color = black; 
		// 黑高度+1
		++parent->height;
		// 若grand为根， 则根的黑高度+1
		if (root_ == grand) ++grand->height;
		// 若grand不为根，则染为红色
		else grand->color = red;
		// 上一层可能还会发生双红缺陷，继续检查
		doubleRed(grand);
	}
}

所有二叉搜索树的代码已上传github，sir, this way.