【C++进阶】红黑树的模拟实现（附源码）

「爱情、让人受尽委屈。」 2024-04-22 12:13 87阅读 0赞

## 一.红黑树的概念 ##

红黑树：是一种二叉搜索树，但在每个结点上增加一个存储位表示结点的颜色，可以是Red或  
Black

#### 红黑树的性质 ####

1.  每个结点不是红色就是黑色
2.  根节点是黑色的
3.  如果一个节点是红色的，则它的两个孩子结点必须是黑色的（所以可以有连续的黑节点，但不可以有连续的红节点）
4.  对于每个结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数目的黑色结点（即每条路径上的黑节点数目相等）
5.  红黑树的最长路径不超过最短路径的两倍
6.  每个叶子结点都是黑色的(此处的叶子结点指的是空结点）

![23f2625f83b84baca91a630877bca36e.png][]

上图就是一个红黑树。

红黑树不是绝对平衡的，它的搜索效率和AVL树的搜索效率差不多，AVL树是绝对平衡的，但是AVL的消耗大，它需要频繁旋转，红黑树的旋转次数要少一些。

--------------------

## 二.红黑树的模拟实现 ##

#### 红黑树的节点 ####

红黑树的节点我们使用三叉链的形式，需要：

1.  左指针（\_left）
2.  右指针（\_right）
3.  父指针 （\_parent）

此外还需要一个颜色变量来表示节点的颜色，这里的颜色只有红色和黑色，可以使用枚举变量。

这里我们使用 K-V 模型，所以需要一个pair

enum COL  //枚举变量
    {
    	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;
    	COL _col;
    
    	RBTreeNode(const pair<K,V>& kv)
    		:_kv(kv)
    		,_left(nullptr)
    		,_right(nullptr)
    		,_parent(nullptr)
    		,_col(RED)
    	{}
    
    };

--------------------

#### 红黑树的插入 Insert ####

首先我们要先找到在哪里插入，这个操作和二叉搜索树的操作是一样的，就不赘述了，如果不清楚的话，可以参考-> [二叉搜索树的模拟实现][Link 1]

注意在新的节点链接好后，还要更新一下parent指针。

接下来就是考虑节点颜色的问题了。

如果插入的是黑色节点，就违背了红黑树的规则，改变了黑节点的数量，牵一发而动全身，可能需要很大的改动，所以插入黑节点是不可取的，应该插入红节点。

所以红黑树节点的构造函数把颜色初始化成红色。

我们先来认识一下什么是叔叔节点（uncle）和爷爷节点（grandfather）

*  叔叔节点（uncle）就是父节点（parent）的兄弟节点
 *  爷爷节点（grandfather）即父节点（parent）的父节点

![99418b19e17f4532989611ed1b836669.png][]

当cur的parent是红色时，此时出现了连续的红节点，此时就需要更改颜色。此时parent分为两种情况：

1.  当parent是grandfather的左节点时
2.  当parent是grandfather的右节点时

**当parent是grandfather的左节点时，此时uncle是grandfather的右节点：**

那么插入红节点又分为两种情况：

*  uncle存在且为红

此时的操作很简单，只需要将cur的parent和uncle都变为黑，grandfather变为红

然后把grandfather给给cur，重复以上操作，继续向上处理，直到没有连续的红节点为止

![ecea4471d69d46e9a674f91d273a1f57.png][]

*  uncle不存在或者uncle存在且为黑

1.  如果cur在parent的左边：只需要将grandfather右旋，然后将parent改为黑色，grandfather改为红色；
2.  如果cur在parent的右边，则要先进行左旋parent，然后再右旋grandfather，旋转完成后，cur的颜色改为黑色，grandfather的颜色改为红色。

![b181dfdcafbb4f9a94e391962d07c2cc.png][]

![36122d782b204e4dad2cf8c056c30873.png][]

**当parent是grandfather的右节点时，此时uncle是grandfather的左节点：**

操作和和前面是差不多的

当uncle存在且为红时，和前面的操作是一样的；

当uncle不存在或者uncle存在且为黑时：

*  cur在parent的右边，此时需要左旋grandfather，然后parent改为黑，grandfather改为红
 *  cur在parent的左边，先右旋parent，再左旋grandfather，然后将cur改为黑，grandfather改为红

在最后，把根节点改为黑色，这样不管怎么插入，最后根节点一定是黑色的。

#### 红黑树的删除 erase ####

红黑树的删除本篇文章不做讲解，有兴趣的可以参考：[红黑树的删除][Link 2]

--------------------

## 三.红黑树的验证 ##

1.  空树也是红黑树
2.  检查根节点是否是黑色
3.  统计任意路径上黑节点的数量，作为基准值，之后再统计其他路径上的黑节点，若不等于基准值，则不是红黑树，返回false

bool isBlance()
    	{
    		return isBlance(_root);   //封装一层，方便调用
    	}
    
    	bool isBlance(Node* root)
    	{
    		if (root == nullptr)   //空树也是红黑树
    			return true;
    
    		if (_root->_col != BLACK)   //检查根节点是否是黑色
    		{
    			cout << "根节点不是黑色" << endl;
    			return false;
    		}
    		//统计某一路径上的黑节点数作为基准值
    		int benchmark = 0;  //基准值
    		Node* cur = _root;
    		while (cur)
    		{
    			if (cur->_col == BLACK)
    				benchmark++;
    			cur = cur->_left;
    		}
    
    		return Chick(root, 0, benchmark);
    
    	}
    
    	bool Chick(Node* root, int blacknum, int benchmark)
    	{
    		if (root == nullptr)    //此时一天路径走完，比较黑节点数是否等于基准值
    		{
    			if (blacknum != benchmark)
    				return false;
    			return true;
    		}
    		if (root->_col == BLACK)  //统计黑节点的个数
    			blacknum++;
    		return Chick(root->_left, blacknum, benchmark)&& Chick(root->_right, blacknum, benchmark);   //递归左树和右树
    	}

--------------------

## 四.红黑树与AVL树的比较 ##

*  红黑树和AVL树都是高效的平衡二叉树，增删改查的时间复杂度都是O(log N)；
 *  红黑树不追求绝对平衡，其只需保证最长路径不超过最短路径的2倍，相对而言，降低了插入和旋转的次数；
 *  所以在经常进行增删的结构中性能比AVL树更优，而且红黑树实现比较简单，所以实际运用中红黑树更多。

## 四.源码 ##

#### RBTree.h ####

enum COL   //颜色枚举变量
    {
    	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;
    	COL _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:
    	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 (cur->_kv.first > kv.first)
    			{
    				parent = cur;
    				cur = cur->_left;
    			}
    			else if (cur->_kv.first < kv.first)
    			{
    				parent = cur;
    				cur = cur->_right;
    			}
    			else
    				return false;
    		}
    
    		cur = new Node(kv);
    		if (parent->_kv.first > kv.first)
    			parent->_left = cur;
    		else
    			parent->_right = cur;
    		cur->_parent = parent;
    		while (parent && parent->_col == RED)
    		{
    			Node* grandfather = parent->_parent;
    			if (grandfather->_left == parent)   //parent在grandfather的左边
    			{
    				Node* uncle = grandfather->_right;
    				if (uncle && uncle->_col == RED)   //uncle存在且为红色 ： 变色
    				{
    					parent->_col = uncle->_col = BLACK;
    					grandfather->_col = RED;
    					cur = grandfather;
    					parent = cur->_parent;
    				}
    				else   //uncle不存在或uncle存在且为黑  ： 旋转+变色
    				{
    					//       g
    					//    p     u
    					//  c
    					if (cur == parent->_left)  //右旋g
    					{
    						RotateR(grandfather);
    						parent->_col = BLACK;
    						grandfather->_col = RED;
    					}
    					else   //左右双旋
    					{
    						//      g
    						//  p        u
    						//     c
    						RotateL(parent);    //左旋p
    						RotateR(grandfather);   //右旋g
    						cur->_col = BLACK;
    						grandfather->_col = RED;
    					}
    					break;
    				}
    			}
    			else     //parent在grandfather的右边
    			{
    				Node* uncle = grandfather->_left;
    				if (uncle && uncle->_col == RED)   //uncle存在且为红
    				{
    					parent->_col = uncle->_col = BLACK;
    					grandfather->_col = RED;
    					cur = grandfather;
    					parent = cur->_parent;
    				}
    				else      //uncle不存在或者uncle存在且为黑
    				{
    					//     g
    					//         p
    					//             c
    					if (parent->_right == cur)  //左旋g
    					{
    						RotateL(grandfather);
    						parent->_col = BLACK;
    						grandfather->_col = RED;
    					}
    					else    //右左双旋
    					{
    						//     g
    						//          p
    						//      c
    						RotateR(parent);    //右旋p
    						RotateL(grandfather);   //左旋g
    						grandfather->_col = RED;
    						cur->_col = BLACK;
    					}
    					break;
    				}
    			}
    		}
    
    		_root->_col = BLACK;
    		return true;
    	}
    
    	void RotateL(Node* parent)   //左旋
    	{
    		Node* cur = parent->_right;
    		Node* curleft = cur->_left;
    		Node* ppnode = parent->_parent;
    
    		parent->_right = curleft;
    		cur->_left = parent;
    		if (curleft)
    			curleft->_parent = parent;
    		parent->_parent = cur;
    		if (ppnode == nullptr)
    		{
    			_root = cur;
    			cur->_parent = nullptr;
    		}
    		else
    		{
    			if (ppnode->_left == parent)
    				ppnode->_left = cur;
    			else
    				ppnode->_right = cur;
    			cur->_parent = ppnode;
    		}
    	}
    
    	void RotateR(Node* parent)    //右旋
    	{
    		Node* cur = parent->_left;
    		Node* curright = cur->_right;
    		Node* ppnode = parent->_parent;
    
    		parent->_left = curright;
    		cur->_right = parent;
    		if (curright)
    			curright->_parent = parent;
    		parent->_parent = cur;
    		if (ppnode == nullptr)
    		{
    			_root = cur;
    			cur->_parent = nullptr;
    		}
    		else
    		{
    			if (ppnode->_left == parent)
    				ppnode->_left = cur;
    			else
    				ppnode->_right = cur;
    			cur->_parent = ppnode;
    		}
    	}
    
    	bool isBlance()
    	{
    		return isBlance(_root);   //封装一层，便于调用
    	}
    
    	bool isBlance(Node* root)
    	{
    		if (root == nullptr)   //空树也是红黑树
    			return true;
    
    		if (_root->_col != BLACK)   //检查根节点是否是黑色
    		{
    			cout << "根节点不是黑色" << endl;
    			return false;
    		}
    		//统计某一路径上的黑节点数作为基准值
    		int benchmark = 0;  //基准值
    		Node* cur = _root;
    		while (cur)
    		{
    			if (cur->_col == BLACK)
    				benchmark++;
    			cur = cur->_left;
    		}
    
    		return Chick(root, 0, benchmark);
    
    	}
    
    	bool Chick(Node* root, int blacknum, int benchmark)
    	{
    		if (root == nullptr)     //此时走完一条路径，比较黑节点数是否等于基准值
    		{
    			if (blacknum != benchmark)
    				return false;
    			return true;
    		}
    		if (root->_col == BLACK)   //统计一条路径上的黑节点的个数
    			blacknum++;
    		return Chick(root->_left, blacknum, benchmark)&& Chick(root->_right, blacknum, benchmark);   //递归它的左树和右树
    	}
    
    private:
    	Node* _root = nullptr;
    };

--------------------

> **??本篇文章到此就结束了， 若有错误或是建议的话，欢迎小伙伴们指出；?️?**
> 
> **??希望小伙伴们能支持支持博主啊，你们的支持对我很重要哦；??**
> 
> **??谢谢你的阅读。??**

[23f2625f83b84baca91a630877bca36e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/22/6fb6a2425cfe4e3bb603dedfdb0b974c.png
[Link 1]: http://t.csdn.cn/okFVq
[99418b19e17f4532989611ed1b836669.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/22/c96bd36363b54366a91e731469e496aa.png
[ecea4471d69d46e9a674f91d273a1f57.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/22/04ceaeb3049442d485d5de058c684849.png
[b181dfdcafbb4f9a94e391962d07c2cc.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/22/b7fe9478ce794263a6d63340899ccacd.png
[36122d782b204e4dad2cf8c056c30873.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/22/58568f542b0c4f7fa5d5ba8b5a3e7b85.png
[Link 2]: http://www.cnblogs.com/fornever/archive/2011/12/02/2270692.html