C++?STL容器详解之红黑树部分模拟实现

来源：jb51　　时间：2021/12/8 8:38:10　　对本文有异议

一、红黑树的概念

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

二、红黑树的性质

1. 每个结点不是红色就是黑色；

2. 根节点是黑色的；

3. 如果一个节点是红色的，则它的两个孩子结点是黑色的；

4. 对于每个结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数目的黑色结点；

5. 每个叶子结点都是黑色的(此处的叶子结点指的是空结点)；

满足上面的性质，红黑树就能保证其最长路径中节点个数不会超过最短路径节点个数的两倍。

三、红黑树节点的定义

enum Colour		//红黑树颜色枚举
{
	RED,
	BLACK,
};
 
template<class K, class V>
struct RBTreeNode					//节点结构体
{
	RBTreeNode<K, V>* _left;		//左子树
	RBTreeNode<K, V>* _right;		//右子树
	RBTreeNode<K, V>* _parent;		//父节点
 
	pair<K, V> _kv;
 
	Colour _col;
 
	RBTreeNode(const pair<K, V>& kv)	//构造函数
		: _left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
		, _kv(kv)
		, _col(RED)
	{}
};

插入时默认为红色节点，因为红色可能会破坏规则3，黑色一定会破坏规则4，所以默认红色。

四、红黑树结构?

为了后续实现关联式容器简单，红黑树的实现中增加一个头结点，因为跟节点必须为黑色，为了与根节点进行区分，将头结点给成黑色，并且让头结点的 parent 域指向红黑树的根节点，left域指向红黑树中最小的节点，right域指向红黑树中最大的节点，如下:

五、红黑树的插入操作

红黑树是在二叉搜索树的基础上加上其平衡限制条件，因此红黑树的插入可分为两步：

1. 按照二叉搜索的树规则插入新节点：

	pair<Node*, bool> Insert(const pair<K, V>& kv)
	{
		if (_root == nullptr)
		{
			_root = new Node(kv);
			_root->_col = BLACK;
			return make_pair(_root, 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 make_pair(cur, false);
			}
		}
 
		Node* newNode = new Node(kv);
		newNode->_col = RED;
		if (parent->_kv.first > kv.first)
		{
			parent->_left = newNode;
			newNode->_parent = parent;
		}
		else
		{
			parent->_right = newNode;
			newNode->_parent = parent;
		}
		cur = newNode;
 
		while (parent && parent->_col == RED)		//违反规则三
		{
 
		}
 
		_root->_col = BLACK;		//插入结束再次将根变为黑
 
		return make_pair(cur, true);
	}

2. 检测新节点插入后，红黑树的性质是否造到破坏

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

cur为当前节点，p为父节点，g为祖父节点，u为叔叔节点

情况一：cur为红，p为红，g为黑，u存在且为红

如果g是根节点，调整完成后，需要将g改为黑色，如果g是子树，g一定有父节点，且如果为红色呃，继续向上调整。

将p,u改为黑，g改为红，然后把g当成cur，继续向上调整。

情况二: cur为红，p为红，g为黑，u不存在/u为黑

u的情况有两种：

1.如果u节点不存在，则cur一定是新插入节点，因为如果cur不是新插入节点，则cur和p一定有一个节点的颜色是黑色，就不满足性质4：每条路径黑色节点个数相同。

2.如果u节点存在，则其一定是黑色的，那么cur节点原来的颜色一定是黑色的，现在看到其是红色的原因是因为cur的子树在调整的过程中将cur节点的颜色由黑色改成红色。

p为g的左孩子，cur为p的左孩子，则进行右单旋转；

p为g的右孩子，cur为p的右孩子，则进行左单旋转。

p变黑，g变红。

情况三: cur为红，p为红，g为黑，u不存在/u为黑

需要进行双旋。

代码实现：

while (parent && parent->_col == RED)		//违反规则三
		{
			Node* grandfather = parent->_parent;
 
			if (parent == grandfather->_left)			//左半边
			{
				Node* uncle = parent->_right;
 
				if (uncle && uncle->_col == red)		//情况一
				{
					uncle->_col = BLACK;
					grandfather->_col = RED;
					parent->_col = BLACK;
 
					cur = grandfather;			//迭代
					parent = cur->_parent;
				}
				else							//情况2.3
				{
					if (cur == parent->_left)		//单侧
					{
						RotateR(grandfather);
 
						grandfather->_col = RED;
						parent->_col = BLACK;
					}
					else					//折
					{
						RotateL(parent);
						RotateR(grandfather);
 
						cur->_col = BLACK;
						grandfather->_col = RED;
					}
 
					break;		//黑色数量无变化，不需要向上
				}
			}
			else         // parent == grandfather->_right
			{
				Node* uncle = parent->_left;
				if (uncle && uncle->_col == red)		//情况一
				{
					uncle->_col = BLACK;
					grandfather->_col = RED;
					parent->_col = BLACK;
 
					cur = grandfather;			//迭代
					parent = cur->_parent;
				}
				else							//情况2.3
				{
					if (cur == parent->_right)		//单侧
					{
						RotateL(grandfather);
 
						grandfather->_col = RED;
						parent->_col = BLACK;
					}
					else					//折
					{
						RotateR(parent);
						RotateL(grandfather);
 
						cur->_col = BLACK;
						grandfather->_col = RED;
					}
 
					break;
				}
			}
		}

