【数据结构】红黑树-EW帮帮网

红黑树（ $Red\ Black\ Tree$ ）是一种自平衡二叉搜索树，也可以看作一种特化的 $A V L$ 树（通过颜色规则来实现自平衡功能），都是在进行插入和删除操作时通过特定操作保持二叉搜索树的平衡，从而获得 $O(\log N)$ 的查找性能，在 $C$ ++ $ST L$ 标准库中， $ma p$ 和 $se t$ 的底层结构就是红黑树。

文章目录

一、红黑树的概念
- 1. 基本规则
- 2. 红黑树的效率
二、红黑树的基本操作
三、红黑树的实现
总结

一、红黑树的概念

红黑树是一棵二叉搜索树，他的每个结点增加一个存储位来表示结点的颜色，可以是红色或者黑色。通过对任何一条从根到叶子的路径上各个结点的颜色进行约束，红黑树确保没有一条路径会比其他路径长出 $2$ 倍，因而是接近平衡的。

在这里插入图片描述

1. 基本规则

红黑树（ $RB - t ree$ ）不仅仅是一个二叉搜索树，其要求和 $A V L$ 树类似，要达到自平衡的效果，因此，其通过约束每个结点的颜色来实现平衡，也就是说必须满足以下四条规则：

【规则 $1$ 】每个结点不是红色就是黑色。

【规则 $2$ 】根结点是黑色的。

【规则 $3$ 】如果一个结点是红色的，则它的两个孩子结点必须是黑色的，也就是说任意一条路径不会有连续的红色结点。

【规则 $4$ 】对于任意一个结点，从该结点到其所有 $N ULL$ 结点的简单路径上，均包含相同数量的黑色结点。

比如说，下图就是一个经典的红黑树（每条路径的黑色结点个数都为 $2$ 个）：

在这里插入图片描述

思考一下，红黑树如何确保最长路径不超过最短路径的 $2$ 倍的呢？

由【规则 $4$ 】可知，从根到 $N ULL$ 结点的每条路径都有相同数量的黑色结点，所以极端场景下，最短路径就是全是黑色结点的路径，假设每条路径的黑色结点数量为 $x$ 个，最短路径长度为 $bh$ （ $black\ height$ ），那么 $bh = x$ 。

在这里插入图片描述

由【规则 $2$ 】和【规则 $3$ 】可知，任意一条路径不会有连续的红色结点，所以极端场景下，最长路径就是一黑一红间隔组成的路径，那么最长路径的长度为 $2\cdot bh$ 。

在这里插入图片描述

综合红黑树的 $4$ 点规则而言，理论上的全黑最短路径和一黑一红的最长路径并不是在每棵红黑树都存在的。假设任意一条从根结点到 $N ULL$ 结点的路径长度为 $h$ ，那么 $\le h \le 2\cdot bh$ 。

在这里插入图片描述

2. 红黑树的效率

红黑树的表达相对 $A V L$ 树要抽象一些， $A V L$ 树通过高度差直观的控制了平衡，红黑树则通过 $4$ 条规则的颜色约束，间接的实现了近似平衡，他们效率都是同一档次（时间复杂度都是 $O(\log N)$ ），但是相对而言，插入相同数量的结点，红黑树的旋转次数是更少的，因为他对平衡的控制没那么严格。

在这里插入图片描述

假设 $N$ 是红黑树树中结点数量， $h$ 最短路径的长度，那么就可以得到：

$2^h − 1 \le N \le 2^{2\cdot h} − 1$

由此推出：

$\log N$

也就是意味着红黑树增删查改最坏也就是走最长路径 $2\cdot \log N$ ，那么时间复杂度还是 $O(\log N)$ 。

二、红黑树的基本操作

1. 基本结构

红黑树本质上也是一棵自平衡二叉搜索树，其结点存的是一个三叉链，也就是说其不仅要存储左右子树的根结点，还要存储其父结点，以及每个结点的颜色（这里用枚举 $e n u m$ 结构来存储所有可能的颜色）。

// 枚举值表示颜色
enum color
{
	red,
	black
};

template<class K, class V>
struct RBTreeNode
{
	pair<K, V> _kv;				// 每个结点存储的值
	RBTreeNode<K, V>* _left;	// 左子树
	RBTreeNode<K, V>* _right;	// 右子树
	RBTreeNode<K, V>* _parent;	// 父结点
	color _col;					// 每个结点的颜色

