高阶数据结构 ＜红黑树＞

本文已收录至《数据结构(C/C++语言)》专栏！
作者：ARMCSKGT

目录

• 前言
• 正文
• • 红黑树简介
  • 红黑树整体结构
  • 红黑树节点的定义
  • 红黑树主体类设计
  • 红黑树的插入函数
  • • 情况一：变色
    • 情况二：变色+旋转
    • • 单旋情况
      • 双旋情况
    • 完整插入代码
  • 关于红黑树
  • • 红黑树检验
    • 红黑树 vs AVL树
• 最后

前言

红黑树是二叉搜索树的一种，但是红黑树是性能最均衡应用场景最广的一种二叉搜索树，相对于AVL树来说，红黑树在旋转条件上并不是很严格，但是依然可以有非常出色的查找性能，这得益于红黑树的性质，本节将为大家介绍红黑树的基本性质。

正文

本文相关知识点：二叉搜索树(搜索树性质)，AVL树(旋转相关)
如果大家对二叉搜索树性质不熟悉或者对树的旋转调整不熟悉，可以先移步这两篇文章就行了解！

红黑树简介

红黑树是在1972年由Rudolf Bayer发明的，当时被称为平衡二叉B树（symmetric binary B-trees）。后来，在1978年被 Leo J. Guibas 和 Robert Sedgewick 修改为如今的“红黑树”。

红黑树，是一种二叉搜索树，但在每个结点上增加一个存储位表示结点的颜色，可以是Red或Black。 通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路径会比其他路径长出俩倍，因而是接近平衡的。

前面我们介绍了AVL树，AVL树有着极其严格的平衡标准，这使得AVL树在某些极端情况下可能会频繁旋转导致插入和删除性能下降，而红黑树只有在极度不平衡下才会调整，对于红黑树来说，极度不平衡就是最长路径大于最短路径的两倍！

红黑树的性质：

• 每个节点不是黑色就是红色
• 根节点是黑色
• 如果一个节点是红色的，则它的两个孩子结点是黑色的（不存在连续的红色节点，例如父子节点都是红色）
• 每条路径上叶子节点都是黑色的（红黑树中空节点NIL可以理解为叶子节点，这个叶节点没有特殊意思，方便判断）
• 每条路径上的黑色节点数量相同

按照红黑树的性质，可以知道：

上图中，如果是AVL树就需要进行左单旋降低高度，而红黑树则不需要调整。
可以说，最短路径是全黑节点，最长路径是红黑相间。
因为最长路径的节点数量不能超过最短路径节点数量的两倍，所以 黑节点数量大于等于红节点数量。

我们一般在使用容器时，增删查改是都会出现的，如果使用AVL树，查找性能非常好，但是插入性能就一般了，所以一般语言标准中的容器都会使用红黑树，性能比较均衡，而AVL树则时候那些只读的静态数据，专门用于查询！

关于实际的性能差距，假设二叉树有n个节点，AVL树查询的时间复杂度为O()；红黑树查询的最优效率为O()，最差效率为O()。和这两个数值的差距，对于计算机来说可以忽略不计，假设有10亿，也仅仅是30和60次查找的差别！

红黑树整体结构

红黑树需要定义节点，比较函数和红黑树类主体，所以分为三部分，封装在红黑树命名空间中！

对于比较函数，我们使用仿函数控制，使用模板参数传参，默认K类型参数为比较对象，使用者也可以自己按要求实现比较函数，按自己的比较规则控制红黑树。

同时，我们在头文件中实现，为了防止重复包含，使用 #ifndef~#endif 来就行条件编译。

#ifndef RB_TREE
#define RB_TREE
#include <iostream>

namespace RB_Tree
{
	typedef bool Color;         //重定义定义bool为颜色类型
	const bool RED = true;      //定义 true 为 RED 常量值 对应红色节点
	const bool BLACK = false;   //定义 false 为 BLACK 常量值 对应黑色节点
	template<class K, class V>
	struct RBTreeNode
	{
		//红黑树节点成员
	};

	//默认比较仿函数
	template<class T>
	struct less { bool operator()(const T& left, const T& right) { return left < right; } };
	template<class T>
	struct greater { bool operator()(const T& left, const T& right) { return left > right; } };

	//红黑树类主体
	template<class K, class V, class Compare = less<K>>
	class RBTree
	{
		//红黑树类主体成员
	};
}

#endif // !RB_TREE

红黑树节点的定义

红黑树依然是三叉链结构，需要一个父节点指针，同时有一个颜色节点来区分红黑节点。
这里红黑节点采用bool值区分，true为红，false为黑。

代码：

