红黑树的实现（图文详解）

小灰灰 2023-01-22 15:49 141阅读 0赞

# 红黑树的实现 #

*  ### 红黑树的定义 ###

红黑树本质上也是一棵二叉搜索树，满足二叉搜索树的基本性质，但二叉搜索树容易形成单边树，导致搜索效率下降，需要进行平衡限制

例如AVL树就通过引平衡因子来实现平衡树[AVL树的实现（图文详解）][AVL]

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

红黑树的性质：

1.  **根节点必须是黑色的**
2.  **红色节点不可连续，黑色节点可连续**
3.  **对于每个节点，从该节点到其所有后代叶节点的简单路径上，均包含相同数目的黑色节点**

具体如下图所示：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2MTMxNjEx_size_16_color_FFFFFF_t_70][]

*  ### 红黑树的结构 ###

红黑树的实现中增加一个头结点，因为跟节点必须为黑色，为了与根节点进行区分，将头结点给成黑色，并且让头结点的 Parent 指向红黑树的根节点，Left指向红黑树中最小的节点，Right指向红黑树中最大的节点，如下：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2MTMxNjEx_size_16_color_FFFFFF_t_70 1][]

// 节点的颜色
    enum Color { RED, BLACK };
    
    // 红黑树节点的定义
    template<class k,class v>
    struct RBTreeNode
    {
    	RBTreeNode(const pair<k,v>& data = pair<k,v>())//默认红色 
    		: _left(nullptr), _right(nullptr), _parent(nullptr)
    		, _data(data), _color(RED)
    	{}
    	RBTreeNode<k,v>* _left; // 节点的左孩子
    	RBTreeNode<k,v>* _right; // 节点的右孩子
    	RBTreeNode<k,v>* _parent; // 节点的双亲(红黑树需要旋转，为了实现简单给出该字段)
    	pair<k,v> _data; // 节点的值
    	Color _color; // 节点的颜色
    };

相比较于AVL树，定义了节点的颜色替换AVL树的平衡因子，初始化节点为红色

其主要原因在于：插入新节点默认为红色，如果与其父节点构成连续红色破坏红黑树的性质则进入调整，如果默认插入为黑色节点，由于没有限制黑色节点不可连续，无法继续向上调整，导致添加后黑色节点数目无法保证每条路径上不变化

*  ### 红黑树节点插入 ###

红黑树节点插入步骤与AVL树基本一致：

1.  **搜索**
2.  **创建新节点，插入合适位置**
3.  **调整结构或调整颜色**

与AVL树不同的是，AVL根据每个节点平衡因子来决定是否进行结构调整，而红黑树通过节点颜色限制来进行结构和颜色调整

**因此，新节点插入后，需要检测红黑树的性质是否被破坏**

因为新节点的默认颜色是红色，因此：如果其双亲节点的颜色是黑色，没有违反红黑树任何性质，则不需要调整；但当新插入节点的双亲节点颜色为红色时，就违反了性质三不能有连在一起的红色节点，此时需要对红黑树分情况来讨论：

**情况1：当前节点为红，父节点为红，父节点在祖父节点左侧，叔叔节点存在且为红色**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2MTMxNjEx_size_16_color_FFFFFF_t_70 2][]

**如果此时pparen祖父节点不为根结点需要继续向上更新，此时将祖父节点作为当前节点**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2MTMxNjEx_size_16_color_FFFFFF_t_70 3][]

**情况2：当前节点为红，父节点为红，父节点在祖父节点左侧，叔叔节点不存在或为黑色**

**如果cur=parent->left**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2MTMxNjEx_size_16_color_FFFFFF_t_70 4][]

**如果cur=parent->right**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2MTMxNjEx_size_16_color_FFFFFF_t_70 5][]

**情况3：当前节点为红，父节点为红，父节点在祖父节点右侧，叔叔节点存在且为红色**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2MTMxNjEx_size_16_color_FFFFFF_t_70 6][]

**如果此时pparen祖父节点不为根结点需要继续向上更新，此时将祖父节点作为当前节点**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2MTMxNjEx_size_16_color_FFFFFF_t_70 7][]