	RBTreeNode(const pair<K, V>& kv)
		:_kv(kv)
		, _left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
		, _col(red)
	{}
};

template<class K, class V>
class RBTree
{
	typedef RBTreeNode<K, V> node;
public:
	// ...
private:
	node* _root = nullptr;
};

2. 插入操作

由于红黑树的本质是一棵自平衡二叉搜索树，因此插入一个值可以按二叉搜索树规则进行插入：

bool insert(const pair<K, V>& kv)
{
	if (_root == nullptr)
	{
		_root = new node(kv);
		_root->_col = black;
		return true;
	}
	
	node* parent = nullptr;
	node* cur = _root;
	while (cur)
	{
		if (kv.first < cur->_kv.first)
		{
			parent = cur;
			cur = cur->_left;
		}
		else if (kv.first > cur->_kv.first)
		{
			parent = cur;
			cur = cur->_right;
		}
		else
		{
			return false;
		}
	}
	cur = new node(kv);
	if (kv.first < parent->_kv.first)
	{
		parent->_left = cur;
	}
	else
	{
		parent->_right = cur;
	}
	cur->_parent = parent;

	// 维持平衡操作
	// ...
	
	_root->_col = black;
	return true;
}

2.1 插入的过程

说明：下面我们假设把新增结点标识为 $c$ （ $c u r$ ）， $c$ 的父亲标识为 $p$ （ $p a re n t$ ）， $p$ 的父亲标识为 $g$ （ $g r an df a t h er$ ）， $p$ 的兄弟标识为 $u$ （ $u n c l e$ ）。

在这里插入图片描述

为了维持整棵树的平衡，插入后我们需要观察是否符合红黑树的 $4$ 条规则：

如果是空树插入，新增结点必须是黑色结点（根）。如果是非空树插入，新增结点必须是红色结点，因为非空树插入，新增黑色结点就破坏了【规则 $4$ 】，【规则 $4$ 】是很难维护的。
如果插入后父亲结点是黑色的，则没有违反任何规则，插入结束。
如果插入后父亲结点是红色的，则违反【规则 $3$ 】。进一步分析， $c$ 是红色， $p$ 为红色， $g$ 必为黑色，这三个颜色都固定了，关键的变化看 $u$ 的情况，需要根据 $u$ 分为以下两种情况分别处理：

	  黑		  黑		  黑		  黑		
     /  \ 		 /  \		 /  \ 	   	 /  \		
   红    u      红    u	  	u	 红     u    红		
  / 			 \		   	    /			  \		
红			      红		  红			   红

2.2 情况一：变色

情况 $1$ ： $u$ 存在且为红色，则只变色，不旋转。所以无论 $c$ 是 $p$ 的左还是右， $p$ 是 $g$ 的左还是右，都是下面的变色处理方式：

	g			g			g			g		
   / \ 		   / \		   / \ 		   / \		
  p   u  	  p   u		  u   p  	  u   p		
 / 			   \		   	 / 			   \		
c			    c			c			    c

在这里插入图片描述

_{图 $1$}

状态	$c$	$p$	$g$	$u$
变色前	红色	红色	黑色	红色
变色后	红色	黑色	红色	黑色

变色前：

	  黑		  黑		  黑		  黑		
     /  \ 		 /  \		 /  \ 	   	 /  \		
   红    红     红    红	   红	 红     红    红		
  / 			 \		   	    /			   \		
红			      红		  红			    红

变色后：

	  红		  红		  红		  红		
     /  \ 		 /  \		 /  \ 	   	 /  \		
   黑    黑     黑    黑	   黑	 黑     黑    黑		
  / 			 \		   	    /			   \		
红			      红		  红			    红

【分析】 $c$ 为红色， $p$ 为红色， $g$ 为黑色， $u$ 存在且为红色，则将 $p$ 和 $u$ 变黑， $g$ 变红。再把 $g$ 当做新的 $c$ ，继续往上更新。

也就相当于：

保持 $g$ 所在子树的黑色结点的数量不变（满足【规则 $4$ 】）
同时解决了 $c$ 和 $p$ 连续红色结点的问题（满足【规则 $3$ 】）

需要继续往上更新是因为： $g$ 是红色

如果 $g$ 的父亲还是红色，那么就还需要继续处理：

_{图 $2$}
如果 $g$ 的父亲是黑色，则处理结束了。
如果 $g$ 就是整棵树的根，再把 $g$ 变回黑色。