struct RBTreeNode
{
	typedef std::pair <K, V> val_type;
	RBTreeNode()
		: _parent(nullptr)
		, _left(nullptr)
		, _right(nullptr)
		, _col(RED)
	{}

	RBTreeNode(const val_type& data)
		: _parent(nullptr)
		, _left(nullptr)
		, _right(nullptr)
		, _data(data)
		, _col(RED)
	{}

	RBTreeNode<K, V>* _parent;
	RBTreeNode<K, V>* _left;
	RBTreeNode<K, V>* _right;
	val_type          _data;
	Color			  _col; //bool类型 true=red false=black
};

关于节点的默认颜色：
新节点的插入，有可能会违反规则，分为下面两种情况：

• 如果是插入黑节点，那么所有路径的黑色节点不相等，此时需要花费大量时间对黑色节点进行调整！
• 如果是插入红色节点，则会造成连续红色节点的的出现，需要变色和旋转。

对于上面的情况，我们必须选择违背其中一个，然后想办法恢复，怎么选择取决于那个的恢复成本比较小。
如果是选择插入黑节点，那么一个节点的插入可能会影响所有路径的黑色节点（全局影响），如果是插入红色节点，最坏的情况仅需要旋转到根即可（局部影响），显而易见，插入红节点的恢复成本更小，如果需要调整所有路径的黑色节点，是非常复杂的！

控制红色节点是必然，如果出现连续的红色节点，那么就不能保证红黑相间，最长路径必然大于最短路径的两倍，而每条路径上黑色节点数量相同，即使是出现连续的黑色节点，在同一层都是连续的，那么每条路径的黑色节点也相同，性质可以得以维持！

所以我们默认插入红色节点，然后对其进行局部调整！

红黑树主体类设计

红黑树类主体对pair<K,V>对象重定义为val_type，对RBTreeNode<K, V>重定义为Node，方便使用。
其成员变量只需要一个根节点指针_root，一个_size记录节点数量，一个_com比较函数即可。
为了防止内存泄漏，我们事先实现了节点释放函数，使用 后序遍历+递归 逐一删除节点。

//红黑树类主体设计
template<class K, class V, class Compare = less<K>>
class RBTree
{
	typedef std::pair <K, V> val_type;
	typedef RBTreeNode<K, V> Node;
public:
	RBTree()
		:_root(nullptr)
		, _size(0)
	{}

	~RBTree()
	{
		DelTree(_root);
		_root = nullptr;
	}

private:
	//删除树
	void DelTree(Node* root)
	{
		if (root == nullptr) return;
		DelTree(root->_left);
		DelTree(root->_right);
		delete root;
	}

private:
	Node* _root;  //根节点
	size_t _size; //节点数量
	Compare _com;  //比较函数
};

我们自己实现的红黑树，与STL库中的有一定区别，我们主要介绍插入思想，插入思想上与库中基本相似，但是在结构设计上有一定区别，这里要提一下的是，STL中的红黑树有一个头节点，其左子树指针指向树中的最小值节点（最左节点），右子树指针指向最大值节点（最右节点），这样好处在于，设计迭代器时，遍历不需要找最左和最右节点，以及对遍历到结尾的条件判断要简单一点，但是我们这里主要介绍红黑树的插入原理，所以使用简单的结构就行。

红黑树的插入函数

红黑树的插入流程与二叉搜索树相似，只不过多了调整环节。

插入流程：

• 判断根节点是否为空，如果为空则直接插入根节点
• 找最合适的插入位置（插入到哪个父节点下），与每个节点相比较，通过比较函数决定向左子树走还是向右子树走
• 找到合适的父节点后，通过比较函数选择插入到父节点的左边还是右边
• 判断父节点颜色，决定是否需要染色或调整

为了方便理解，我们先介绍一下节点关系，一张图说明：

代码：

pair<val_type, bool> insert(const val_type& data)
{
	//为空插入根节点
	if (nullptr == _root)
	{
		Node* newnode = new Node(data);
		_root = newnode;
	}
	else //否则开始找插入位置
	{
		Node* newnode = new Node(data);
		Node* parent = _root;
		Node* cur = _root;
		while (cur)
		{
			if (_com(data.first, cur->_data.first))      // <
			{
				parent = cur;
				cur = cur->_left;
			}
			else if (_com(cur->_data.first, data.first)) // >
			{
				parent = cur;
				cur = cur->_right;
			}
			else return { data,false };      // ==
		}
		//新节点插入合适的父节点下
		if (_com(data.first, parent->_data.first)) parent->_left = newnode;
		else parent->_right = newnode;
		newnode->_parent = parent;
		cur = newnode;

		//开始调整
		while (parent && parent->_col == RED)
		{
			//祖父节点
			Node* grandfather = parent->_parent;
			//叔叔节点
			Node* uncle = nullptr;
			//调整 ... 
		}
	}

	++_size;
	_root->_col = BLACK; //无论怎么调整 根节点总是黑色
	return { data,true };
}

