菜鸟追梦旅行

这个屌丝很懒，什么也没留下！

热门标签

C++:红黑树_c++红黑树

作者：菜鸟追梦旅行 | 2024-03-16 01:14:45

踩

c++红黑树

一.红黑树介绍

1.红黑树的概念

2.红黑树的性质

思考：如何保证最长的路径不超过最短路径的2倍？

情况一: 红叔：叔父爷变色，爷变新结点。（cur为红，p为红，g为黑，u存在且为红）

（1）具体情况1

（2）具体情况2：相当于重复具体情况1

情况一: 黑叔LL型：右单旋，父,爷变色。（cur为红，p为红，g为黑，u存在且为红）

情况二: cur为红，p为红，g为黑，u不存在/u存在且为黑，但是cur是p的左

（1）具体情况1：cur为红，p为红，g为黑，u不存在，但是cur是p的左

（2）具体情况2：cur为红，p为红，g为黑，u存在且为黑，但是cur是p的左

情况三: cur为红，p为红，g为黑，u不存在/u存在且为黑，但是cur是p的右

（1）具体情况1：cur为红，p为红，g为黑，u不存在，但是cur是p的右

一.红黑树介绍

1.红黑树的概念

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

Black。通过对 任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路

径会比其他路径长出俩倍，因而是 接近平衡的。（最长的路径不超过最短路径的2倍，近似平衡）

2.红黑树的性质

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

2. 根节点是黑色的

3. 如果一个节点是红色的，则它的两个孩子结点是黑色的 (没有连续的红色节点)

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

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

思考：如何保证最长的路径不超过最短路径的2倍？

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

最长的路径不超过最短路径的2倍
最短:全黑
最长:一黑一红间隔

3.小练习

4.黑高

5.红黑树和AVL树比较

100w数据
AVL树高度: 20行左右
红黑树高度: 40行左右，但旋转次数少很多

4.新增节点给红色

