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

aosei

发布于 2024-01-23 15:20:09

1450

发布于 2024-01-23 15:20:09

文章被收录于专栏：csdn-nagiYcsdn-nagiY

一.红黑树的概念

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

红黑树的性质

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

上图就是一个红黑树。

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

二.红黑树的模拟实现

红黑树的节点

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

左指针（_left）
右指针（_right）
父指针（_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

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

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

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

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

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

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

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

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

当parent是grandfather的左节点时
当parent是grandfather的右节点时

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

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

uncle存在且为红

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

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

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

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

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

操作和和前面是差不多的

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

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

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

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

红黑树的删除 erase

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

三.红黑树的验证

空树也是红黑树
检查根节点是否是黑色
统计任意路径上黑节点的数量，作为基准值，之后再统计其他路径上的黑节点，若不等于基准值，则不是红黑树，返回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;
};

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2024-01-23，如有侵权请联系 cloudcommunity@tencent.com 删除

统计