跟 $A V L$ 树类似，图 $1$ 我们展示了一种具体情况，但是实际中需要这样处理的有很多种情况：

图 $3$ 将以上类似的处理进行了抽象表达， $d / e / f$ 代表每条路径拥有 $bh$ （ $bh\ge0$ ）个黑色结点的子树， $a / b$ 代表每条路径拥有 $bh - 1$ 个黑色结点的根为红色的子树。

在这里插入图片描述

_{图 $3$}

上述情况代表了所有只变色（情况一）的场景，因此一般来说我们只需要看抽象图即可，但通过下面根据 $d / e / f$ 子树每条路径黑色结点的个数 $bh$ 而分为的很多种具体场景，可以更直观的帮助我们理解抽象场景：

【第一种场景】 $d / e / f$ 子树没有黑色结点（ $bh = 0$ ）：

即 $a / b / d / e / f$ 都为空树， $c$ 为新增结点。

注意： $x$ 是 $6$ 和 $15$ 结点的任意一个孩子，都会引发这里的变色逻辑。

在这里插入图片描述

_{图 $4$}

【第二种场景】 $d / e / f$ 子树每条路径都只有 $1$ 个黑色结点（ $bh = 1$ ）：

即 $d / e / f$ 都代表一个 $bh = 1$ 的红黑树：

在这里插入图片描述

_{图 $5$}

$c$ 之前是黑色结点，在 $a$ 和 $b$ 中插入引发 $c$ 变色为红色结点。
$d / e / f$ 为 $x / y / z / m$ 中任意一种，组合为 $4\times4\times4$ 种。
$a$ 和 $b$ 为红色结点，再 $a$ 和 $b$ 的四个孩子的任意位置插入，都会让 $a$ 和 $b$ 变成黑色， $c$ 变成红色，继续向上更新，插入位置有 $4$ 个位置。
所有情况组合起来合计： $4\times4\times4\times4=256$ 种。

在这里插入图片描述

_{图 $6$}

【第三种场景】 $d / e / f$ 子树每条路径都只有 $2$ 个黑色结点（ $bh = 2$ ）：

即 $d / e / f$ 都代表一个 $bh = 2$ 的红黑树：

在这里插入图片描述

_{图 $7$}

在这里插入图片描述

_{图 $8$}

$a$ 和 $b$ 都代表一个 $bh = 1$ 的根为红色的树：
在这里插入图片描述

_{图 $9$}

$d / e / f$ 的组合为： $(256+16)\times(256+16)\times(256+16)=20123648$ 种。
$a$ 和 $b$ 为根结点为红色的 $bh = 1$ 的树，这里可以看到 $a$ 和 $b$ 的插入组合也不少： $16\times16=256$ 种。
$a$ 或者 $b$ 插入至少要经历两次变色和向上处理才能得到这里的情况，因此这里的组合情况至少是百亿种以上了： $20123648\times256\times n(n\ge2)\ge10303307776$ 种。

在这里插入图片描述

_{图 $10$}

2.2 情况二：旋转+变色

情况 $2$ ： $u$ 不存在或者 $u$ 存在且为黑色，则需要先旋转，再变色。

旋转的核心逻辑和之前 $A V L$ 树一模一样，可以参考我的这篇博客：【数据结构】 $A V L$ 树。

不同的是，红黑树的旋转不用更新平衡因子：

左单旋：

void rotateL(node* parent)
{
	node* subR = parent->_right;
	node* subRL = subR->_left;
	node* pParent = parent->_parent;

	// 旋转核心逻辑
	subR->_left = parent;
	parent->_right = subRL;
	if (pParent == nullptr)	// parent == _root
		_root = subR;
	else if (pParent->_left == parent)
		pParent->_left = subR;
	else
		pParent->_right = subR;

	// 处理_parent
	if(subRL)
		subRL->_parent = parent;
	parent->_parent = subR;
	subR->_parent = pParent;
}

右单旋：

void rotateR(node* parent)
{
	node* subL = parent->_left;
	node* subLR = subL->_right;
	node* pParent = parent->_parent;

	// 旋转核心逻辑
	subL->_right = parent;
	parent->_left = subLR;
	if (pParent == nullptr)	// parent == _root
		_root = subL;
	else if (pParent->_left = parent)
		pParent->_left = subL;
	else
		pParent->_right = subL;

	// 处理_parent
	if (subLR)
		subLR->_parent = parent;
	parent->_parent = subL;
	subL->_parent = pParent;
}