说明：

• 插入函数的返回值为pair对象key-value类型，表示数据data是否插入成功，插入成功时second为true，失败则为false。
• 每次成功插入节点时，都将_size+1，用作计数（如果设计返回节点数量的接口，该变量可以大大优化效率，否则需要对整棵树进行遍历）。
• 每次插入成功返回前都将根节点_root的颜色置为BLACK，以确保根节点一直为黑（染色调整可能会修改根节点颜色）。

关于调整：
调整的关键是看 父节点 和 叔叔节点 ！

• 如果父节点为黑节点，则直接插入，不需要进行任何调整
• 如果父节点为红色，则需要去看叔叔节点，如果叔叔节点也为红色，则直接变色然后继续向上调整即可
• 如果父节点为红色，叔叔节点为黑色或不存在，则需要进行 旋转+变色 调整。

因为左区间和右区间的判断条件对称，所以我们左右一起介绍。

下面介绍时因为祖父单词过长，简写为gf！

情况一：变色

父节点和叔叔节点都为红色此时需要变色
如果新节点插入后，父节点（parent）和叔叔节点（uncle）的颜色都为黑色，则可以将父节点和叔叔节点变为黑色，祖父节点（grandfather）变为红色来解决！

不过在变色后，如果祖父节点是其他树的子树，则需要继续向上调整，将祖父节点作为新插入节点继续检查，因为祖父节点变成红色后可能其曾祖父也是红色，此时还需要继续判断和调整，如果曾祖父是黑色或不存在，则停止调整即可！

if (grandfather->_left == parent)
{
	//父节点是祖父的左 叔叔就是祖父的右
	uncle = grandfather->_right;
	if (uncle && uncle->_col == RED)
	{
		grandfather->_col = RED;
		parent->_col = uncle->_col = BLACK;
		uncle->_col = BLACK;
		//继续检查和调整
		cur = grandfather;
		parent = grandfather->_parent;
	}
	else if (uncle == nullptr || uncle->_col == BLACK)
	{
		//旋转+染色
	}
}
else if (grandfather->_right == parent)
{
	//父节点是祖父的右 叔叔就是祖父的左
	uncle = grandfather->_left;
	if (uncle && uncle->_col == RED)
	{
		grandfather->_col = RED;
		parent->_col = BLACK;
		uncle->_col = BLACK;
		//继续检查和调整
		cur = grandfather;
		parent = grandfather->_parent;
	}
	else if (uncle == nullptr || uncle->_col == BLACK)
	{
		//旋转+染色
	}
}

这里主要是通过祖父指针分辨父节点和叔叔节点的位置，以做不同操作！

情况二：变色+旋转

叔叔不存在或叔叔为黑色此时需要旋转和变色
有些情况下染色并不能保持性质，此时需要旋转降低高度！
情况二可以由情况一产生，变色后祖父和曾祖父为连续的红色节点！

在AVL树中，旋转分为单旋和双旋，如果插入在左子树的左和右子树的右，不平衡的情况直接分别进行右单旋和左单旋即可；如果插入在左子树的右和右子树的左，不平衡的情况直接分别进行左右双旋和右左双旋即可！

涉及旋转都需要注意新增节点的插入位置，才能进行对应的旋转！

旋转后就需要调整节点的颜色，以符合红黑树的性质！
当旋转和染色结束后，直接跳出调整即可，不需要继续向上检测！

单旋情况

如果插入位置在左子树的左和右子树的右且叔叔节点不存在或存在且为黑节点，此时需要进行单旋和变色调整！

图示：

左单旋+染色

右单旋+染色

代码：

if (grandfather->_left == parent)
{
	uncle = grandfather->_right;
	if (uncle && uncle->_col == RED)
	{
		//单纯染色
	}
	else if (uncle == nullptr || uncle->_col == BLACK)
	{
		if (parent->_left == cur)
		{
			//右单旋
			RotateR(grandfather);
			parent->_col = BLACK;
			grandfather->_col = RED;
		}
		else if (parent->_right == cur)
		{
			//左右双旋
		}
		//旋转完后整树平衡 直接跳出
		break;
	}
}
else if (grandfather->_right == parent)
{
	uncle = grandfather->_left;
	if (uncle && uncle->_col == RED)
	{
		//单纯染色
	}
	else if (uncle == nullptr || uncle->_col == BLACK)
	{
		if (parent->_right == cur)
		{
			//左单旋
			RotateL(grandfather);
			grandfather->_col = RED;
			parent->_col = BLACK;
		}
		else if (parent->_left == cur)
		{
			//右左双旋
		}
		//旋转完成后整树趋于平衡
		break;
	}
}

