C++【实现红黑树(核心插入)】-Toy模板网

这篇具有很好参考价值的文章主要介绍了C++【实现红黑树(核心插入)】。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

一、红黑树概念介绍

概念：
红黑树，也是一种二叉搜索树，它是在每个结点上增加一个存储位表示结点的颜色，可以是红或黑，然后通过对任何一条从根到叶子的路径上各个结点着色方式的限制，保证了没有一条路径会能超过其他路径的俩倍，因而是近似平衡的。map和set的底层数据结构就是用红黑树来封装的。
性质：
1.根节点是黑色的
2.不能出现连续的红色节点
3. 每条路径上有相同数量的黑色节点
4. 每个叶子(空节点)结点都是黑色
5. 每个结点不是红色就是黑色
满足上面的性质，红黑树就能保证：最长路径中节点个数不会超过最短路径节点个数的2倍。
优势：
假设全部的黑色节点有N个最短路径长度是logN 整棵树的节点数量：[N,2N]，最长路径长度：2logN。假设10亿个节点，AVL：最多查找30次左右；RB：最多查找60次左右。
综合而言，其实对于查找大量数据30次和60次没太大差别，而红黑树不要求绝对平衡，只需保证最长路径不超过最短路径的2倍，相对来说降低了插入和旋转的次数，所以在经常进行增删的结构中性能比AVL树更优。

二、红黑树模拟实现

（1）红黑树节点

enum Color
{
	RED=0,
	BLACK,
};
template<class K,class V>
struct RbTreeNode
{
	RbTreeNode<K, V>* _left;
	RbTreeNode<K, V>* _right;
	RbTreeNode<K, V>* _parent;
	pair<K, V>_kv;
	Color _col;
	RbTreeNode(const pair<K, V>& kv)
		:_left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
		, _kv(kv)
		, _col(RED)
	{}
};

里面同样用三叉链，要有左孩子右孩子，父节点，以及pair类的类型来存储kv两个相同或不同类型的值(当我们使用make_pair函数创建一个pair对象，该函数会自动推断参数类型)，并在里面增加一个枚举，用来表示一个节点不是红色就是黑色。关于构造函数里面的颜色初始化为黑色还是红色，在插入会讲解。

（2）红黑树插入分析(核心)

插入和前面的AVL插入部分是一样的，在里面如果是根节点，那就把跟点为置为黑色。
那这有一个问题就是节点构造函数里面的一个问题：我们在申请一个新节点时，宁愿新增红色还是黑色？
因为不管是增哪种颜色，本质上是违反规则三还是违反规则四的问题，如果插入黑色，一定违反规则四，但它代价太大，违反规则三就不一定，因为它的父节点可能为红色也可能为黑色，如果在黑色节点下面插入就没影响，反之就会影响。
对于上面的做法会出现下面的两大情况，第一GPC为一一条直线，第二GPC为折线。
如图：
C++【实现红黑树(核心插入)】
G为祖父节点，P为父亲节点，C为当前节点，U为叔父节点
1、先解决当GPC为一条直线的时候：
（1）如果U存在且为红色，P必须变黑，U也得变黑，左右都增加了黑，那就把G变红,这样久能保持黑色节点不变，因为G现在变成红了，但是G的父节点如果是红色的还得继续处理，那就把G当成C节点，继续算它的祖父，再看U，如果U是红再把它变成黑。
C++【实现红黑树(核心插入)】
它的所对应的抽象图以及具象图：

（2）如果U不存在或者存在且为黑又是两种情况
如果U不存在，再增加红节点，且有连续的红色节点，有可能会超过它的最短路径，只能旋转来降高度。把P变黑，把G给P的左，再把P作为左，同时把原来的G变红，这里就是左单旋加G和P变色。
如下例图：
C++【实现红黑树(核心插入)】
它所对应的抽象及具象图：

如果U存在且为黑色
U存在且为黑是由第一种请况变化而来，这里发生了右单旋，P的左孩子作为G的左孩子，而G又作为P的右孩子，且P变为黑，G变为红。
C++【实现红黑树(核心插入)】
对于上面的U不存在或者存在为黑两种情况进行总结： P为G的左孩子时，C为P的左孩子进行右单旋转，如果P为G的右孩子，C为P的右孩子，进行左单旋转。P变为黑色，G变为红色。
旋转的目的就是为了防止最长路径超过最短路径的2倍。GPC为一条线的时候就是左单旋转或右单旋。