(1) 单旋+变色

$u$ 不存在，则 $c$ 一定是新增结点。

在这里插入图片描述

_{图 $11$}

$u$ 存在且为黑，则 $c$ 一定不是新增， $c$ 之前是黑色的，是在 $c$ 的子树中插入，符合情况 $1$ ，变色将 $c$ 从黑色变成红色，更新上来的。

在这里插入图片描述

_{图 $12$}

分析： $p$ 必须变黑，才能解决连续红色结点的问题， $u$ 不存在或者是黑色的，这里单纯的变色无法解决问题，因此需要旋转 $+$ 变色。

在这里插入图片描述

_{图 $13$}

如果 $p$ 是 $g$ 的左， $c$ 是 $p$ 的左，那么以 $g$ 为旋转点进行右单旋，再把 $p$ 变黑， $g$ 变红， $p$ 变成这棵树新的根：

	g					  p
   / \					 / \
  p   u		右单旋->		c   g
 /					   		 \
c 					  		  u	

	  黑					   红 					  黑		
     /  \					  /  \					 /	\
   红     黑		右单旋->		红     黑	 变色->     红	 红			    	 		 		
  /					   		 	    \			  		   \
红 					  		  	     黑 					黑

这样子树黑色结点的数量不变【规则 $3$ 】，且没有连续的红色结点了【规则 $4$ 】，因此不需要往上更新，因为 $p$ 的父亲是黑色还是红色或者为空都不违反规则。

if(parent == grandparent->_left)
{
	if(uncle == nullptr || uncle->_col = black)
	{
		if(cur == parent->_left)
		{
			// 右单旋
			rotateR(grandparent);
			// 变色
			parent->_col = black;
			grandparent->_col = red;
		}
		break;
	}
}

如果 $p$ 是 $g$ 的右， $c$ 是 $p$ 的右，那么以 $g$ 为旋转点进行左单旋，再把 $p$ 变黑， $g$ 变红， $p$ 变成这棵树新的根：

	g					  p
   / \					 / \
  u   p		左单旋->		g   c
   	   \			   / 	   
        c			  u	   	  	
        
	  黑					   红 					  黑		
     /  \					  /  \					 /	\
   黑     红		左单旋->		黑     红	 变色->     红	 红			    	 		 		
           \			   /	    		  	  / 
            红 			 黑		      			黑

if(parent == grandparent->_right)
{
	if(uncle == nullptr || uncle->_col = black)
	{
		if(cur == parent->_right)
		{
			// 右单旋
			rotateR(grandparent);
			// 变色
			parent->_col = black;
			grandparent->_col = red; 
		}
		break;
	}
}

(2) 双旋+变色

$u$ 不存在，则 $c$ 一定是新增结点。

在这里插入图片描述

_{图 $14$}

$u$ 存在且为黑，则 $c$ 一定不是新增， $c$ 之前是黑色的，是在 $c$ 的子树中插入，符合情况 $1$ ，变色将 $c$ 从黑色变成红色，更新上来的。

在这里插入图片描述

_{图 $15$}

分析： $p$ 必须变黑，才能解决连续红色结点的问题， $u$ 不存在或者是黑色的，这里单纯的变色无法解决问题，因此需要旋转 $+$ 变色。

在这里插入图片描述

_{图 $16$}

如果 $p$ 是 $g$ 的左， $c$ 是 $p$ 的左，那么再以 $p$ 为旋转点进行左单旋，再以 $g$ 为旋转点进行右单旋，再把 $c$ 变黑， $g$ 变红， $c$ 变成这棵树新的根：

	g					  g					   c
   / \					 / \				  / \
  p   u		左单旋->		c   u	 右单旋->	 p	 g	   	    	
   \				   /   	 					  \
  	c				  p		  	                   u

	黑					   黑 					    红					黑
   /  \					  /  \				   	   /  \				   /  \
 红    黑	左单旋->		红     黑	 右单旋->	 红	   黑	 变色-> 	 红	   红	    	 		 		
  \					   /		 	    			 	 \					 \
   红				 红	  	      					  	  黑                  黑

这样子树黑色结点的数量不变【规则 $3$ 】，且没有连续的红色结点了【规则 $4$ 】，因此不需要往上更新，因为 $c$ 的父亲是黑色还是红色或者为空都不违反规则。

