【C++】红黑树的实现

文章目录

📕 概念
- 特性
📕 红黑树具体实现
📕 源代码

📕 概念

红黑树，是一种

二叉搜索树

，但在每个结点上增加一个存储位表示结点的颜色，可以是Red或Black。通过对任何一条从根到叶子的路径上各个结点

着色方式的限制

，红黑树确保

没有一条路径会比其他路径长出俩倍

，因而是接近平衡的。

特性

每个结点不是红色就是黑色。
根节点是黑色的。
如果一个节点是红色的，则它的两个孩子结点是黑色的。
对于每个结点，从该结点到其所有后代叶结点的简单路径上，均包含

相同数目的黑色结点

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

如下，是一个红黑树的例子。其叶子节点都是黑色，指的是最后的 NULL 节点。

该红黑树一共有 11 条路径，因为有 11 个 NULL 节点（叶子节点）。

请添加图片描述

满足上面的性质，红黑树就能保证：其

最长路径

中节点个数不会超过

最短路径

节点个数的

两倍

。

其实很好理解，每个节点非红即黑，红色节点不允许连续。那么最短的路径的节点一定是全黑的（假设有 n 个黑色节点），最长路径的节点是一黑一红，而由于每条路径上黑色节点数目相同，所以最长路径也有n个黑色节点，由于一黑一红，所以红色节点也是n个，最长路径有 2n 个节点。这就是其原理。

📕 红黑树具体实现

节点定义

如下，红黑树里面需要有颜色，可以用枚举。

同时，当 new 一个节点的时候，默认是红色，这是因为，如果插入一个节点，默认为黑色，那么就会导致这个节点所在路径的黑色节点数目+1，原本一棵红黑树的结构收到破坏（性质4不满足）。

所以，默认是红色可以减少插入新节点对红黑树造成的影响。

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)
	{}
};

结构框架

如下，和 AVL 树大致类似，区别只是 AVL 树里面的平衡因子换成了红黑树的颜色。

#pragma once
#include<iostream>
#include<cassert>

using namespace std;

namespace simulate {
	
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 struct RBTreeNode<K, V> Node;

public:
	// 成员方法

private:
	Node* _root;
};

}

插入

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

按照二叉搜索的树规则插入新节点。
检测新节点插入后，红黑树的性质是否造到破坏。

对于第一步，就不必赘述了，过于简单。

对于第二步，因为新节点的默认颜色是红色，因此：如果其

双亲节点的颜色是黑色

，没有违反红黑树任何性质，则

不需要调整

；但当

新插入节点的双亲节点颜色为红色时，就违反了性质三不能有连在一起的红色节点

，此时需要对红黑树分情况来讨论：

情况一

cur为红，p为红，g为黑，u存在且为红。

cur为新插入的节点，p为 cur 的父亲，g 为 cur 的祖父，u 为 cur 的叔叔（p的兄弟）。

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

因为在当前这棵树（可能是子树）其余部分忽略，只剩下 g、p、u三个节点。并且看为两层，g为第一层，p、u 为第二层，当前这棵树，任意一条路径，都会经过第一层，也必然会经过第二层。

修改颜色前，第一层的一个节点，颜色是黑色；第二层的两个节点，颜色是红色，所以任意一条路径，经过这两层，会有一个黑色节点。

修改颜色后，第一层的一个节点，颜色是红色；第二层的两个节点，颜色是黑色，所以，任意一条路径，经过这两层，也必然会有一个黑色节点。

我们只改变了这两层的颜色，但是改变前后，任意一条路径经过这两层黑色节点的数目并没有发生改变！

而如果 g 就是根节点，则无法向上继续修改颜色了，根据规则根节点要是黑色，将其改成黑色。根节点颜色变成黑色，每条路径的黑色节点个数在修改根节点颜色之前的基础上 +1，那么，修改前后，每条路径黑色节点个数都是相等的。

请添加图片描述

如果修改之后，g 并不是根节点，那么遵循如下规则：

如果 g 的父亲节点颜色是黑色，可以不修改。
如果 g 的父亲节点颜色是红色，把 g 当作 cur ，继续向上调整。

请添加图片描述

情况二

cur为红，p为红，g为黑，u不存在 / u存在且为黑

解决方式：

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

p、g变色——p变黑，g变红。

如下，查看各个路径的黑色节点数目。很显然，旋转前后，a、b、c、d、e 任何一个区域内，任何一个路径（以 NULL 为叶子节点），其黑色节点的数目没有改变。

请添加图片描述

情况三

cur为红，p为红，g为黑，u不存在/u存在且为黑

解决方法：