2、再解决GPC为折线的情况
（1）U存在且为黑
出现这种折线情况的原因是由第一种情况先变色而产生，然后p变成g的左，c变成p的右，c为红，p为红，g为黑，接着我们先以p为轴进行左旋转进行降低高度，在以g为轴进行右旋，且g变红，c变黑，因为这样才能保证不出现连续红结点且保证每个路径黑色数量一样。以上实际进行了双旋。
C++【实现红黑树(核心插入)】

（2）U不存在，直接右单旋

（3）插入代码思路(如何快速写插入算法)

C++【实现红黑树(核心插入)】

（一）先看左面这种大情况
插入C1肯定为红节点，P1如果是红，就需要开始作处理：先利用三叉链，从P1得出G1，进入核心环节：左面的这种情况是P1是G1的左孩子时，里面又要有分两种情况：
（1）如果是U存在且为红，我们把P1和U变为黑，G1变为红，更新C1到G1的位置，继续往上调整；
（2）如果是U不存在或黑(是一种情况)，如果U不存在就不能变黑，而且就算存在为黑说明是一定是由继续往上调整的那一步(情况(1))而来的即继续往上处理，我们还是是增加了节点，就可能导致最长路径超过最短路径的2倍或者一直用情况(1)的方式最终导致每条路径黑色数量不相等。这时候我们就要通过旋转方式降低高度加变色来解决。所以在这里又分两种：G1P1C1为直线和G1P1C1为折线：

如果是C1P1在一条直线上即C1是P1的左孩子，我们以G1为轴进行右单旋(哪边高往哪边降)，G1要变红，P1要变成黑，因为G1下来了P1作为根，不能出现连续的红节点P要变黑，又因为保证黑色数量相等，G1要变红。
如果是C1和P1，G1是折线的时候即C1是P1的右孩子，这时候需要先以P1为轴进行左单旋，再以G1为轴进行右单旋，最终C1做了根节点，G1是右孩子，因为P1是红，C1是红不能出现连续红节点，需把C1变黑，但是还要保证黑色数量相等，就把G1变红。最后结束break，只有情况(1)才会继续向上来回处理。
（二）再看右面这种大情况
和（一）情况类似
P2是G2的右孩子，同理那旋转方式就根上面相反。
所以我们的插入函数：

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->_right;
			}
			else if (cur->_kv.first > kv.first)
			{
				parent = cur;
				cur = cur->_left;
			}
			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* grandf = parent->_parent;
			if (grandf->_left == parent)
			{
				Node* unc = grandf->_right;
				if (unc && unc->_col == RED)//u存在且为红，变色处理
				{
					parent->_col = BLACK;
					unc->_col = BLACK;
					grandf->_col = RED;

					cur = grandf;//继续往上调整
					parent = cur->_parent;
				}
				else//u不存在或者黑
				{
					if (parent->_left == cur)
					{
						RotateR(grandf);
						parent->_col = BLACK;
						grandf->_col = RED;
						
					}
					else
					{
						RotateL(parent);
						RotateR(grandf);
						cur->_col = BLACK;
						grandf->_col = RED;
					}
					break;
				}
			}
			else
			{
				Node* unc = grandf->_left;
				if (unc && unc->_col == RED)
				{
					parent->_col = BLACK;
					unc->_col = BLACK;
					grandf->_col = RED;

					cur = grandf;
					parent = cur->_parent;
				
				}
				else
				{
					if (parent->_right == cur)
					{
						RotateL(grandf);
						parent->_col = BLACK;
						grandf->_col = RED;
					}
					else
					{
						RotateR(parent);
						RotateL(grandf);
						cur->_col = BLACK;
						grandf->_col = RED;

					}
					break;
				}
			}
		}
		_root->_col = BLACK;
		return true;
	}

（4）判断平衡函数

bool IsBalance()
	{
		if (_root && _root->_col == RED)
		{
			cout << "根节点颜色错误" << endl;
			return false;
		}
		int Bsign = 0;
		Node* cur = _root;
		while (cur)
		{
			if (cur->_col == BLACK)
			{
				++Bsign;
			}
			cur = cur->_left;
		}
		return _check(_root, 0, Bsign);

	}
	bool _check(Node* root, int Bnum, int Bsign)
	{
		if (root == nullptr)
		{
		
			if (Bnum != Bsign)
			{
				cout << "黑色节点数量不相等" << endl;
				return false;
			}
			return true;
		}
		if (root->_col == BLACK)
		{
			++Bnum;
		}
		if (root->_col == RED && root->_parent && root->_parent->_col == RED)
		{
			cout << "连续红色节点" << endl;
			return false;
		}
		return _check(root->_left,Bnum,Bsign) && _check(root->_right, Bnum, Bsign);
	}
	void _Destroy(Node* root)
	{
		if (root == nullptr)
		{
			return;
		}

		_Destroy(root->_left);
		_Destroy(root->_right);
		delete root;
	}