if(parent == grandparent->_left)
{
	if(uncle == nullptr || uncle->_col == black)
	{
		if(cur == parent->_right)
		{
			// 先左旋，再右旋
			rotateL(parent);
			rotateR(grandparent);
			// 变色
			cur->_col = black;
			grandparent->_col = red;
		}
		break;
	}
}

如果 $p$ 是 $g$ 的右， $c$ 是 $p$ 的右，那么先以 $p$ 为旋转点进行右单旋，再以 $g$ 为旋转点进行左单旋，再把 $c$ 变黑， $g$ 变红， $c$ 变成这棵树新的根：

	g					  g					   c
   / \					 / \				  / \
  u   p		右单旋->		u   c	 左单旋->	 g	 p	   	    	
     /				      	 \				/	  
  	c				          p		  	   u        

	黑					   黑 					    红					黑
   /  \					  /  \				   	   /  \				   /  \
 黑    红	右单旋->		黑     红	 左单旋->	 黑	   红	 变色-> 	 红	   红	    	 		 		
  	 /				         	\		 	    /		            /
   红				             红	  	      黑				  黑

if(parent == grandparent->_right)
{
	if(uncle == nullptr || uncle->_col == black)
	{
		if(cur == parent->_left)
		{
			// 先右旋，再左旋
			rotateR(parent);
			rotateL(grandparent);
			// 变色
			cur->_col = black;
			grandparent->_col = red;
		}
		break;
	}
}

3. 查找操作

红黑树的本质也是一棵自平衡的二叉搜索树，所以查找操作和二叉搜索树的操作完全一致，因此直接使用二叉搜索树逻辑实现即可，搜索效率为 $O(\log N)$ 。

node* find(const K& key)
{
	node* cur = _root;
	while (cur)
	{
		if (key < cur->_kv.first)
		{
			cur = cur->_left;
		}
		else if (key > cur->_kv.first)
		{
			cur = cur->_right;
		}
		else
		{
			return cur;
		}
	}
	return nullptr;
}

4. 验证操作

这里直接获取最长路径和最短路径，检查最长路径不超过最短路径的 $2$ 倍是不可行的，因为就算满足这个条件，红黑树也可能颜色不满足规则，当前暂时没出问题，后续继续插入还是会出问题的。所以我们还是去检查 $4$ 点规则，满足这 $4$ 点规则，就一定能保证最长路径不超过最短路径的 $2$ 倍。

在这里插入图片描述

检查【规则 $1$ 】：枚举颜色类型，天然实现保证了颜色不是黑色就是红色。

检查【规则 $2$ 】：直接检查根即可。

检查【规则 $3$ 】：前序遍历检查，遇到红色结点查孩子不太方便，因为孩子有两个，且不一定存在，反过来检查父亲的颜色就方便多了。

检查【规则 $4$ 】：前序遍历，遍历过程中用形参记录跟到当前结点的 $b l a c k N u m$ （黑色结点数量），前序遍历遇到黑色结点就 ++ $b l a c k N u m$ ，走到空就计算出了一条路径的黑色结点数量。再以任意一条路径黑色结点数量作为参考值，依次比较即可。

递归检查是否满足规则：

bool check(node* root, int blackNum, const int refNum)
	{
		if (root == nullptr)
		{
			if (blackNum != refNum)
			{
				cout << "存在黑色结点不相等的路径！" << endl;
				return false;
			}
			return true;
		}
		if (root->_col == red && root->_parent->_col == red)
		{
			cout << "存在有连续两个红色结点的路径！" << endl;
			return false;
		}
		if (root->_col == black)
		{
			++blackNum;
		}
		return check(root->_left, blackNum, refNum) && check(root->_right, blackNum, refNum);
	}

检查是否平衡（为红黑树）：

bool isBalance()
	{
		if (_root == nullptr)
			return true;
		if (_root->_col == red)
			return false;
		int refNum = 0;
		node* cur = _root;
		while (cur)
		{
			if (cur->_col == black)
				++refNum;
			cur = cur->_left;
		}
		return check(_root, 0, refNum);
	}

三、红黑树的实现

由于这个数据结构是用 $C$ ++ 代码来模拟实现的，因此采用了模板来定义的红黑树类，所以不能将声明和定义分离，因此这里分为了两个文件： $RBT ree . h$ 来模拟实现并封装一个红黑树的模板类， $t es t . c pp$ 用来测试。

原理部分已经交代清楚了，这里给出完整代码：

