数据结构：红黑树讲解（C++）

红黑树

- 1.前言
- 2.红黑树简述
- - 2.1概念
  - 2.2性质
- 3.红黑树的插入
- - 3.1关于新插入节点的颜色
  - 3.2节点的定义
  - 3.3插入新节点
  - 3.4判断插入后是否需要调整
  - 3.5插入后维持红黑树结构（重点）
  - - 3.5.1cur、p、u为红，g为黑
    - 3.5.2cur、p为红，g为黑，u为空/u存在为黑
- 4.一些简单的测试接口
- 5.完整代码

1.前言

本文旨在理解红黑树基本概念以及变色旋转规则，以理解C++map和set的底层原理，不会讲红黑树的删除操作。
对于基本的旋转操作(单旋和双旋)，本文不会展开讲，详细讲解在这里：
AVL树旋转讲解。

2.红黑树简述

2.1概念

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

2.2性质

每个节点不是红色就是黑色。
根部节点是黑色的。(为了减少旋转次数，后面讲旋转大家就明白了）
对于一个红节点，它的孩子只能是黑色。(即一条路径上不能出现连续的红色节点)
每条路径都必须包含相同数量的黑色节点。

通过上面规则的限制，红黑树最长路径一定不会超过最短路径两倍，也就维持了高度的相对平衡。
结合3、4来看下面的两条路径：
最长：黑、红、黑、红、黑、红…………
最短：黑、黑、黑…………

3.红黑树的插入

3.1关于新插入节点的颜色

对于新插入节点，我们设置为红色，原因是红黑树每条路径都必须包含相同数量的黑色节点（性质4），新插入红节点不一定破坏红黑树的结构，新插入黑色节点一定不符合性质4而且很难调整。

3.2节点的定义

//用枚举来定义颜色
enum Color
{
	RED,
	BLACK
};

//这里直接实现key_value模型
template<class K, class V>
struct RBTreeNode
{
	RBTreeNode<K, V>* _left;
	RBTreeNode<K, V>* _right;
	RBTreeNode<K, V>* _parent;  //涉及到旋转，多加父亲指针来简化操作
	pair<K, V> _kv;  //存储键值对
	Color _col; //颜色
	RBTreeNode(const pair<K, V>& kv)
		:_left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
		, _kv(kv)
		,_col(RED)  //新节点颜色为红色
	{}
};

3.3插入新节点

这里比较简单，按二叉搜索树的规则插入即可：

bool Insert(const pair<K, V>& kv)
{
	if (_root == nullptr)
	{
		_root = new Node(kv);
		_root->_col = BLACK;
		return true;
	}
	Node* cur = _root;
	Node* parent = nullptr;
	while (cur)
	{
		if (kv.first > cur->_kv.first) //待插入节点在右子树
		{
			parent = cur;
			cur = cur->_right;
		}
		else if (kv.first < cur->_kv.first)  //待插入节点在左子树
		{
			parent = cur;
			cur = cur->_left;
		}
		else  //相同
		{
			return false;
		}
	}
	cur = new Node(kv);
	if (kv.first > parent->_kv.first) //新节点在父亲右子树
	{
		parent->_right = cur;
	}
	else  //新节点在父亲左子树
	{
		parent->_left = cur;
	}
	cur->_parent = parent;  //记得更新父亲指针
	
	/// 变色旋转维持红黑树结构（暂时省略）  //
	
	_root->_col = BLACK; //可能改变根部颜色，保持根部为黑色
	return true;
}

3.4判断插入后是否需要调整

其实红黑树插入后只需要看当前节点和父亲的颜色即可，其中新节点一定为红。

父亲为黑，符合规则，不需要调整。
父亲为红，此时出现红红的连续节点，需要进行调整。

3.5插入后维持红黑树结构（重点）

为了方便叙述，我们做如下定义：

cur表示当前节点
p表示cur父亲节点
u表示叔叔节点
g表示祖父(p和u的父亲)节点

3.5.1cur、p、u为红，g为黑

代码：

while (parent && parent->_col == RED)  //父亲为红就调整，调整到根部要结束
{
	Node* granderfather = parent->_parent;  //祖父
	//需要对叔叔进行操作，需要判断叔叔是祖父的左还是右
	if (parent == granderfather->_left)  //父亲是祖父的左子树
	{
		Node* uncle = granderfather->_right;
		if (uncle && uncle->_col == RED) //叔叔不为空并且叔叔为红，变色即可
		{
			uncle->_col = parent->_col = BLACK;
			granderfather->_col = RED; 
			//当前子树可能为部分，继续向上调整
			cur = granderfather;
			parent = cur->_parent;
		}
		else  //叔叔为空或为黑色
		{ 
			//先省略
		}
	}
	else  //父亲是祖父的右子树
	{
		Node* uncle = granderfather->_left;
		if (uncle && uncle->_col == RED)  //叔叔不空并且为红
		{
			parent->_col = uncle->_col = BLACK;
			granderfather->_col = RED;  
			//当前可能为部分子树，需要继续上调
			cur = granderfather;
			parent = cur->_parent;
		}
		else  //叔叔为空或为黑色
		{
			// 先省略
		}
	}
}

3.5.2cur、p为红，g为黑，u为空/u存在为黑

下面是一会要用到的旋转接口：

void RotateL(Node* parent)  //左单旋,rotate->旋转
{
	Node* SubR = parent->_right;
	Node* SubRL = SubR->_left;  //这个有可能为空
	Node* ppnode = parent->_parent;  //原来父亲的父亲

	parent->_right = SubRL;
	if (SubRL)  SubRL->_parent = parent;

	SubR->_left = parent;
	parent->_parent = SubR;

	if (ppnode == nullptr)  //旋转的是整颗树
	{
		_root = SubR;
		SubR->_parent = nullptr;
	}
	else  //旋转的是部分
	{
		if (ppnode->_left == parent) //是左子树
		{
			ppnode->_left = SubR;
		}
		else  //是右子树
		{
			ppnode->_right = SubR;
		}
		SubR->_parent = ppnode;
	}
}

void RotateR(Node* parent)  //右单旋细节处理和左单旋差不多
{
	Node* SubL = parent->_left;
	Node* SubLR = SubL->_right;  //这个有可能为空
	Node* ppnode = parent->_parent;

	parent->_left = SubLR;
	if (SubLR)  SubLR->_parent = parent;

	SubL->_right = parent;
	parent->_parent = SubL;

	if (ppnode == nullptr)  //旋转的是整颗树
	{
		_root = SubL;
		SubL->_parent = nullptr;
	}
	else  //旋转部分
	{
		if (ppnode->_left == parent)  //是左子树
		{
			ppnode->_left = SubL;
		}
		else  //右子树
		{
			ppnode->_right = SubL;
		}
		SubL->_parent = ppnode;
	}
}

涉及旋转情况比较复杂，分开讨论：

（1）p为g的左孩子，cur为p的左孩子

（2）p为g的左孩子，cur为p的右孩子

（3）p为g的右孩子，cur为p的右孩子

（4）p为g的右孩子，cur为p的左孩子

整合一下（1、2、3、4）得到下面的调整代码：

//到这里插入新节点的工作完成，下面进行结构调整：
while (parent && parent->_col == RED)  //父亲为红就调整，调整到根部要结束
{
	Node* granderfather = parent->_parent;  //祖父
	if (parent == granderfather->_left)  //父亲是祖父的左子树，p为g的左孩子
	{
		Node* uncle = granderfather->_right;
		if (uncle && uncle->_col == RED) //叔叔不为空并且叔叔为红，变色即可
		{
			uncle->_col = parent->_col = BLACK;
			granderfather->_col = RED; 
			//当前子树可能为部分，继续向上调整
			cur = granderfather;
			parent = cur->_parent;
		}
		else  //叔叔为空或为黑色
		{ 
			//     g
			//   p   u
			// c
			if (cur == parent->_left)  //当前为父亲的左子树，cur为p的左孩子
			{
				RotateR(granderfather);
				granderfather->_col = RED;
				parent->_col = BLACK;
			}
			else   //当前为父亲的右子树，cur为p的右孩子
			{
				//    g
				//  p   u
				//    c
				//左右双旋
				RotateL(parent);
				RotateR(granderfather);
				granderfather->_col = RED;
				cur->_col = BLACK;
			}
			break;  //这两种情况调整完可以结束
		}
	}
	else  //父亲是祖父的右子树，p为g的右孩子
	{
		Node* uncle = granderfather->_left;
		if (uncle && uncle->_col == RED)  //叔叔不空并且为红
		{
			parent->_col = uncle->_col = BLACK;
			granderfather->_col = RED;  
			//当前可能为部分子树，需要继续上调
			cur = granderfather;
			parent = cur->_parent;
		}
		else  //叔叔为空或为黑色
		{
			if (cur == parent->_right)  //当前为父亲的右，cur为p的右孩子
			{
				//    g
				//  u   p
				//        c
				//左旋
				RotateL(granderfather);
				parent->_col = BLACK;
				granderfather->_col = RED;
			}
			else  //当前为父亲的左，cur为p的左孩子
			{
				//   g
				// u   p
				//   c
				//右左双旋
				RotateR(parent);
				RotateL(granderfather);
				cur->_col = BLACK;
				granderfather->_col = RED;	
			}
			break;  //这两种情况调整完可以结束
		}
	}
}
_root->_col = BLACK; //保持根部为黑色

4.一些简单的测试接口

void InOrder()   //中序遍历，验证是否为二叉搜索树
{
	_InOrder(_root);
	cout << endl;
}

void _InOrder(Node* root)
{
	if (root == nullptr)
		return;

	_InOrder(root->_left);
	cout << root->_kv.first << " ";
	_InOrder(root->_right);
}

// 根节点->当前节点这条路径的黑色节点的数量
bool Check(Node* root, int blacknum, const int refVal)  
{
	if (root == nullptr)  //到根部看看当前路径黑色节点和标准值是否一致
	{
		//cout << balcknum << endl;
		if (blacknum != refVal)
		{
			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, refVal)
		&& Check(root->_right, blacknum, refVal);
}

bool IsBalance()
{
	if (_root == nullptr)
		return true;

	if (_root->_col == RED)
		return false;

	//参考值，即先算出一条路径的黑色节点数
	int refVal = 0;
	Node* cur = _root;
	while (cur)
	{
		if (cur->_col == BLACK)
		{
			++refVal;
		}

		cur = cur->_left;
	}

	int blacknum = 0;
	return Check(_root, blacknum, refVal);
}

5.完整代码

#pragma once
#include <iostream>
#include <utility>
using namespace std;

//用枚举来定义颜色
enum Color
{
	RED,
	BLACK
};

//这里直接实现key_value模型
template<class K, class V>
struct RBTreeNode
{
	RBTreeNode<K, V>* _left;
	RBTreeNode<K, V>* _right;
	RBTreeNode<K, V>* _parent;  //涉及到旋转，多加父亲指针来简化操作
	pair<K, V> _kv;  //存储键值对
	Color _col; //颜色
	RBTreeNode(const pair<K, V>& kv)
		:_left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
		, _kv(kv)
		,_col(RED)  //新节点颜色为红色
	{}
};

template<class K, class V>
class RBTree
{
public:
	typedef RBTreeNode<K, V> Node;

	bool Insert(const pair<K, V>& kv)
	{
		if (_root == nullptr)
		{
			_root = new Node(kv);
			_root->_col = BLACK;
			return true;
		}
		Node* cur = _root;
		Node* parent = nullptr;
		while (cur)
		{
			if (kv.first > cur->_kv.first) //待插入节点在右子树
			{
				parent = cur;
				cur = cur->_right;
			}
			else if (kv.first < cur->_kv.first)  //待插入节点在左子树
			{
				parent = cur;
				cur = cur->_left;
			}
			else  //相同
			{
				return false;
			}
		}
		cur = new Node(kv);
		if (kv.first > parent->_kv.first) //在右子树
		{
			parent->_right = cur;
		}
		else
		{
			parent->_left = cur;
		}
		cur->_parent = parent;

		while (parent && parent->_col == RED)  //父亲为红就调整，调整到根部要结束
		{
			Node* granderfather = parent->_parent;  //祖父
			if (parent == granderfather->_left)  //父亲是祖父的左子树
			{
				Node* uncle = granderfather->_right;
				if (uncle && uncle->_col == RED) //叔叔不为空并且叔叔为红，变色即可
				{
					uncle->_col = parent->_col = BLACK;
					granderfather->_col = RED; 
					//当前子树可能为部分，继续向上调整
					cur = granderfather;
					parent = cur->_parent;
				}
				else  //叔叔为空或为黑色
				{ 
					//     g
					//   p   u
					// c
					if (cur == parent->_left)  //当前为父亲的左子树
					{
						RotateR(granderfather);
						granderfather->_col = RED;
						parent->_col = BLACK;
					}
					else   //当前为父亲的右子树
					{
						//    g
						//  p   u
						//    c
						//左右双旋
						RotateL(parent);
						RotateR(granderfather);
						granderfather->_col = RED;
						cur->_col = BLACK;
					}
					break;
				}
			}
			else  //父亲是祖父的右子树
			{
				Node* uncle = granderfather->_left;
				if (uncle && uncle->_col == RED)  //叔叔不空并且为红
				{
					parent->_col = uncle->_col = BLACK;
					granderfather->_col = RED;  
					//当前可能为部分子树，需要继续上调
					cur = granderfather;
					parent = cur->_parent;
				}
				else  //叔叔为空或为黑色
				{
					if (cur == parent->_right)  //当前为父亲的右
					{
						//    g
						//  u   p
						//        c
						//左旋
						RotateL(granderfather);
						parent->_col = BLACK;
						granderfather->_col = RED;
					}
					else  //当前为父亲的左
					{

						//   g
						// u   p
						//   c
						//右左双旋
						RotateR(parent);
						RotateL(granderfather);
						cur->_col = BLACK;
						granderfather->_col = RED;	
					}
					break;
				}
			}
		}
		_root->_col = BLACK; //保持根部为黑色
		return true;
	}


/// //
/// /
/// 	测试代码
	 
	void InOrder()   //中序遍历，验证是否为二叉搜索树
	{
		_InOrder(_root);
		cout << endl;
	}

	void _InOrder(Node* root)
	{
		if (root == nullptr)
			return;

		_InOrder(root->_left);
		cout << root->_kv.first << " ";
		_InOrder(root->_right);
	}

	// 根节点->当前节点这条路径的黑色节点的数量
	bool Check(Node* root, int blacknum, const int refVal)  
	{
		if (root == nullptr)  //到根部看看当前路径黑色节点和标准值是否一致
		{
			//cout << balcknum << endl;
			if (blacknum != refVal)
			{
				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, refVal)
			&& Check(root->_right, blacknum, refVal);
	}

	bool IsBalance()
	{
		if (_root == nullptr)
			return true;

		if (_root->_col == RED)
			return false;

		//参考值，即先算出一条路径的黑色节点数
		int refVal = 0;
		Node* cur = _root;
		while (cur)
		{
			if (cur->_col == BLACK)
			{
				++refVal;
			}

			cur = cur->_left;
		}

		int blacknum = 0;
		return Check(_root, blacknum, refVal);
	}


	int Height()
	{
		return _Height(_root);
	}

	int _Height(Node* root)  //求高度的
	{
		if (root == nullptr)
			return 0;

		int leftHeight = _Height(root->_left);
		int rightHeight = _Height(root->_right);

		return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
	}


	Node* Find(K key)
	{
		return _Find(key, _root);
	}

	Node* _Find(K key, Node* root)
	{
		if (root == nullptr)
			return nullptr;
		if (key > root->_kv.first) //在右子树
		{
			return _Find(key, root->_right);
		}
		else if (key < root->_kv.first) //在左子树
		{
			return _Find(key, root->_left);
		}
		else  //找到了
		{
			return root;
		}
	}

private:
	Node* _root = nullptr;

	void RotateL(Node* parent)  //左单旋,rotate->旋转
	{
		Node* SubR = parent->_right;
		Node* SubRL = SubR->_left;  //这个有可能为空
		Node* ppnode = parent->_parent;  //原来父亲的父亲

		parent->_right = SubRL;
		if (SubRL)  SubRL->_parent = parent;

		SubR->_left = parent;
		parent->_parent = SubR;

		if (ppnode == nullptr)  //旋转的是整颗树
		{
			_root = SubR;
			SubR->_parent = nullptr;
		}
		else  //旋转的是部分
		{
			if (ppnode->_left == parent) //是左子树
			{
				ppnode->_left = SubR;
			}
			else  //是右子树
			{
				ppnode->_right = SubR;
			}
			SubR->_parent = ppnode;
		}
	}

	void RotateR(Node* parent)  //右单旋细节处理和左单旋差不多
	{
		Node* SubL = parent->_left;
		Node* SubLR = SubL->_right;  //这个有可能为空
		Node* ppnode = parent->_parent;

		parent->_left = SubLR;
		if (SubLR)  SubLR->_parent = parent;

		SubL->_right = parent;
		parent->_parent = SubL;

		if (ppnode == nullptr)  //旋转的是整颗树
		{
			_root = SubL;
			SubL->_parent = nullptr;
		}
		else  //旋转部分
		{
			if (ppnode->_left == parent)  //是左子树
			{
				ppnode->_left = SubL;
			}
			else  //右子树
			{
				ppnode->_right = SubL;
			}
			SubL->_parent = ppnode;
		}
	}
};

文章出处登录后可见！

已经登录？立即刷新