p为g的左孩子，cur为p的右孩子，则针对p做左单旋转；相反，p为g的右孩子，cur为p的左孩子，则针对p做右单旋转。

则转换成了情况2，然后

依据情况二来处理

。

请添加图片描述

虽然这里分了三类，但是每一类都会面临一个问题： p 是 g 的左孩子，还是 g 的右孩子？

所以，实际写代码的时候，也可以按照 p 是 g 的左/右孩子来分类，然后三种情况一次在每一类中实现。

	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->_right = cur;
		}
		else if (parent->_kv.first > kv.first) {
			parent->_left = cur;
		}
		cur->_parent = parent;


		// 调整颜色
		while (parent && parent->_col == RED) {
			Node* grandfather = parent->_parent;
			if (parent == grandfather->_left) {
				Node* uncle = grandfather->_right;
				if (uncle && uncle->_col == RED) { // uncle 为红色
					parent->_col = BLACK;
					uncle->_col = BLACK;
					grandfather->_col = RED;

					// 继续调整
					cur = grandfather;
					parent = cur->_parent;
				}
				else { // uncle不存在 or 存在且为黑
					if (cur == parent->_left) {
						RotateR(grandfather);
						parent->_col = BLACK;
						grandfather->_col = RED;
						//cur->_col = RED;
					}
					else if (cur == parent->_right) {
						RotateL(parent);
						RotateR(grandfather);
						cur->_col = BLACK;
						grandfather->_col = RED;
						parent->_col = RED;
					}

					break;
				}
			}
			else { // if (parent == grandfather->_right)
				Node* uncle = grandfather->_left;
				if (uncle && uncle->_col == RED) { // uncle 为红色
					parent->_col = BLACK;
					uncle->_col = BLACK;
					grandfather->_col = RED;

					// 继续调整
					cur = grandfather;
					parent = cur->_parent;
				}
				else { // uncle不存在 or 存在且为黑
					if (cur == parent->_right) {
						RotateL(grandfather);
						parent->_col = BLACK;
						grandfather->_col = RED;
						//cur->_col = RED;
					}
					else { // cur == parent->_left
						RotateR(parent);
						RotateL(grandfather);
						cur->_col = BLACK;
						parent->_col = RED;
						grandfather->_col = RED;
					}

					break;
				}
			}
		}

		_root->_col = BLACK;
		return true;
	}

判断是否满足红黑树

要从三个方面考虑：1**.根节点颜色。2.任意一条路径的黑色节点数目。3.是否有两个连续的红色节点**。

如下，_isBalance() 是辅助 isBalance() 的，在调用的时候，只需要调用 isBalance() 即可！_isBalance() 包含三个参数，第一个是节点指针；第二个是根节点到当前节点的路径中，黑色节点的个数；第三个是任意一条路径的黑色节点个数。

每当

走完一条路径

，用 blackNum 和 benchmark 进行比较即可，

有任意一个 blackNum 和 benchmark 不相等，就说明每一条路径的黑色节点个数并不完全相同

！

		bool isBalance()
		{
			if (_root->_col == RED)
			{
				cout << "根节点的颜色是红色" << endl;
				return false;
			}

			int benchmark = 0; // 任意一条路径的黑色节点数目
			Node* tmp = _root;
			while (tmp)
			{
				if (tmp->_col == BLACK)
					benchmark++;
				tmp = tmp->_left;
			}

			return _isBalance(_root, 0, benchmark);
		}



		bool _isBalance(Node* root, int blackNum, int benchmark)
		{
			if (root == nullptr)
			{
				if (blackNum == benchmark)
					return true;
				else
				{
					cout << "某条链路黑色节点数目错误！" << endl;
					return false;
				}
			}

			if (root->_col == BLACK)
				++blackNum;
			else
			{
				if (root->_parent && root->_parent->_col == RED)
				{
					cout << "存在两个连续的红色节点" << endl;
					return false;
				}
			}

			return _isBalance(root->_left, blackNum, benchmark)
				&& _isBalance(root->_right, blackNum, benchmark);
		}

📕 源代码

#pragma once
#include<iostream>
#include<cassert>

using namespace std;

namespace simulate
{
	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 struct RBTreeNode<K, V> Node;

	public:

		~RBTree()
		{
			Delete(_root);
			_root = nullptr;
		}