$RBT ree . h$ ：

#pragma once
#include<iostream>

using namespace std;

// 枚举值表示颜色
enum color
{
	red,
	black
};

template<class K, class V>
struct RBTreeNode
{
	pair<K, V> _kv;				// 每个结点存储的值
	RBTreeNode<K, V>* _left;	// 左子树
	RBTreeNode<K, V>* _right;	// 右子树
	RBTreeNode<K, V>* _parent;	// 父结点
	color _col;					// 每个结点的颜色

	RBTreeNode(const pair<K, V>& kv)
		:_kv(kv)
		, _left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
		, _col(red)
	{}
};

template<class K, class V>
class RBTree
{
	typedef RBTreeNode<K, V> node;
public:
	void rotateL(node* parent)
	{
		node* subR = parent->_right;
		node* subRL = subR->_left;
		node* pParent = parent->_parent;

		// 旋转核心逻辑
		subR->_left = parent;
		parent->_right = subRL;
		if (pParent == nullptr)	// parent == _root
			_root = subR;
		else if (pParent->_left == parent)
			pParent->_left = subR;
		else
			pParent->_right = subR;

		// 处理_parent
		if(subRL)
			subRL->_parent = parent;
		parent->_parent = subR;
		subR->_parent = pParent;
	}

	void rotateR(node* parent)
	{
		node* subL = parent->_left;
		node* subLR = subL->_right;
		node* pParent = parent->_parent;

		// 旋转核心逻辑
		subL->_right = parent;
		parent->_left = subLR;
		if (pParent == nullptr)	// parent == _root
			_root = subL;
		else if (pParent->_left = parent)
			pParent->_left = subL;
		else
			pParent->_right = subL;

		// 处理_parent
		if (subLR)
			subLR->_parent = parent;
		parent->_parent = subL;
		subL->_parent = pParent;
	}

	bool insert(const pair<K, V>& kv)
	{
		if (_root == nullptr)
		{
			_root = new node(kv);
			_root->_col = black;
			return true;
		}
		
		node* parent = nullptr;
		node* cur = _root;
		while (cur)
		{
			if (kv.first < cur->_kv.first)
			{
				parent = cur;
				cur = cur->_left;
			}
			else if (kv.first > cur->_kv.first)
			{
				parent = cur;
				cur = cur->_right;
			}
			else
			{
				return false;
			}
		}
		cur = new node(kv);
		if (kv.first < parent->_kv.first)
		{
			parent->_left = cur;
		}
		else
		{
			parent->_right = cur;
		}
		cur->_parent = parent;

		// 维持平衡操作
		while (parent && parent->_col == red)	// 如果父亲是红，说明出现了连续的红色结点
		{
			node* grandparent = parent->_parent;
		
			if(parent == grandparent->_left)
			{
				node* uncle = grandparent->_right;
			/*
				  g
				 / \
				p   u
			*/
				if (uncle && uncle->_col == red)	// 情况一：u 存在且为红色
				{
					// 变色
					grandparent->_col = red;
					parent->_col = uncle->_col = black; 
				
					// 继续向上更新
					cur = grandparent;
					parent = cur->_parent;
				}
				else								// 情况二：u 存在且为黑色 或者 u 不存在
				{
					// 旋转 + 变色
					if (cur == parent->_left)
					{
					/*	1. 单旋
						    g          p
						   / \        / \
						  p   u  ->  c   g
						 /                \
						c                  u
					*/
						rotateR(grandparent);
						// 变色
						parent->_col = black;
						grandparent->_col = red;
					}
					else
					{
					/*	2. 双旋
							g          c
						   / \        / \
						  p   u  ->  p   g
						   \              \
						    c              u
					*/
						rotateL(parent);
						rotateR(grandparent);
						// 变色
						cur->_col = black;
						grandparent->_col = red;
					}
					break;
				}
			}
			else
			{
				node* uncle = grandparent->_left;
			/*
				  g
				 / \
				u   p
			*/
				if (uncle && uncle->_col == red)	// 情况一：u 存在且为红色
				{
					// 只变色
					grandparent->_col = red;
					uncle->_col = parent->_col = black;

					// 继续向上更新
					cur = grandparent;
					parent = cur->_parent;
				}
				else								// 情况二：u 存在且为黑色 或者 u 不存在
				{
					// 旋转 + 变色
					if (cur == parent->_right)
					{
					/*	1. 单旋
						    g          p
						   / \        / \
						  u   p  ->  g   c
						       \    /
						        c  u
					*/
						rotateL(grandparent);
						// 变色
						parent->_col = black;
						grandparent->_col = red;
					}
					else
					{
					/*	2. 双旋
						    g          c
						   / \        / \
						  u   p  ->  g   p
						     /      /
						    c      u
					*/
						rotateR(parent);
						rotateL(grandparent);
						// 变色
						cur->_col = black;
						grandparent->_col = red;
					}
					break;
				}
			}
		}

		_root->_col = black;
		return true;
	}