新增节点是红色，可能破坏3.(没有连续的红色节点）
新增节点是黑色，一定破坏4.(每条路径都包含相同数量黑色节点),规则4很难维护
因此新插入的节点都染成红色，因为他下面有黑色的null叶节点，因此不是叶节点，不用给成黑色。

5.红黑树的插入操作

规则：（染色=变色）

叶子都是黑色的null节点，下面没有画出来而已。

情况一: 红叔：叔父爷变色，爷变新结点。（cur为红，p为红，g为黑，u存在且为红）

对应上面的红叔情况，叔父爷变色，爷变为新节点。即：叔父p,u变黑色，爷g变红。

如果g是子树，则继续将g当成cur,继续向上调整；若如果g是根，则“爷变新结点”，即：将爷g当作新节点，又回到上面判断新节点的条件：新结点是根—染为黑色，新结点非根—染为红色。则将g染为黑色即可。

（1）具体情况1

a、b、c、d、e都是空，则它们都是黑色的null叶节点。

（2）具体情况2：相当于重复具体情况1

cur是新增节点，将p,u改为黑，g改为红，把g当成cur,继续向上调整。此时g/cur 这个节点看成新增节点，把他的父pp亲和叔叔uu改成黑色，gg改成红色，然后如果是子树就还能继续像这样向上调整；如果是根

情况一: 黑叔LL型：右单旋，父,爷变色。（cur为红，p为红，g为黑，u存在且为红）

对应上面的黑叔情况，叔父爷变色，爷变为新节点。即：叔父p,u变黑色，爷g变红。

情况二: cur为红，p为红，g为黑，u不存在/u存在且为黑，但是cur是p的左

（1）具体情况1：cur为红，p为红，g为黑，u不存在，但是cur是p的左

p,g右单旋后，把p改成黑色，g改成红色。因为这个局部子树的根节点p是黑色，所以跟上面的数颜色也没关系，所以不用继续向上调整。

（2）具体情况2：cur为红，p为红，g为黑，u存在且为黑，但是cur是p的左

通过上面的分析，u如果存在且为黑那么cur原来一定是黑色的，作为下面子树的祖父，由情况一变更过来，原来是黑色，现在变红。

操作是右单旋p，g：p的右给g的左，把g再给p的右，p做根节点。最后p和g变色，p变黑，g变红

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

x y m n几个位置中某个位置子树插入红节点，引发cur从黑变红
xymnabd e等子树一定是包含相同数量黑色节点的红黑树子树

①到②是情况一cur(y位置)为红，p为红，g为黑，u存在且为红的变化，②到③才是这里的 cur为红，p为红，g为黑，u存在且为黑 的情况，操作是右单旋p,g，g变红，p变黑。

情况三: cur为红，p为红，g为黑，u不存在/u存在且为黑，但是cur是p的右

情况二和情况三的区别

情况二：p是g的左，cur是p的左 -- 单旋
情况三：p是g的左，cur是p的右 -- 双旋

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

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

则转换成了情况 2

①到②p和cur进行左单旋，②到③把cur和p交换，最终转换成了情况二

（1）具体情况1：cur为红，p为红，g为黑，u不存在，但是cur是p的右

双旋+变色

（2）具体情况2：cur为红，p为红，g为黑，u存在且为黑，但是cur是p的右

6.检查红黑树合法性

1、遇到红色节点就检查孩子，但是建议改成遇到红色节点检查父亲，这样好实现。（遇到红色节点就检查孩子不好检查，因为孩子可能为空可能不为空）
2、每条路径黑色节点如何检查?（下图有11条路径，走到空为一条路径）
前序递归遍历树，求出每条路径黑色节点的数量


// 检测是否有连续红色节点和各路径黑节点个数是否相同 的支线函数
    bool _IsValidRBTree(Node* pRoot, size_t k, const size_t blackCount)
	{//k用来记录每条路径中黑色节点的个数， blackCount是主要函数传进来的“任意一个路径的黑色
//节点个数”作基准值，只要有k和基准值比较不同就违反了性质四：每条路径中黑色节点的个数必须相同
		//走到null之后，k就是整个路径的黑色节点个数，判断k和black是否相等
		if (nullptr == pRoot)
		{
			if (k != blackCount)
			{
				cout << "违反性质四：每条路径中黑色节点的个数必须相同" << endl;
				return false;
			}
			return true;
		}
 
		// 统计黑色节点的个数
		if (BLACK == pRoot->_col)
			k++;
 
		// 顺便检测当前节点与其双亲是否都为红色
	if (RED == pRoot->_col && pRoot->_parent && pRoot->_parent->_col == RED)
		{
			cout << "违反性质三：存在连在一起的红色节点" << endl;
			return false;
		}
 
		return _IsValidRBTree(pRoot->_left, k, blackCount) &&
			_IsValidRBTree(pRoot->_right, k, blackCount);
	}
	bool IsBalanceTree()    //检查红黑树合法性的主要函数
	{
		// 检查红黑树几条规则
 
		Node* pRoot = _root;
		// 1.只要是空树就是红黑树
		if (nullptr == pRoot)
			return true;
 
		// 2.检测根节点是否满足情况
		if (BLACK != pRoot->_col)
		{
			cout << "违反红黑树性质二：根节点必须为黑色" << endl;
			return false;
		}
 
		// 获取任意一条路径中黑色节点的个数 -- 比较基准值
		size_t blackCount = 0;
		Node* pCur = pRoot;
		while (pCur)
		{
			if (BLACK == pCur->_col)
				blackCount++;
 
			pCur = pCur->_left;
		}
 
		// 检测是否有连续红色节点和各路径黑节点个数是否相同
		size_t k = 0;    //k用来记录路径中黑色节点的个数
		return _IsValidRBTree(pRoot, k, blackCount);
	}

红黑树总代码


#pragma once
 
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)
		:_kv(kv)
		, _left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
		, _col(RED)
	{}
};
 