首先不能以最长路径不超过最短路径2倍为准则判断平衡，它只是结果。
还是要以前面说的规则：
第一个：先检查根是不是黑色的；
第二个：再检查连续的红色节点：如果是红色的就去检查儿子，这种方式不行，因为孩子可能不存在，可以改为它的父亲，如果是红一定有父亲，如果父亲为红就存在连续红色节点直接返回假；
还有一个：最重要的规则：判断黑色节点的数量是否相等，我们需要先记录一下黑色数量，我们可以先获取一条路径的黑色数量Bsign，然后以它为标准，如何让每条路径以它标准判断是否相等？我们可以在参数里面的形参传值Bnum，往下递归就会往下传，下一层++不会影响上一层++，因为下一层是上一层的拷贝，只要有一条不相等就返回假。

（5）查找函数

Node* Find(const K& key)
	{
		Node* cur = _root;
		while (cur)
		{
			if (cur->_kv.first < key)
			{
				cur = cur->_right;
			}
			else if (cur->_kv.first > key)
			{
				cur = cur->_left;
			}
			else
			{
				return cur;
			}
		}

		return nullptr;
	}

从根开始走，如果比它大，就往右边走，如果比它小，就往左边走，如果相等说明找到，否则返回空。

（6）测试函数

void Test()
{

	int arr[] = { 33, 22, 6, 1, 3, 5, 66, 7, 16, 14, 16, 3, 7, 11, 9, 36, 18, 14, 15 };
	RbTree<int, int> t;
	for (auto n : arr)
	{
	
		t.Insert(make_pair(n, n));
	}

	t.Inorder();
	cout << endl;
	cout << t.IsBalance() << endl;
	cout << "高度："<<t.height() << endl;

	cout << endl;
	cout << "随机数据测试:" << endl;

	srand(time(0));
	const size_t N = 100000;
	RbTree<int, int> r;
	for (size_t i = 0; i < N; ++i)
	{
		size_t x = rand() + i;
		r.Insert(make_pair(x, x));

	}

	cout << r.IsBalance() << endl;
	cout <<"高度："<< r.height() << endl;
}

（7）测试结果

C++【实现红黑树(核心插入)】文章来源地址https://www.toymoban.com/news/detail-466079.html

三、红黑树源代码

（1）RbTree.h

#pragma once
#include<iostream>
#include<utility>
#include<ctime>
using namespace std;
enum Color
{
	RED=0,
	BLACK,
};
template<class K,class V>
struct RbTreeNode
{
	RbTreeNode<K, V>* _left;
	RbTreeNode<K, V>* _right;
	RbTreeNode<K, V>* _parent;
	pair<K, V>_kv;
	Color _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;
public:
	~RbTree()
	{
		_Destroy(_root);
		_root = 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->_right;
			}
			else if (cur->_kv.first > kv.first)
			{
				parent = cur;
				cur = cur->_left;
			}
			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* grandf = parent->_parent;
			if (grandf->_left == parent)
			{
				Node* unc = grandf->_right;
				if (unc && unc->_col == RED)//u存在且为红，变色处理
				{
					parent->_col = BLACK;
					unc->_col = BLACK;
					grandf->_col = RED;

					cur = grandf;//继续往上调整
					parent = cur->_parent;
				}
				else//u不存在或者黑
				{
					if (parent->_left == cur)
					{
						RotateR(grandf);
						parent->_col = BLACK;
						grandf->_col = RED;
						
					}
					else
					{
						RotateL(parent);
						RotateR(grandf);
						cur->_col = BLACK;
						grandf->_col = RED;
					}
					break;
				}
			}
			else
			{
				Node* unc = grandf->_left;
				if (unc && unc->_col == RED)
				{
					parent->_col = BLACK;
					unc->_col = BLACK;
					grandf->_col = RED;

					cur = grandf;
					parent = cur->_parent;
				
				}
				else
				{
					if (parent->_right == cur)
					{
						RotateL(grandf);
						parent->_col = BLACK;
						grandf->_col = RED;
					}
					else
					{
						RotateR(parent);
						RotateL(grandf);
						cur->_col = BLACK;
						grandf->_col = RED;

					}
					break;
				}
			}
		}
		_root->_col = BLACK;
		return true;
	}
	Node* Find(const K& key)
	{
		Node* cur = _root;
		while (cur)
		{
			if (cur->_kv.first < key)
			{
				cur = cur->_right;
			}
			else if (cur->_kv.first > key)
			{
				cur = cur->_left;
			}
			else
			{
				return cur;
			}
		}

		return nullptr;
	}
	void Inorder()
	{
		_InOrder(_root);

	}
	int height()
	{
		return _Height(_root);
	}
	bool IsBalance()
	{
		if (_root && _root->_col == RED)
		{
			cout << "根节点颜色错误" << endl;
			return false;
		}
		int Bsign = 0;
		Node* cur = _root;
		while (cur)
		{
			if (cur->_col == BLACK)
			{
				++Bsign;
			}
			cur = cur->_left;
		}
		return _check(_root, 0, Bsign);

	}
