【C++】红黑树

风中的云彩

发布于 2025-05-28 08:35:13

1110

文章被收录于专栏：C/C++的自学之路C/C++的自学之路

欲穷千里目，更上一层楼。

前言

这是我自己学习C++的第十六篇博客总结。后期我会继续把C++学习笔记开源至博客上。 上一期笔记是关于C++的AVL树知识，没看的同学可以过去看看： 【C++】AVL树-CSDN博客

https://cloud.tencent.com/developer/article/2518061

红黑树

红黑树的概念

红黑树是一种二叉搜索树。在红黑树中，每个节点除了保存键值之外，还增加了一个额外的颜色属性，颜色可以是红色或黑色。通过对从根节点到叶子节点的每条路径上的节点颜色进行约束，红黑树保证了任意一条路径的长度都不会超过其他路径长度的两倍，因此红黑树是接近平衡的。

红黑树的规则

1. 每个结点不是红色就是黑色 。 2. 根结点是黑色 。 3. 如果一个结点是红色的，则它的两个孩子结点必须是黑色的 。 4. 对于任意一个结点，从该结点到其所有NULL结点的简单路径上，均包含相同数量的黑色结点 。

红黑树的效率

红黑树 的查找效率为 O(logN) 。 AVL树 通过 高度差 直观的控制了平衡； 红黑树 通过 4条规则的颜色约束 ，间接的实现了近似平衡。 它们效率都是同一档次 ，但是相对而言，插入相同数量的结点， 红黑树的旋转次数是更少的 。

#include <iostream>
using namespace std;

enum Colour
{
	RED,
	BLACK
};

template<class K, class V>
struct RBTreeNode
{
	typedef RBTreeNode<K, V> Node;
	K _key;
	V _val;
	Node* _left;
	Node* _right;
	Node* _parent;
	Colour _col;
	RBTreeNode(const K& key, const V& val)
		: _key(key)
		, _val(val)
		, _col(RED)
		, _left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
	{}
};

template<class K, class V>
class RBTree
{
	typedef RBTreeNode<K, V> Node;
	typedef RBTree<K, V> Tree;
public:

	RBTree()
		:_root(nullptr)
	{}
	bool insert(const K& x, const V& y)
	{
		if (_root == nullptr)//如果插入的节点为根节点
		{
			_root = new Node(x, y);
			_root->_col = BLACK;
			return true;
		}

		Node* cur = _root;
		Node* parent = nullptr;
		while (cur != nullptr)//找到新节点的插入位置
		{
			if (cur->_key < x)
			{
				parent = cur;
				cur = cur->_right;
			}
			else if (cur->_key > x)
			{
				parent = cur;
				cur = cur->_left;
			}
			else
			{
				return false;//不允许有重复
			}
		}

		cur = new Node(x, y);
		if (parent->_key < cur->_key)//插入新节点
		{
			parent->_right = cur;
		}
		else
		{
			parent->_left = cur;
		}
		cur->_parent = parent;

		while (parent&&parent->_col==RED)//父节点为红色
		{
			Node* grandfather = parent->_parent;
			if (grandfather->_left == parent)//父节点在左侧
			{
				Node* uncle = grandfather->_right;
				if (uncle && uncle->_col == RED)//叔叔节点存在，且为红色
				{
					parent->_col = uncle->_col = BLACK;
					grandfather->_col = RED;
					cur = grandfather;
					parent = grandfather->_parent;
				}
				else//叔叔节点不存在；叔叔节点存在，且为黑色
				{
					if (cur == parent->_left)//插入节点在父节点左侧
					{
						Rotate_Right(grandfather);
						grandfather->_col = RED;
						parent->_col = BLACK;
					}
					else//插入节点在父节点右侧
					{
						Rotate_Left(parent);
						Rotate_Right(grandfather);
						grandfather->_col = RED;
						cur->_col = BLACK;
					}
					break;
				}
			}
			else
			{
				Node* uncle = grandfather->_left;
				if (uncle && uncle->_col == RED)
				{
					parent->_col = uncle->_col = BLACK;
					grandfather->_col = RED;
					cur = grandfather;
					parent = grandfather->_parent;
				}
				else
				{
					if (cur == parent->_right)
					{
						Rotate_Left(grandfather);
						grandfather->_col = RED;
						parent->_col = BLACK;
					}
					else
					{
						Rotate_Right(parent);
						Rotate_Left(grandfather);
						grandfather->_col = RED;
						cur->_col = BLACK;
					}
					break;
				}
			}
		}
		return true;
	}

	void InOrder()
	{
		_InOrder(_root);
	}