template<class K, class V>
struct RBTree
{
	typedef RBTreeNode<K, V> Node;
public:
	bool Insert(const pair<K, V>& kv)
	{
		// 1、搜索树的规则插入
		// 2、看是否违反平衡规则，如果违反就需要处理：旋转
		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->_right;
			}
			else if (cur->_kv.first > kv.first)
			{
				parent = cur;
				cur = cur->_left;
			}
			else
			{
				return false;
			}
		}
 
		cur = new Node(kv);
		cur->_col = RED;  
		if (parent->_kv.first < kv.first)
		{
			parent->_right = cur;
		}
		else
		{
			parent->_left = cur;
		}
 
		cur->_parent = parent;
 
		// 存在连续红色节点
		while (parent && parent->_col == RED)
		{
			Node* grandfater = parent->_parent;
			assert(grandfater);
 
			if (grandfater->_left == parent)
			{
				Node* uncle = grandfater->_right;
				// 情况一：
				if (uncle && uncle->_col == RED) // 叔叔存在且为红
				{
					// 变色
					parent->_col = uncle->_col = BLACK;
					grandfater->_col = RED;
 
					// 继续往上处理
					cur = grandfater;
					parent = cur->_parent;
				}
				else // 叔叔不存在 或者 叔叔存在且为黑
				{
					if (cur == parent->_left) // 单旋
					{
						//     g
						//   p
						// c
						RotateR(grandfater);
						parent->_col = BLACK;
						grandfater->_col = RED;
					}
					else // 双旋
					{
						//     g
						//   p
						//     c 
						RotateL(parent);
						RotateR(grandfater);
						cur->_col = BLACK;
						grandfater->_col = RED;
					}
 
					break;
				}
			}
			else //(grandfater->_right == parent)
			{
				Node* uncle = grandfater->_left;
				// 情况一：
				if (uncle && uncle->_col == RED)
				{
					// 变色
					parent->_col = uncle->_col = BLACK;
					grandfater->_col = RED;
 
					// 继续往上处理
					cur = grandfater;
					parent = cur->_parent;
				}
				else
				{
					if (cur == parent->_right)
					{
						// g
						//   p
						//     c 
						RotateL(grandfater);
						parent->_col = BLACK;
						grandfater->_col = RED;
					}
					else // 双旋
					{
						// g
						//   p
						// c
						RotateR(parent);
						RotateL(grandfater);
						cur->_col = BLACK;
						grandfater->_col = RED;
					}
 
					break;
				}
			}
		}
 
		_root->_col = BLACK;
 
		return true;
	}
 
	vector<vector<int>> levelOrder() {
		vector<vector<int>> vv;
		if (_root == nullptr)
			return vv;
 
		queue<Node*> q;
		int levelSize = 1;
		q.push(_root);
 
		while (!q.empty())
		{
			// levelSize控制一层一层出
			vector<int> levelV;
			while (levelSize--)
			{
				Node* front = q.front();
				q.pop();
				levelV.push_back(front->_kv.first);
				if (front->_left)
					q.push(front->_left);
 
				if (front->_right)
					q.push(front->_right);
			}
			vv.push_back(levelV);
			for (auto e : levelV)
			{
				cout << e << " ";
			}
			cout << endl;
 
			// 上一层出完，下一层就都进队列
			levelSize = q.size();
		}
 
		return vv;
	}
 
	void RotateL(Node* parent)
	{
		Node* subR = parent->_right;
		Node* subRL = subR->_left;
 
		parent->_right = subRL;
		if (subRL)
			subRL->_parent = parent;
 
		Node* ppNode = parent->_parent;
 
		subR->_left = parent;
		parent->_parent = subR;
 
		if (parent == _root)
		{
			_root = subR;
			_root->_parent = nullptr;
		}
		else
		{
			if (parent == ppNode->_left)
			{
				ppNode->_left = subR;
			}
			else
			{
				ppNode->_right = subR;
			}
 
			subR->_parent = ppNode;
		}
	}
 
	void RotateR(Node* parent)
	{
		Node* subL = parent->_left;
		Node* subLR = subL->_right;
 
		parent->_left = subLR;
		if (subLR)
			subLR->_parent = parent;
 
		Node* ppNode = parent->_parent;
 
		subL->_right = parent;
		parent->_parent = subL;
 
		if (parent == _root)
		{
			_root = subL;
			_root->_parent = nullptr;
		}
		else
		{
			if (ppNode->_left == parent)
			{
				ppNode->_left = subL;
			}
			else
			{
				ppNode->_right = subL;
			}
			subL->_parent = ppNode;
		}
 
	}
 
	int _maxHeight(Node* root)
	{
		if (root == nullptr)
			return 0;
 
		int lh = _maxHeight(root->_left);
		int rh = _maxHeight(root->_right);
 
		return lh > rh ? lh + 1 : rh + 1;
	}
 
	int _minHeight(Node* root)
	{
		if (root == nullptr)
			return 0;
 
		int lh = _minHeight(root->_left);
		int rh = _minHeight(root->_right);
 
		return lh < rh ? lh + 1 : rh + 1;
	}
 
 
	void _InOrder(Node* root)
	{
		if (root == nullptr)
			return;
 
		_InOrder(root->_left);
		cout << root->_kv.first << " ";
		_InOrder(root->_right);
	}
 
	bool _IsValidRBTree(Node* pRoot, size_t k, const size_t blackCount)
	{
		//走到null之后，判断k和black是否相等
		if (nullptr == pRoot)
		{
			if (k != blackCount)
			{
				cout << "违反性质四：每条路径中黑色节点的个数必须相同" << endl;
				return false;
			}
			return true;
		}
 
		// 统计黑色节点的个数
		if (BLACK == pRoot->_col)
			k++;
 
		// 检测当前节点与其双亲是否都为红色
		if (RED == pRoot->_col && pRoot->_parent && pRoot->_parent->_col == RED)
		{
			cout << "违反性质三：存在连在一起的红色节点" << endl;
			return false;
		}
 
		return _IsValidRBTree(pRoot->_left, k, blackCount) &&
			_IsValidRBTree(pRoot->_right, k, blackCount);
	}
 