**情况4：当前节点为红，父节点为红，父节点在祖父节点右侧，叔叔节点不存在或为黑色**

**如果cur=parent->right**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2MTMxNjEx_size_16_color_FFFFFF_t_70 8][]

**如果cur=parent->left**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2MTMxNjEx_size_16_color_FFFFFF_t_70 9][]

代码如下：

bool insert(const pair<k, v>& data)
    	{
    		//1,搜索树插入
    		if (_header->_parent == nullptr)//如果为空树
    		{
    			Node* root = new Node(data);
    			_header->_parent = root;
    			root->_parent = _header;
    			_header->_left = _header->_right = root;
    			root->_color = BLACK;
    			return true;
    		}
    		//从根节点开始搜索
    		Node* cur = _header->_parent;//_header->_parent即为root
    		Node* parent = nullptr;
    		while (cur)
    		{
    			parent = cur;
    			if (cur->_data.first == data.first)
    			{
    				return false;//不能重复
    			}
    			else if (cur->_data.first > data.first)
    			{
    				cur = cur->_left;
    			}
    			else
    				cur = cur->_right;
    		}
    		//创建待插入节点
    		cur = new Node(data);
    		if (parent->_data.first > cur->_data.first)//选择插入位置
    		{
    			parent->_left=cur;
    		}
    		else
    			parent->_right = cur;
    		cur->_parent = parent;
    		//结构调整 颜色调整
    		//默认插入红色节点  只有可能破坏规则：红色不能连续
    		//需要向上查是否有红色连续
    		while (cur != _header->_parent&&cur->_parent->_color == RED)
    		{
    			Node* pparent = cur->_parent->_parent;
    			parent = cur->_parent;
    			if (pparent->_left == parent)//父节点在祖父节点左边
    			{
    				Node* uncle = pparent->_right;
    				//uncle存在，且为红色
    				if (uncle&&uncle->_color == RED)
    				{
    					uncle->_color = parent->_color = BLACK;
    					pparent->_color = RED;
    					//继续向上更新
    					cur = pparent;
    				}
    				else //uncle不存在 或存在为黑色
    				{
    					//cout << "进行旋转" << endl;
    					//判断双旋场景
    					if (cur == parent->_right)  //左边的右边  左旋
    					{
    						RotateL(parent);
    						swap(cur, parent);//交换两个节点指向，退化成左边的左边，即仅右旋场景
    					}
    					RotateR(pparent);//左边的左边  右旋
    					parent->_color = BLACK;
    					pparent->_color = RED;
    					break;
    				}
    			}
    			else//父节点在祖父节点右边 pparent->_right == parent
    			{
    				Node* uncle = pparent->_left;
    				//uncle存在，且为红色
    				if (uncle&&uncle->_color == RED)
    				{
    					uncle->_color = parent->_color = BLACK;
    					pparent->_color = RED;
    					//继续向上更新
    					cur = pparent;
    				}
    				else
    				{
    					//cout << "进行旋转" << endl;
    					if (cur == parent->_left)//右边的左边
    					{
    						RotateR(parent);//先右旋
    						swap(cur, parent);//交换 cur和parent
    					}
    				    //无uncle节点 或uncle节点存在且为黑色    仅左旋  
    					RotateL(pparent);//右边的右边 左旋  cur 和parent 均在右侧
    					parent->_color = BLACK;
    					pparent->_color = RED;
    					break;
    				}
    			}
    		}
    		//直至根结点  根结点必须为黑色
    		_header->_parent->_color = BLACK;
    		//更新header左右指向
    		_header->_left = leftMost();
    		_header->_right = rightMost();
    		return true;
    	}

**其中左旋 右旋具体参考[AVL树的实现（图文详解）][AVL]注意到heade最终左右指向需要更新到最左和最右子节点**

Node* leftMost()
    	{
    		Node* cur = _header->_parent;
    		while (cur&&cur->_left)
    		{
    			cur = cur->_left;
    		}
    		return cur;
    	}
    
    	Node* rightMost()
    	{
    		Node* cur = _header->_parent;
    		while (cur&&cur->_right)
    		{
    			cur = cur->_right;
    		}
    		return cur;
    	}