双旋情况

如果插入位置在左子树的右和右子树的左且叔叔节点不存在或存在且为黑节点，此时需要进行双旋和变色调整！

图示：

右左双旋+变色

右左双旋+变色

代码：

if (grandfather->_left == parent)
{
	uncle = grandfather->_right;
	if (uncle && uncle->_col == RED)
	{
		//染色+调整
	}
	else if (uncle == nullptr || uncle->_col == BLACK)
	{
		if (parent->_left == cur)
		{
			//右单旋+染色
		}
		else if (parent->_right == cur)
		{
			//左右双旋+染色
			RotateL(parent);
			RotateR(grandfather);
			cur->_col = BLACK;
			grandfather->_col = RED;
		}
		//旋转完后整树平衡 直接跳出
		break;
	}
}
else if (grandfather->_right == parent)
{
	uncle = grandfather->_left;
	if (uncle && uncle->_col == RED)
	{
		//染色+调整
	}
	else if (uncle == nullptr || uncle->_col == BLACK)
	{
		if (parent->_right == cur)
		{
			//左单旋+变色
		}
		else if (parent->_left == cur)
		{
			//右左双旋+染色
			RotateR(parent);
			RotateL(grandfather);
			grandfather->_col = RED;
			cur->_col = BLACK;
		}
		//旋转完成后整树趋于平衡
		break;
	}

完整插入代码

pair<val_type, bool> insert(const val_type& data)
{
	if (nullptr == _root)
	{
		Node* newnode = new Node(data);
		_root = newnode;
	}
	else
	{
		Node* newnode = new Node(data);
		Node* parent = _root;
		Node* cur = _root;
		while (cur)
		{
			if (_com(data.first, cur->_data.first))      // <
			{
				parent = cur;
				cur = cur->_left;
			}
			else if (_com(cur->_data.first, data.first)) // >
			{
				parent = cur;
				cur = cur->_right;
			}
			else return { data,false };      // ==
		}

		if (_com(data.first, parent->_data.first)) parent->_left = newnode;
		else parent->_right = newnode;
		newnode->_parent = parent;
		cur = newnode;

		while (parent && parent->_col == RED)
		{
			//祖父节点
			Node* grandfather = parent->_parent;
			//叔叔节点
			Node* uncle = nullptr;
			//调整
			if (grandfather->_left == parent)
			{
				uncle = grandfather->_right;
				if (uncle && uncle->_col == RED)
				{
					grandfather->_col = RED;
					parent->_col = uncle->_col = BLACK;
					uncle->_col = BLACK;
					//继续染色
					cur = grandfather;
					parent = grandfather->_parent;
				}
				else if (uncle == nullptr || uncle->_col == BLACK)
				{
					if (parent->_left == cur)
					{
						//右单旋
						RotateR(grandfather);
						parent->_col = BLACK;
						grandfather->_col = RED;
					}
					else if (parent->_right == cur)
					{
						//左右双旋
						RotateL(parent);
						RotateR(grandfather);
						cur->_col = BLACK;
						grandfather->_col = RED;
					}
					//旋转完后整树平衡 直接跳出
					break;
				}
			}
			else if (grandfather->_right == parent)
			{
				uncle = grandfather->_left;
				if (uncle && uncle->_col == RED)
				{
					grandfather->_col = RED;
					parent->_col = BLACK;
					uncle->_col = BLACK;
					//继续染色
					cur = grandfather;
					parent = grandfather->_parent;
				}
				else if (uncle == nullptr || uncle->_col == BLACK)
				{
					if (parent->_right == cur)
					{
						//左单旋
						RotateL(grandfather);
						grandfather->_col = RED;
						parent->_col = BLACK;
					}
					else if (parent->_left == cur)
					{
						//右左双旋
						RotateR(parent);
						RotateL(grandfather);
						grandfather->_col = RED;
						cur->_col = BLACK;
					}
					//旋转完成后整树趋于平衡
					break;
				}
			}

		}
	}

	++_size;
	_root->_col = BLACK; //无论怎么调整 根节点总是黑色
	return { data,true };
}

关于红黑树

红黑树检验

我们实现红黑树后，还需要对其规则进行检验，防止bug导致红黑树结构异常！

检验规则：

• 根节点是否为黑色姐
• 是否出现连续的红色节点
  – 说明：如果我们先判断当前节点再判断子节点，就需要对子节点进行分类判断，很麻烦。此时我们需要转换思想，先判断子树是否为红再判断父节点，因为根节点为黑所以不会访问根节点的父级指针，也就是不会访问空指针，而后的子树必有父节点，所以我们只需要判断当前节点是否为红，如果为红再去判断父节点，红节点一定有父节点。
• 每条路径的黑色节点数量是否相等
  –说明：既然是每条路径都相等，我们随意找一条路径取基准值（例如取最左路径或最右路径的黑节点数量），然后去与每条路径进行对比，全相等就符合要求。

//检验函数 调用接口
bool isRBTree()
{
	//三个条件
	//没有连续红色节点
	//每条路上的黑色节点数相等
	if (_root == nullptr) return true;
	if (_root && _root->_col == RED) return false;
	int blackmark = 0;
	Node* cur = _root;
	while (cur)
	{
		if (cur->_col == BLACK) ++blackmark;
		cur = cur->_right;
	}

	return _isRBTree(_root, blackmark, 0);
}

//检验函数 执行接口
bool _isRBTree(Node* root, const int blackmark, int blacknum)
{
	if (root == nullptr)
	{
		if (blackmark != blacknum)
		{
			cout << "黑节点数不相等！" << endl;
			return false;
		}
		return true;
	}

	if (root->_col == BLACK) ++blacknum;
	else if (root->_parent && root->_parent->_col == RED)
	{
		cout << "出现连续的红色节点！" << endl;
		return false;
	}

	return _isRBTree(root->_left, blackmark, blacknum) && _isRBTree(root->_right, blackmark, blacknum);
}

有序插入1-10000的数，查看情况：

可以发现，插入有序序列下，最大和最小层数正好相差二倍，但是仍然合格！

红黑树 vs AVL树

我们将两棵树进行性能对比，插入1-100w节点，查看耗时！
检查代码：

void randominsert(const int N)
{
	srand(time(nullptr));
	cout << "随机数据插入！" << endl;
	RB_Tree::RBTree<int, int> rbt;
	AVLTree::AVLTree<int, int> avl;
	clock_t start = clock();
	for (int i = 1; i <= N; ++i) avl.insert({ rand() % i + i,i });
	clock_t end = clock();
	cout << "AVLTree：" << end - start << "ms" << endl;
	avl.~AVLTree();

	start = clock();
	for (int i = 1; i <= N; ++i) rbt.insert({ rand() % i + i,i });
	end = clock();
	cout << "RBTree：" << end - start << "ms" << endl;

}

void orderlyinsert(const int N)
{
	cout << "有序数据插入！" << endl;
	RB_Tree::RBTree<int, int> rbt;
	AVLTree::AVLTree<int, int> avl;

	clock_t start = clock();
	for (int i = 1; i <= N; ++i) avl.insert({ i,i });
	clock_t end = clock();
	cout << "AVLTree：" << end - start << "ms" << endl;
	avl.~AVLTree();

	start = clock();
	for (int i = 1; i <= N; ++i) rbt.insert({ i,i });
	end = clock();
	cout << "RBTree：" << end - start << "ms" << endl;


}

int main()
{
	const int N = 1000000;
	randominsert(N);
	cout << endl;
	orderlyinsert(N);
	return 0;
}

在测试中，我们插入随机节点，发现红黑树与AVL相差不大，而插入有序节点，AVL树反而比红黑树性能要好，所以不同情况两树性能有区别。
这里我们只实现了插入，还有增删改查等一系列的操作，都进行的话，红黑树平均性能会超过AVL树！

注意：实际对比下，因为数据量问题可能出现AVL树性能比红黑树好的情况，这种属于正常现象，单比插入不能真实体现全部性能！

最后

本节红黑树的介绍到这里就告一段落了，当我们完全了解红黑树后，发现其实红黑树比较抽象，但是比AVL树好控制，而我们的STL容器中map和set使用的底层数据结构就是红黑树，后面我们将为大家介绍库中红黑树的使用以及map和set的基本封装！

本次 <红黑树> 就先介绍到这里啦，希望能够尽可能帮助到大家。

如果文章中有瑕疵，还请各位大佬细心点评和留言，我将立即修补错误，谢谢！

本节涉及代码：红黑树博客代码

🌟其他文章阅读推荐🌟
高级数据结构＜AVL树＞
高级数据结构＜二叉搜索树＞
数据结构初级＜二叉树＞
C++ <继承>
C++ <多态>
🌹欢迎读者多多浏览多多支持!🌹