	Node* Find(const K& x)
	{
		Node* cur = _root;
		while (cur != nullptr)
		{
			if (cur->_key < x)
			{
				cur = cur->_right;
			}
			else if (cur->_key > x)
			{
				cur = cur->_left;
			}
			else
			{
				return cur;
			}
		}
		return nullptr;
	}

	void InOrder()
	{
		_InOrder(_root);
		cout << endl;
	}

	bool Check(Node* root, int blackNum, const int refNum)
	{
		if (root == nullptr)
		{
			// 前序遍历走到空时，意味着一条路径走完了
			if (refNum != blackNum)
			{
				cout << "存在黑色结点的数量不相等的路径" << endl;
				return false;
			}
			return true;
		}

		// 检查孩子不太方便，因为孩子有两个，且不一定存在，反过来检查父亲就方便多了
		if (root->_col == RED && root->_parent->_col == RED)
		{
			cout << root->_kv.first << "存在连续的红色结点" << endl;
			return false;
		}

		if (root->_col == BLACK)
		{
			blackNum++;
		}

		return Check(root->_left, blackNum, refNum)
			&& Check(root->_right, blackNum, refNum);
	}

	bool IsBalance()
	{
		if (_root == nullptr)
			return true;

		if (_root->_col == RED)
			return false;

		// 参考值
		int refNum = 0;
		Node* cur = _root;
		while (cur)
		{
			if (cur->_col == BLACK)
			{
				++refNum;
			}
			cur = cur->_left;
		}

		return Check(_root, 0, refNum);
	}
private:
	Node* _root;

	void _InOrder(Node* root)
	{
		if (root == nullptr)
		{
			return;
		}
		else
		{
			_InOrder(root->_left);
			cout << root->_key << " " << root->_val << endl;
			_InOrder(root->_right);
		}
	}

	void Rotate_Right(Node* parent)
	{
		Node* ppNode = parent->_parent;
		Node* sub_left = parent->_left;
		Node* subl_right = sub_left->_right;

		sub_left->_right = parent;
		parent->_parent = sub_left;
		parent->_left = subl_right;
		if (subl_right)
		{
			subl_right->_parent = parent;
		}
		if (ppNode == nullptr)
		{
			_root = sub_left;
			sub_left->_parent = nullptr;
		}
		else
		{
			if (ppNode->_left == parent)
			{
				ppNode->_left = sub_left;
			}
			else
			{
				ppNode->_right = sub_left;
			}
		}
	}

	void Rotate_Left(Node* parent)
	{
		Node* ppNode = parent->_parent;
		Node* sub_right = parent->_right;
		Node* subr_left = sub_right->_left;

		sub_right->_left = parent;
		parent->_parent = sub_right;
		parent->_right = subr_left;
		if (subr_left)
		{
			subr_left->_parent = parent;
		}
		if (ppNode == nullptr)
		{
			_root = sub_right;
			sub_right->_parent = nullptr;
		}
		else
		{
			if (ppNode->_left == parent)
			{
				ppNode->_left = sub_right;
			}
			else
			{
				ppNode->_right = sub_right;
			}
		}
	}

};
int main()
{
	RBTree<int, int> rbt;
	rbt.insert(999, 1);
	rbt.insert(998, 2);
	rbt.insert(997, 3);
	rbt.insert(996, 4);
	rbt.insert(995, 5);
	rbt.insert(994, 6);
	rbt.insert(993, 7);
	rbt.insert(992, 8);
	rbt.insert(991, 9);
	rbt.insert(990, 10);
	rbt.InOrder();
	return 0;
}

在这里获取最长路径和最短路径，检查最长路径不超过最短路径的2倍是不可行的，因为即使满足这个条件，红黑树也可能颜色不满足规则。当前看起来没有问题，但在后续继续插入节点时可能会出现问题。因此，我们应当检查四点规则，满足这四点规则能够保证最长路径不超过最短路径的2倍。规则1：枚举颜色类型，这样实现可以保证颜色不是黑色就是红色。规则2：直接检查根节点即可。规则3：通过前序遍历检查，当遇到红色节点时查找孩子节点不太方便，因为孩子节点有两个，且不一定存在。相反，检查父节点的颜色更为方便。规则4：在前序遍历中，使用形参记录从根节点到当前节点的黑色节点数量。遍历过程中，遇到黑色节点就增加黑色节点数量，遍历到空节点即可计算出一条路径的黑色节点数量。将任意一条路径的黑色节点数量作为参考值，依次比较即可。

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

原始发表：2025-05-27，如有侵权请联系 cloudcommunity@tencent.com 删除

parent