		Node* find(pair<K, V> kv)
		{
			Node* cur = _root;
			while (cur)
			{
				if (kv.first > cur->_kv.first)
				{
					cur = cur->_right;
				}
				else if (kv.first < cur->_kv.first)
				{
					cur = cur->_left;
				}
				else
					return cur;
			}

			return nullptr;
		}

		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->_right = cur;
			}
			else if (parent->_kv.first > kv.first)
			{
				parent->_left = cur;
			}
			cur->_parent = parent;


			// 调整颜色
			while (parent && parent->_col == RED)
			{
				Node* grandfather = parent->_parent;
				if (parent == grandfather->_left)
				{
					Node* uncle = grandfather->_right;
					if (uncle && uncle->_col == RED) // uncle 为红色
					{
						parent->_col = BLACK;
						uncle->_col = BLACK;
						grandfather->_col = RED;

						// 继续调整
						cur = grandfather;
						parent = cur->_parent;
					}
					else // uncle不存在 or 存在且为黑
					{
						if (cur == parent->_left)
						{
							RotateR(grandfather);
							parent->_col = BLACK;
							grandfather->_col = RED;
							//cur->_col = RED;
						}
						else if (cur == parent->_right)
						{
							RotateL(parent);
							RotateR(grandfather);
							cur->_col = BLACK;
							grandfather->_col = RED;
							parent->_col = RED;
						}

						break;
					}
				}
				else // if (parent == grandfather->_right)
				{
					Node* uncle = grandfather->_left;
					if (uncle && uncle->_col == RED) // uncle 为红色
					{
						parent->_col = BLACK;
						uncle->_col = BLACK;
						grandfather->_col = RED;

						// 继续调整
						cur = grandfather;
						parent = cur->_parent;
					}
					else // uncle不存在 or 存在且为黑
					{
						if (cur == parent->_right)
						{
							RotateL(grandfather);
							parent->_col = BLACK;
							grandfather->_col = RED;
							//cur->_col = RED;
						}
						else // cur == parent->_left
						{
							RotateR(parent);
							RotateL(grandfather);
							cur->_col = BLACK;
							parent->_col = RED;
							grandfather->_col = RED;
						}

						break;
					}
				}
			}

			_root->_col = BLACK;
			return true;
		}

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

		bool isBalance()
		{
			if (_root->_col == RED)
			{
				cout << "根节点的颜色是红色" << endl;
				return false;
			}

			int benchmark = 0;
			Node* tmp = _root;
			while (tmp)
			{
				if (tmp->_col == BLACK)
					benchmark++;
				tmp = tmp->_left;
			}

			return _isBalance(_root, 0, benchmark);
		}

		void Inorder()
		{
			_Inorder(_root);
		}

	private:

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

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

		bool _isBalance(Node* root, int blackNum, int benchmark)
		{
			if (root == nullptr)
			{
				if (blackNum == benchmark)
					return true;
				else
				{
					cout << "某条链路黑色节点数目错误！" << endl;
					return false;
				}
			}

			if (root->_col == BLACK)
				++blackNum;
			else
			{
				if (root->_parent && root->_parent->_col == RED)
				{
					cout << "存在两个连续的红色节点" << endl;
					return false;
				}
			}

			return _isBalance(root->_left, blackNum, benchmark)
				&& _isBalance(root->_right, blackNum, benchmark);
		}

		int _Height(Node* root)
		{
			if (root == nullptr) return 0;

			int leftH = _Height(root->_left);
			int rightH = _Height(root->_right);

			return leftH > rightH ? leftH + 1 : rightH + 1;
		}



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

			Delete(root->_left);
			Delete(root->_right);
			free(root);
		}

		void RotateL(Node* parent)
		{
			Node* subR = parent->_right;
			Node* subRL = subR->_left;

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

			Node* pparent = parent->_parent;
			subR->_left = parent;
			parent->_parent = subR;

			if (pparent == nullptr)
			{
				_root = subR;
				_root->_parent = nullptr;
			}
			else
			{
				if (parent == pparent->_left)
				{
					pparent->_left = subR;
				}
				else
				{
					pparent->_right = subR;
				}
				subR->_parent = pparent;
			}


		}



		void RotateR(Node* parent)
		{
			Node* subL = parent->_left;
			Node* subLR = subL->_right;

			Node* pparent = parent->_parent;
			subL->_right = parent;
			parent->_parent = subL;

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


			if (pparent == nullptr)
			{
				subL->_parent = nullptr;
				_root = subL;
			}
			else
			{
				if (parent == pparent->_left)
				{
					pparent->_left = subL;
				}
				else
				{
					pparent->_right = subL;
				}

				subL->_parent = pparent;
			}

		}

	private:
		Node* _root;
	};

}

原文链接：https://blog.csdn.net/m0_65679465/article/details/130604163

文章目录

📕 概念

特性

📕 红黑树具体实现

节点定义

结构框架

插入

判断是否满足红黑树

📕 源代码

你可能也喜欢