六、代码

#pragma once
#include<iostream>
#include<assert.h>
 
using namespace std;
 
enum Colour		//红黑树颜色枚举
{
	RED,
	BLACK,
};
 
template<class K, class V>
struct RBTreeNode					//节点结构体
{
	RBTreeNode<K, V>* _left;		//左子树
	RBTreeNode<K, V>* _right;		//右子树
	RBTreeNode<K, V>* _parent;		//父节点
 
	pair<K, V> _kv;
 
	Colour _col;
 
	RBTreeNode(const pair<K, V>& kv)	//构造函数
		: _left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
		, _kv(kv)
		, _col(RED)
	{}
};
 
template<class K, class V>
class RBTree
{
	typedef RBTreeNode<K, V> Node;
private:
	Node* _root;
 
	void RotateR(Node* parent)
	{
		Node* subL = parent->_left;
		Node* subLR = subL->_right;
		Node* parentP = parent->_parent;
 
		if (subLR)							//左子树的右子树连接到父的右
			subLR->_parent = parent;
 
		parent->_left = subLR;
		subL->_right = parent;
		parent->_parent = subL;
 
		// 如果parent是根节点，根新指向根节点的指针
		if (parent == _root)
		{
			_root = subL;
			subL->_parent = nullptr;
		}
		else
		{
			// 如果parent是子树，可能是其双亲的左子树，也可能是右子树
			if (parentP->_left == parent)
				parentP->_left = subL;
			else
				parentP->_right = subL;
 
			subL->_parent = parentP;
		}
	}
 
	void RotateL(Node* parent)
	{
		Node* subR = parent->_right;
		Node* subRL = subR->_left;
		Node* parentP = parent->_parent;
 
		if (subRL)
			subRL->_parent = parent;
 
		parent->_right = subRL;
		subR->_left = parent;
		parent->_parent = subR;
 
		// 如果parent是根节点，根新指向根节点的指针
		if (parent == _root)
		{
			_root = subR;
			subR->_parent = nullptr;
		}
		else
		{
			// 如果parent是子树，可能是其双亲的左子树，也可能是右子树
			if (parentP->_left == parent)
				parentP->_left = subR;
			else
				parentP->_right = subR;
 
			subR->_parent = parentP;
		}
	}
 
	void _Destory(Node* root)
	{
		if (root == nullptr)
		{
			return;
		}
 
		_Destory(root->_left);
		_Destory(root->_right);
 
		delete root;
	}
 
public:
	RBTree()
		:_root(nullptr)
	{}
 
	~RBTree()
	{
		_Destory(_root);
		_root = nullptr;
	}
 
	Node* Find(const K& key)
	{
		Node* cur = _root;
		while (cur)
		{
			if (cur->_kv.first > key)
			{
				cur = cur->_left;
			}
			else if (cur->_kv < key)
			{
				cur = cur->_right;
			}
			else
			{
				return cur;
			}
		}
 
		return nullptr;
	}
 
	pair<Node*, bool> Insert(const pair<K, V>& kv)
	{
		if (_root == nullptr)
		{
			_root = new Node(kv);
			_root->_col = BLACK;
			return make_pair(_root, 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 make_pair(cur, false);
			}
		}
 
		Node* newNode = new Node(kv);
		newNode->_col = RED;
		if (parent->_kv.first > kv.first)
		{
			parent->_left = newNode;
			newNode->_parent = parent;
		}
		else
		{
			parent->_right = newNode;
			newNode->_parent = parent;
		}
		cur = newNode;
 
		while (parent && parent->_col == RED)		//违反规则三
		{
			Node* grandfather = parent->_parent;
 
			if (parent == grandfather->_left)			//左半边
			{
				Node* uncle = parent->_right;
 
				if (uncle && uncle->_col == red)		//情况一
				{
					uncle->_col = BLACK;
					grandfather->_col = RED;
					parent->_col = BLACK;
 
					cur = grandfather;			//迭代
					parent = cur->_parent;
				}
				else							//情况2.3
				{
					if (cur == parent->_left)		//单侧
					{
						RotateR(grandfather);
 
						grandfather->_col = RED;
						parent->_col = BLACK;
					}
					else					//折
					{
						RotateL(parent);
						RotateR(grandfather);
 
						cur->_col = BLACK;
						grandfather->_col = RED;
					}
 
					break;		//黑色数量无变化，不需要向上
				}
			}
			else         // parent == grandfather->_right
			{
				Node* uncle = parent->_left;
				if (uncle && uncle->_col == red)		//情况一
				{
					uncle->_col = BLACK;
					grandfather->_col = RED;
					parent->_col = BLACK;
 
					cur = grandfather;			//迭代
					parent = cur->_parent;
				}
				else							//情况2.3
				{
					if (cur == parent->_right)		//单侧
					{
						RotateL(grandfather);
 
						grandfather->_col = RED;
						parent->_col = BLACK;
					}
					else					//折
					{
						RotateR(parent);
						RotateL(grandfather);
 
						cur->_col = BLACK;
						grandfather->_col = RED;
					}
 
					break;
				}
			}
		}
 
		_root->_col = BLACK;		//插入结束再次将根变为黑
 
		return make_pair(newNode, true);
	}
};