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

开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> C++知识库 -> C++ 二叉搜索树（五）红黑树的实现（1）定义与插入操作 -> 正文阅读

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

本篇和下一篇实现红黑树。

由于红黑树比较复杂，本篇仅说明其基本定义以及插入操作的实现，将删除操作放在下一篇。

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

AVL树的平衡中使用的旋转操作
使用3+4重构方法代码实现1的旋转操作
B树的定义、上溢和下溢处理的方法

动机：

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

	插入操作后	删除操作后
旋转次数	$O (1)$	$O (l o g n)$

删除操作后的重平衡次数多达 $O (l o g n)$ ，花费时间太长，而红黑树保证在插入和删除后的重平衡次数为 $O (1)$ 。

文章目录

基本概念

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

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

红、黑节点：在普通二叉搜索树的基础上，红黑树的节点被染为红色或黑色。

黑深度：从根到节点A路径中除去根节点后黑节点的个数，为A的黑深度，根节点黑深度0。

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

红黑树的限制条件：

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

上面的限制条件让人一头雾水，下面借助B树理解一下。

红黑树是4阶B树

一个红黑树例子：

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

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

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

在对应的B树中：

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

含有与上面3种情况不同的节点的B树所对应的红黑树必然是不满足限制条件的，因此可借助B树判断红黑树是否合格。

代码实现

红黑树的实现基于第一篇中的基本二叉搜索树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方法。
updateHeight更新节点的黑高度，而不是高度，红黑树中使用黑高度，这与普通的搜索树不同。
doubleRed和doubleBlack用于处理插入和删除数据后红黑树不满足限制条件的情况。
insert和remove为插入和删除操作。
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为黑节点，显然红黑树的所有条件都满足，不需要额外的处理。

如果p为红节点，那么此时v与p都为红，不满足限制条件，下面分2种情况处理：

注意：既然插入前的红黑树合法，那么p之父g必为黑节点。

1. 叔叔节点u为黑节点

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

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

v与p在大节点中相邻，此时的大节点不符合要求，合格的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次。

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);
	}
}