	node* find(const K& key)
	{
		node* cur = _root;
		while (cur)
		{
			if (key < cur->_kv.first)
			{
				cur = cur->_left;
			}
			else if (key > cur->_kv.first)
			{
				cur = cur->_right;
			}
			else
			{
				return cur;
			}
		}
		return nullptr;
	}

	void inorder()
	{
		_inorder(_root);
		cout << endl;
	}

	int size()
	{
		return _size(_root);
	}

	int height()
	{
		return _height(_root);
	}

	bool isBalance()
	{
		if (_root == nullptr)
			return true;
		if (_root->_col == red)
			return false;
		int refNum = 0;
		node* cur = _root;
		while (cur)
		{
			if (cur->_col == black)
				++refNum;
			cur = cur->_left;
		}
		return check(_root, 0, refNum);
	}
private:
	bool check(node* root, int blackNum, const int refNum)
	{
		if (root == nullptr)
		{
			if (blackNum != refNum)
			{
				cout << "存在黑色结点不相等的路径！" << endl;
				return false;
			}
			return true;
		}
		if (root->_col == red && root->_parent->_col == red)
		{
			cout << "存在有连续两个红色结点的路径！" << endl;
			return false;
		}
		if (root->_col == black)
		{
			++blackNum;
		}
		return check(root->_left, blackNum, refNum) && check(root->_right, blackNum, refNum);
	}

	int _height(node* root)
	{
		if (root == nullptr)
			return 0;
		int lh = _height(root->_left);
		int rh = _height(root->_right);
		return lh > rh ? lh + 1 : rh + 1;
	}

	int _size(node* root)
	{
		if (root == nullptr)
			return 0;
		return _size(root->_left) + _size(root->_right) + 1;
	}

	void _inorder(node* root)
	{
		if (root == nullptr)
			return;
		_inorder(root->_left);
		cout << root->_kv.first << ":" << root->_kv.second << " ";
		_inorder(root->_right);
	}

	node* _root = nullptr;
};

$t es t . c pp$ ：

#include"RBTree.h"

void test()
{
	RBTree<int, int> rbt;

	rbt.insert({ 1,1 });
	rbt.insert({ 2,2 });
	rbt.insert({ 3,3 });
	rbt.insert({ 4,4 });

	rbt.inorder();
	cout << "结点个数：" << rbt.size() << " 个" << endl;
	cout << "树的高度：" << rbt.height() << " 层" << endl;
	cout << "是否平衡：";
	rbt.isBalance() == true ? cout << "平衡！" << endl : cout << "不平衡：" << endl;
}

int main()
{
	test();

	return 0;
}

总结

与 $A V L$ 树相同，红黑树也是一种自平衡的二叉搜索树，通过给每个结点染色（红色或黑色），从而能够使用规则来约束树的结构，使整棵树近似平衡。

红黑树虽然平衡效果略逊于 $A V L$ 树，但是红黑树的效率要比 $A V L$ 树高，因为 $A V L$ 树是通过高度差实现自平衡效果，几乎每几次插入或删除就需要旋转，而红黑树通过颜色规则约束整棵树，大部分情况直接变色就可以解决问题，需要旋转的次数大大降低，因此效率也就增加了。

$C$ ++ 的 $ST L$ 标准库中， $ma p$ 和 $se t$ 容器的底层结构使用的数据结构就是红黑树，可见红黑树的重要性和使用广泛。

【数据结构】红黑树

文章目录

一、红黑树的概念

1. 基本规则

2. 红黑树的效率

二、红黑树的基本操作

1. 基本结构

2. 插入操作

2.1 插入的过程

2.2 情况一：变色

2.2 情况二：旋转+变色

(1) 单旋+变色

(2) 双旋+变色

3. 查找操作

4. 验证操作

三、红黑树的实现

总结

网站公告

今日签到

热门文章

最新发布