*  ### 红黑树的检测 ###

红黑树的检测分为两步：  
**1. 检测其是否满足二叉搜索树(中序遍历是否为有序序列)  
2. 检测其是否满足红黑树的性质**

//红黑树验证
    	bool isBalance()
    	{
    		if (_header->_parent == nullptr)
    			return true;
    		Node* root = _header->_parent;
    		if (root->_color == RED)//判断根节点是否为黑色
    			return false;
    		//统计一条路径上黑色节点数目  作为每条路径黑色节点数参考值
    		int count = 0;
    		Node* cur = root;
    		while (cur)
    		{
    			if (cur->_color == BLACK)
    				count++;
    			cur = cur->_left;
    		}
    		//遍历每一条路径
    		int curcount = 0;
    		return travel(root, count, curcount);
    	}
    	bool travel(Node* root, int& count, int curcount)
    	{
    		if (root == nullptr)
    		{
    			if (count != curcount)
    				return false;
    			else
    				return true;
    		}
    		//判断节点是否为黑色
    		if (root->_color == BLACK)
    			curcount++;
    		//判断是否红色连续
    		if (root->_parent&&root->_color == RED && root->_parent->_color == RED)
    		{
    			return false;
    		}
    		return travel(root->_left, count, curcount) && travel(root->_right, count, curcount);
    	}

测试如下：

*  根为黑色

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2MTMxNjEx_size_16_color_FFFFFF_t_70 10][]

*  颜色更改

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2MTMxNjEx_size_16_color_FFFFFF_t_70 11][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2MTMxNjEx_size_16_color_FFFFFF_t_70 12][]

*  平衡判断

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2MTMxNjEx_size_16_color_FFFFFF_t_70 13][]

[AVL]: https://blog.csdn.net/qq_36131611/article/details/116903745
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2MTMxNjEx_size_16_color_FFFFFF_t_70]: /images/20221020/92781b5175db44869ca7c0a1a9a71903.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2MTMxNjEx_size_16_color_FFFFFF_t_70 1]: /images/20221020/176a2a35602f484783a3823506d15451.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2MTMxNjEx_size_16_color_FFFFFF_t_70 2]: /images/20221020/5903ee0f422a46d084291ee947a74573.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2MTMxNjEx_size_16_color_FFFFFF_t_70 3]: /images/20221020/95da4ae353c74c2abc9ec0be51617bfc.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2MTMxNjEx_size_16_color_FFFFFF_t_70 4]: /images/20221020/d37e933041a5409f9d912204eff740a9.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2MTMxNjEx_size_16_color_FFFFFF_t_70 5]: /images/20221020/dfa3936f4a244682b9064fa5cdc9f6c8.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2MTMxNjEx_size_16_color_FFFFFF_t_70 6]: /images/20221020/d8b561d3d19e4d59a662f8c720640806.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2MTMxNjEx_size_16_color_FFFFFF_t_70 7]: /images/20221020/af99172c8285412aa76c3719bc5dd173.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2MTMxNjEx_size_16_color_FFFFFF_t_70 8]: /images/20221020/9ad3ba4cb1794b06a5c0d758457ae36c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2MTMxNjEx_size_16_color_FFFFFF_t_70 9]: /images/20221020/804f7181bfc845c5adf4c549335868c8.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2MTMxNjEx_size_16_color_FFFFFF_t_70 10]: /images/20221020/c345fe0ef9b54d0486389b244f044c04.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2MTMxNjEx_size_16_color_FFFFFF_t_70 11]: /images/20221020/a2a86e534d3640edb74efe0f7dcb99a6.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2MTMxNjEx_size_16_color_FFFFFF_t_70 12]: /images/20221020/ac8bc7802fdf4a74bc6a8b99db649dda.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2MTMxNjEx_size_16_color_FFFFFF_t_70 13]: /images/20221020/14e3f30cb9a448cca34ba1ea862b4fd1.png