private:
	void RotateL(Node* parent)//左单旋
	{
		Node* suR = parent->_right;//11的右孩子即22
		Node* suRL = suR->_left;//11的右孩子的左孩子即b
		Node* ppnode = parent->_parent;//维护父结点的父结点


		parent->_right = suRL;//11右孩子链接b
		if (suRL)//如果b不为空
			suRL->_parent = parent;//更新双亲结点


		suR->_left = parent;//22上提，左孩子链接11
		parent->_parent = suR;//更新双亲结点

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

	}
	void RotateR(Node* parent)//右单旋
	{
		Node* suL = parent->_left;
		Node* suLR = suL->_right;

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

		Node* ppnode = parent->_parent;

		suL->_right = parent;
		parent->_parent = suL;


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

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

		_InOrder(root->_left);
		cout << root->_kv.first << " ";
		_InOrder(root->_right);
	}
	int _Height(Node* root)
	{
		if (root == NULL)
			return 0;

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

		return leftH > rightH ? leftH + 1 : rightH + 1;
	}
	bool _check(Node* root, int Bnum, int Bsign)
	{
		if (root == nullptr)
		{
		
			if (Bnum != Bsign)
			{
				cout << "黑色节点数量不相等" << endl;
				return false;
			}
			return true;
		}
		if (root->_col == BLACK)
		{
			++Bnum;
		}
		if (root->_col == RED && root->_parent && root->_parent->_col == RED)
		{
			cout << "连续红色节点" << endl;
			return false;
		}
		return _check(root->_left,Bnum,Bsign) && _check(root->_right, Bnum, Bsign);
	}
	void _Destroy(Node* root)
	{
		if (root == nullptr)
		{
			return;
		}

		_Destroy(root->_left);
		_Destroy(root->_right);
		delete root;
	}
	

private:
	Node* _root;
};

void Test()
{

	int arr[] = { 33, 22, 6, 1, 3, 5, 66, 7, 16, 14, 16, 3, 7, 11, 9, 36, 18, 14, 15 };
	RbTree<int, int> t;
	for (auto n : arr)
	{
	
		t.Insert(make_pair(n, n));
	}

	t.Inorder();
	cout << endl;
	cout << t.IsBalance() << endl;
	cout << "高度："<<t.height() << endl;

	cout << endl;
	cout << "随机数据测试:" << endl;

	srand(time(0));
	const size_t N = 100000;
	RbTree<int, int> r;
	for (size_t i = 0; i < N; ++i)
	{
		size_t x = rand() + i;
		r.Insert(make_pair(x, x));

	}

	cout << r.IsBalance() << endl;
	cout <<"高度："<< r.height() << endl;
}

（2）Test.cpp

#include"RbTree.h"
int main()
{
	Test();
	return 0;
}

到了这里，关于C++【实现红黑树(核心插入)】的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！

C++【实现红黑树(核心插入)】

一、红黑树概念介绍

二、红黑树模拟实现

（1）红黑树节点

（2）红黑树插入分析(核心)

（3）插入代码思路(如何快速写插入算法)

（4）判断平衡函数

（5）查找函数

（6）测试函数

（7）测试结果

三、红黑树源代码

（1）RbTree.h

（2）Test.cpp

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信扫一扫打赏

支付宝扫一扫领取红包，优惠每天领

二维码1

二维码2