public:
 
	void InOrder()
	{
		_InOrder(_root);
		cout << endl;
	}
 
	void Height()
	{
		cout << "最长路径:" << _maxHeight(_root) << endl;
		cout << "最短路径:" << _minHeight(_root) << endl;
	}
 
 
	bool IsBalanceTree()    //检查红黑树合法性的主要函数
	{
		// 检查红黑树几条规则
 
		Node* pRoot = _root;
		// 1.只要是空树就是红黑树
		if (nullptr == pRoot)
			return true;
 
		// 2.检测根节点是否满足情况
		if (BLACK != pRoot->_col)
		{
			cout << "违反红黑树性质二：根节点必须为黑色" << endl;
			return false;
		}
 
		// 获取任意一条路径中黑色节点的个数 -- 比较基准值
		size_t blackCount = 0;
		Node* pCur = pRoot;
		while (pCur)
		{
			if (BLACK == pCur->_col)
				blackCount++;
 
			pCur = pCur->_left;
		}
 
		// 检测是否有连续红色节点和各路径黑节点个数是否相同
		size_t k = 0;    //k用来记录路径中黑色节点的个数
		return _IsValidRBTree(pRoot, k, blackCount);
	}
 
private:
	Node* _root = nullptr;
};
 
void TestRBTree1()
{
	//int a[] = { 1, 2, 3, 4, 5, 6, 7, 8 };
	int a[] = { 30, 29, 28, 27, 26, 25, 24, 11, 8, 7, 6, 5, 4, 3, 2, 1 };
	RBTree<int, int> t;
	for (auto e : a)
	{
		t.Insert(make_pair(e, e));
	}
	t.levelOrder();
	t.InOrder();
	t.Height();
}
 
void TestRBTree2()
{
	const size_t N = 1024 * 1024;
	vector<int> v;
	v.reserve(N);
	srand(time(0));
	for (size_t i = 0; i < N; ++i)
	{
		v.push_back(rand());
		//v.push_back(i);
	}
 
	RBTree<int, int> t;
	for (auto e : v)
	{
		t.Insert(make_pair(e, e));
	}
 
	//t.levelOrder();
	//cout << endl;
	cout << "是否平衡?" << t.IsBalanceTree() << endl;
	t.Height();
 
	//t.InOrder();
}

二. 插入红黑树的完整实例

1.实例

（1）黑叔LL型。右单旋，父,爷变色。

对应上面的黑叔LL型 情况，右单旋，父,爷变色。

5是新插入节点—儿子，此时父10是爷20的左L，儿子5是父10的左L，所以是黑叔LL型，父10和爷20右单旋，10的右给20的左边，把20给10的右，10去爷爷的位置。再变色，把父亲10和爷爷20变色。

（2）红叔：叔父爷变色，爷变新结点。

30是新插入节点—儿子，让爷10变红，叔5和父20变黑，爷10变新结点，如果爷10是根节点，就回到上面判断新节点的条件：新结点是根—染为黑色，新结点非根—染为红色。这里爷10是根，则将10染为黑色即可。

（3）黑叔RR型。左单旋，父,爷变色。

对应上面的黑叔RR型 情况，左单旋，父,爷变色。

40是新插入节点—儿子，此时父30是爷20的右R，儿子40是父30的右R，并且叔叔是null黑节点，所以是黑叔RR型，父30和爷20左单旋，30的左给20的右，把20给30的左，30去爷爷的位置。再变色，把父亲30和爷爷20变色，20变红，30变黑。因为这个局部子树的根节点30是黑色，所以跟上面的数颜色也没关系，所以不用继续向上调整。