1. Toy模板网首页
  2. > Toy博客

【C++】红黑树的模拟实现

7月前 作者：椿融雪 分类：Toy博客 阅读(31) 违法举报

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

一、红黑树的概念

红黑树，是一种二叉搜索树，但在每个结点上增加一个存储位表示结点的颜色，可以是Red或Black。 通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路径会比其他路径长出俩倍，因而是接近平衡的

【C++】红黑树的模拟实现

红黑树要求整棵树的最长路径是最短路径的两倍，所以红黑树是近似平衡的，即子树中某一路径可能比另一条路径长大于2倍，但是AVL树是通过高度来控制平衡的，且AVL能达到的平衡是二叉树中能达到的最好的平衡了，所以AVL树是绝对平衡的

二、红黑树的性质

红黑树有如下性质：

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

2.根节点是黑色的

3.如果一个节点是红色的，则它的两个孩子结点是黑色的

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

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

【C++】红黑树的模拟实现

我们需要注意的是，第5点中的叶子节点并不是我们平常所说的叶子节点，这里的叶子节点是指空节点，图中的NIL节点，它之所以要加这个节点的未来更好的标识每条路径，但是我们可以不需要太在意在这一点，这一点的目的只是为了让我们更好的理解每一条路径，即使没有这一点，那么树中的所有路径的黑色节点的数量都会减一，并不会违反规则4，所有我们只需要了解即可

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

这里我们可以在极端的场景下来思考这个问题，当一条路径上的全部节点都是黑色节点的时候，此时该路径为最短路径，当一条路径中黑色节点与红色节点交替时该路径为最长路径，此时最长路径刚好为最大路径的两倍

【C++】红黑树的模拟实现

三、红黑树节点的定义

红黑树的节点的结构和AVL树节点整体上差不多，三个指针分别指向父节点，左孩子，右孩子，其次包含一个pair键值对，和AVL树节点不同的是，红黑树不再需要_bf变量来作为树的平衡因子，而是需要一个_col变量来标识每一个节点的颜色

/定义颜色
enum Color
{
	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;
	Color _col;  //节点颜色
	
    //构造
	RBTreeNode(const pair<K, V>& kv)
		:_kv(kv)
		, _left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
		, _col(RED)  //默认使用红色
	{}
};

思考：在节点的定义中，为什么要将节点的默认颜色给成红色的?

1.如果新增节点的颜色为红色，那么这里存在三种情况，一是新增节点为根节点，由于规则2，所以此时我们需要将节点的颜色改为黑色，二是新增节点的父节点的颜色是红色，由于规则3，红黑树不能出现连续的红色节点，此时就需要进行调整，三是新增节点的父节点的颜色是黑色，此时我们不需要进行任何的处理，因为此时位于违反红黑树的规则

2.如果新增节点的颜色是黑色，那么我们每插入一个节点，都会导致这条路径 黑色节点的数量比其他所以路径的黑色节点的数据多1，违反了红黑树的规则4，所以每次插入都需要进行处理

3.综上所述，当新增节点的颜色为红色的时候，有时需要处理，有时并不需要处理，而当新增节点的颜色为黑色的时候，每次插入一个节点都需要进行处理，而且处理比较的麻烦，所以我们将新增节点的颜色默认设置为红色

四、红黑树结构

为了后续实现关联式容器简单，红黑树的实现中增加一个头结点，因为跟节点必须为黑色，为了与根节点进行区分，将头结点给成黑色，并且让头结点的 pParent 域指向红黑树的根节点，pLeft域指向红黑树中最小的节点，_pRight域指向红黑树中最大的节点，如下：

【C++】红黑树的模拟实现

我们下面在实现红黑树的时候不会向STL库中一样使用上面的规则，因为学习STL并不是为了造一个更好的轮子，而是学习其底层结构，增加对其结构的认识以及学习大佬的优秀的代码

五、红黑树的插入操作

红黑树的插入前面部分和二叉树搜索树一样，这里唯一需要注意的是当插入的节点为根节点的时候，此时我们需要将根节点的颜色修改为黑色，因为新增节点的颜色默认是红色，而红黑树的规则2要求根节点的颜色为黑色

bool Insert(const pair<K, V>& kv)
{
    //判断根节点是否为空
	if (_root == nullptr)
	{
		_root = new Node(kv);
        //将根节点的颜色改为黑色
		_root->_col = BLACK;
		return true;
	}
	else
	{
        //寻找插入位置
		Node* cur = _root;
		Node* parent = nullptr;

		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;  //已经存在，则返回false
			}
		}
		
        //初始化列表中已经将节点的颜色设置为红色，这里我们不需要显式写
		cur = new Node(kv);
		//cur->_col = RED;

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

检测新节点插入后，红黑树的性质是否造到破坏，因为新节点的默认颜色是红色，因此：如果其双亲节点的颜色是黑色，没有违反红黑树任何性质，则不需要调整；但当新插入节点的双亲节点颜色为红色时，就违反了性质三不能有连在一起的红色节点，此时需要对红黑树分情况来讨论：约定:cur为当前节点，p为父节点，g为祖父节点，u为叔叔节点

1.叔叔节点存在且为红，此时我们需要进行变色处理

2.叔叔不存在或是叔叔存在且颜色为黑色，此时我们需要进行旋转+变色

下面我们针对上面的两种情况进行讨论

六、红黑树的调整

1.叔叔存在且为红

cur为红，p为红，g为黑，u存在且为红,此时我们需要将p和u变黑，再将g变红即可(约定:cur为当前节点，p为父节点，g为祖父节点，u为叔叔节点)

【C++】红黑树的模拟实现

我们可以看到，当p为红，由于g是p的父节点，所以g一定是黑色，否则在插入节点之前就违反了规则3，此时如果叔叔节点存在且为红，那么我们只需要将p和u变黑，再将g变红即可，这样做不会改变g这棵子树黑色节点是数量，所以不会影响到其他的路径，同时g的子树的每条路径的黑色节点的数量也是相同的，符合红黑树的性质

节点颜色修改之后，这里又分为两种情况：

1.g如果是根节点，由于根节点必须是黑色的，所以此时我们需要将g 的颜色置为黑色

2.如果g不是根节点，由于我们将g变成了红色，而我们并不知道g的父节点是不是红色的，所以我们需要将g作为新增节点，继续向上调整，直到不需要进行调整或者调整到根

【C++】红黑树的模拟实现

此外，我们需要注意的是，和AVL树中的旋转图一样，这里给出的是抽象图，其中a/b/c/d代表的是高度为h的红黑子树，h可以取任意大于等于0的整数，所以上面的图只是代表一类情况，我们下面给出两种具体的情况：

h==0

【C++】红黑树的模拟实现

h==1

【C++】红黑树的模拟实现

尽管有无数多种情况，只要叔叔存在且为红，那么无论是插入节点在父节点的左边还是右边，插入节点的父亲在祖父节点的左边还是右边都没有关系，可以采取统一的处理方式，即统一将父节点和叔叔节点变黑，将祖父节点变红

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

2.叔叔不存在或者存在且为黑

上面将叔叔存在于叔叔不存在且为红分为一种情况是因为这两种情况我们可以使用同一种方式进行处理，(约定：cur为当前节点，p为父节点，g为祖父节点，u为叔叔节点):

叔叔不存在或者存在且为黑，有以下两种情况：

1.当u不存在时，cur一定是新插入节点，因为如果cur不是新插入节点，则cur和p中一定有一个节点的颜色是黑色，否则就不满足规则4–每条路径上黑色节点的个数相同，此时我们的操作是旋转+变色，其中旋转会根据父节点位置和插入节点位置的不同分为四种情况，而变色是统一将旋转后子树的根节点变为黑色，将根节点的左右节点变为红色

【C++】红黑树的模拟实现

2.如果u存在且为黑，那么cur节点原来的颜色一定是黑色，现在看到其是红色是因为cur的子树之前为情况1，然后情况1调整后将祖父节点也就是cur节点变成了红色，否则g左子树的黑色节点的个数会比右子树的黑色节点个数少1，违反规则4，此时我们的操作和u不存在时一模一样–旋转+变色，旋转分为四种情况，变色统一将旋转后子树的根节点变为黑色，将根的左右节点变为红色，所以我们可以将u不存在和u存在且为黑分为同一类(本质上我们不会改变u及其子树的颜色)

【C++】红黑树的模拟实现

【C++】红黑树的模拟实现

红黑树的旋转和AVL树一样，红黑树会根据父节点位置的不同和插入位置的不同选择不同的旋转方式来进行调整，旋转一共分为四类：

1.右单旋–父节点在祖父节点的左侧，cur节点在父节点的左侧

2.左单旋–父节点在祖父节点的右侧，cur节点在父节点的右侧

3.先左旋再右旋–父节点在祖父节点的左侧，cur节点在父节点的右侧

4.先右旋再左旋–父节点在祖父节点的右侧，cur节点在父节点的左侧

我们可以看到，红黑树的旋转其实就是AVL树中的四种旋转，只不过红黑树中不需要更新平衡因子，而是需要更新节点的颜色。

红黑树中叔叔不存在或者存在且为黑的情况下，我们需要进行旋转，具体是哪一种旋转，需要根据cur节点，父节点和祖父节点的位置进行判断，然后将旋转后子树的根节点变为黑色，子树的左右子树变为红色即可。这样调整之后，我们已经将该子树的根节点的颜色变为了黑色，所以我们就不再需要考虑该子树的根节点变为红色而违反规则4的问题，所以这样调整之后我们不再需要继续向上进行调整。

下面我们给出需要双旋的情况：

【C++】红黑树的模拟实现

3.插入完整代码

bool Insert(const pair<K, V>& kv)
{
	// 判断根节点是否为空
	if (_root == nullptr)
	{
		_root = new Node(kv);
		_root->_col = BLACK;  //根节点的颜色置为黑色
		return true;
	}
	else
	{
		// 寻找插入位置
		Node* cur = _root;
		Node* parent = nullptr;

		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;  //重复节点返回false
			}
		}

		cur = new Node(kv);
		cur->_col = RED;

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


		while (parent && parent->_col == RED)
		{
			Node* grandfather = parent->_parent;

			//父节点在祖父节点的左边
			if (parent == grandfather->_left)
			{
				Node* uncle = grandfather->_right;

				// 情况一  uncle存在且为红
				if (uncle && uncle->_col == RED)
				{
					parent->_col = uncle->_col = BLACK;
					grandfather->_col = RED;

					cur = grandfather;
					parent = cur->_parent;
				}
				else  // 情况二 叔叔不存在或者存在且为黑
				{
					// cur在父节点的左边
					if (cur == parent->_left)
					{
						RotateR(grandfather);

						//更新节点颜色
						parent->_col = BLACK;
						grandfather->_col = RED;
					}
					// 情况三  左右双旋
					else
					{
						//以parent为轴进行左旋
						RotateL(parent);
						// 再以grandfather为轴进行右旋
						RotateR(grandfather);

						// 更新节点颜色
						cur->_col = BLACK;
						grandfather->_col = RED;
					}

					//走到这里跳出循环，因为此时不会印象上层节点
					break;
				}
			}
			//如果父节点在祖父节点的右边
			else
			{
				Node* uncle = grandfather->_left;
				// 情况一  叔叔存在且为红
				if (uncle && uncle->_col == RED)
				{
					uncle->_col = parent->_col = BLACK;
					grandfather->_col = RED;

					cur = grandfather;
					parent = cur->_parent;
				}
				else
				{
					// g
					//     p
					// c
					if (cur == parent->_left)
					{
						RotateR(parent);
						RotateL(grandfather);

						parent->_col = BLACK;
						grandfather->_col = RED;
					}
					// g
					//    p
					//      c
					else
					{
						RotateL(grandfather);

						parent->_col = BLACK;
						grandfather->_col = RED;
					}

					break;
				}
			}
		}

		_root->_col = BLACK;

		//最后将根节点的颜色置为黑色
		return true;
	}
}

4.总结

红黑树的调整一根可以分为一下三种情况：(约定:cur为当前节点，p为父节点，g为祖父节点，u为叔叔节点)

情况一: cur为红，p为红，g为黑，u存在且为红

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

【C++】红黑树的模拟实现

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

【C++】红黑树的模拟实现

解决方式：

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

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

p、g变色–p变黑，g变红

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

【C++】红黑树的模拟实现

解决方式：

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

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

则转换成了情况2

我们可以将其分为两种情况:

1.父节点的颜色为黑色，此时没有违反红黑树的规则，不需要进行调整

2.父节点的颜色为红色，此时出现了连续的红色节点，需要进行调整，调整又分为两种情况：

​ 1.如果叔叔节点存在且为红，则将父节点和叔叔节点的颜色置为黑色，祖父节点的颜色置为红色，然后继续向上进行调整

​ 2.叔叔不存在或者叔叔存在且为黑，此时我们需要进行旋转+变色–旋转根据父节点和cur节点位置的不同分为左单旋，右单旋，左右双旋和右左双旋，变色统一将旋转后的子树的很接地的颜色置为黑色，根节点的左右节点的颜色置为红色，调整完成之后不需要再进行往上进行调整

七、红黑树的验证

红黑树的检测分为两步：

1.检测其是否满足二叉搜索树(中序遍历是否为有序序列)

2.检测其是否满足红黑树的性质

对于需要验证的第一点，我们只需要检查插入数据之后。进行中序遍历是否有序即可

对于需要验证的第二点，我们需要一次验证是否满足红黑树的规则–根节点的颜色为黑色，不允许出现连续的红色节点，每条路径上的黑色节点的数量相等，此外，我们不能仅仅使用几个数据进行检测，而是应该使用大量的随机数进行检测，这样才能更好的检测我们写的红黑树是否正确。

测试代码如下：

void InOrder()
{
	_InOrder(_root);
}

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

	_InOrder(root->_left);
	cout << root->_kv.first << ":" << root->_kv.second << endl;
	_InOrder(root->_right);
}

bool check(Node* root, int blackNum, int ref)
{
	if (root == nullptr)
	{
		if (blackNum != ref)
		{
			cout << "违反规则:本条路径的黑色节点的数量跟最左路径不相等" << endl;
			return false;
		}

		return true;
	}

	if (root->_col == RED && root->_parent->_col == RED)
	{
		cout << "违反规则：出现连续红色节点" << endl;
		return false;
	}

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

	return check(root->_left, blackNum, ref)
		&& check(root->_right, blackNum, ref);
}


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

	if (_root->_col != BLACK)
		return false;

	int ref = 0;// 统计黑节点的个数
	Node* left = _root;
	while (left)
	{

		if (left->_col == BLACK)
			ref++;

		left = left->_left;
	}

	return check(_root, 0, ref);
}

//使用少量数据检测是否满足二叉搜索树的性质
void TestRBTree1()
{
	//int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };
	//int a[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };
	int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };
	RBTree<int, int> t;

	for (auto e : a)
	{
		t.Insert(make_pair(e, e));
	}

	t.InOrder();
	cout << t.IsBalance() << endl;
}

//使用大量随机数进行检测
void TestRBTree2()
{
	srand(time(0));
	const size_t N = 10000;
	RBTree<int, int> t;
	for (size_t i = 0; i < N; ++i)
	{
		size_t x = rand();
		t.Insert(make_pair(x, x));
	}

	cout << t.IsBalance() << endl;
}

八、红黑树的删除

红黑树和AVL树一样，它的删除作为我们了解的内容即可，有兴趣的同学可参考：《算法导论》或者《STL源码剖析》，也可以看看下面博客:红黑树- _Never_ -博客园

九、红黑树与AVL树的比较

红黑树和AVL树都是高效的平衡二叉树，增删改查的时间复杂度都是O(logN)，红黑树不追求绝对平衡，其只需保证最长路径不超过最短路径的2倍，所以在某些极端的场景下红黑树的查找效率相较于AVL树要低一些，但是10个数AVL树最多查找30，红黑树最多查找60，由于CPU速度跟快，所以这多查找的30次几乎可以忽略不计，相对而言，降低了插入和旋转的次数，所以在经常进行增删的结构中性能比AVL树更优，而且红黑树实现比较简单，所以实际运用中红黑树更多

十、红黑树的应用

红黑树应用于 C++ STL库-- map/set、mutil_map/mutil_set，Java 库，inux内核还有，其他一些库文章来源地址https://www.toymoban.com/news/detail-480402.html

十一、红黑树的代码实现

1.RBTree.h

#pragma once

//定义颜色
enum Color
{
	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;
	Color _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;
		}
		else
		{
			Node* cur = _root;
			Node* parent = nullptr;

			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;
				cur->_parent = parent;
			}
			else
			{
				parent->_left = cur;
				cur->_parent = parent;
			}


			while (parent && parent->_col == RED)
			{
				Node* grandfather = parent->_parent;
				if (parent == grandfather->_left)
				{
					Node* uncle = grandfather->_right;

					// 情况一  uncle存在且为红
					if (uncle && uncle->_col == RED)
					{
						parent->_col = uncle->_col = BLACK;
						grandfather->_col = RED;

						cur = grandfather;
						parent = cur->_parent;
					}
					else
					{
						// 情况二
						if (cur == parent->_left)
						{
							RotateR(grandfather);

							parent->_col = BLACK;
							grandfather->_col = RED;
						}
						// 情况三
						else
						{
							RotateL(parent);
							RotateR(grandfather);

							cur->_col = BLACK;
							grandfather->_col = RED;
						}

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

						cur = grandfather;
						parent = cur->_parent;
					}
					else
					{
						// g
						//     p
						// c
						if (cur == parent->_left)
						{
							RotateR(parent);
							RotateL(grandfather);

							cur->_col = BLACK;
							grandfather->_col = RED;
						}
						// g
						//    p
						//      c
						else
						{
							RotateL(grandfather);

							parent->_col = BLACK;
							grandfather->_col = RED;
						}

						break;
					}
				}
			}

			_root->_col = BLACK;

			return true;
		}
	}
	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 (ppNode == nullptr)
		{
			_root = SubR;
			SubR->_parent = nullptr;
		}
		else
		{
			if (parent == ppNode->_left)
			{
				ppNode->_left = SubR;
				SubR->_parent = ppNode;
			}
			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 (ppNode == nullptr)
		{
			_root = SubL;
			SubL->_parent = nullptr;
		}
		else
		{
			if (parent == ppNode->_left)
			{
				ppNode->_left = SubL;
			}
			else
			{
				ppNode->_right = SubL;
			}

			SubL->_parent = ppNode;
		}
	}

	void InOrder()
	{
		_InOrder(_root);
	}

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

		_InOrder(root->_left);
		cout << root->_kv.first << ":" << root->_kv.second << endl;
		_InOrder(root->_right);
	}

	bool check(Node* root, int blackNum, int ref)
	{
		if (root == nullptr)
		{
			if (blackNum != ref)
			{
				cout << "违反规则:本条路径的黑色节点的数量跟最左路径不相等" << endl;
				return false;
			}

			return true;
		}

		if (root->_col == RED && root->_parent->_col == RED)
		{
			cout << "违反规则：出现连续红色节点" << endl;
			return false;
		}

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

		return check(root->_left, blackNum, ref)
			&& check(root->_right, blackNum, ref);
	}


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

		if (_root->_col != BLACK)
			return false;

		int ref = 0;// 统计黑节点的个数
		Node* left = _root;
		while (left)
		{

			if (left->_col == BLACK)
				ref++;

			left = left->_left;
		}

		return check(_root, 0, ref);
	}
private:
	Node* _root = nullptr;
};

2.RBTree.cpp

#define _CRT_SECURE_NO_WARNINGS 1

#include <iostream>
using namespace std;

#include "RBTree.h"

void TestRBTree1()
{
	//int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };
	int a[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };
	//int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };
	RBTree<int, int> t;

	for (auto e : a)
	{
		t.Insert(make_pair(e, e));
	}

	t.InOrder();
	cout << t.IsBalance() << endl;
}

void TestRBTree2()
{
	srand(time(0));
	const size_t N = 10000;
	RBTree<int, int> t;
	for (size_t i = 0; i < N; ++i)
	{
		size_t x = rand();
		t.Insert(make_pair(x, x));
	}

	cout << t.IsBalance() << endl;
}

int main()
{
	TestRBTree1();
	//TestRBTree2();
	return 0;
}

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

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处： 如若内容造成侵权/违法违规/事实不符，请点击违法举报进行投诉反馈，一经查实，立即删除！

分享到：
领支付宝红包 赞助服务器费用

相关文章

  • 【C++】红黑树的原理与实现

    【C++】红黑树的原理与实现

      文章目录 一、引言 二、红黑树的概念与性质 2、1 红黑树的概念 2、2 红黑树的性质 三、红黑树的定义与实现 3、1 红黑树的定义 3、2 插入新节点 3、2、1 默认插入红色节点 3、3 插入情况分类 3、3、1 情况一（根据颜色向上调整） 3、3、2 情况二（单次旋转+变色） 3、3、3 情

    2024年02月13日
    浏览(34)
  • 【C++进阶06】红黑树图文详解及C++模拟实现红黑树

    【C++进阶06】红黑树图文详解及C++模拟实现红黑树

    1.1 红黑树的概念 AVL树用平衡因子让树达到高度平衡 红黑树可以认为是AVL树的改良 通过给每个节点标记颜色让树接近平衡 以减少树在插入节点的旋转 在每个结点新增一个存储位表示结点颜色 可以是Red或Black 通过对任何一条从根到叶子的路径上 各个结点着色方式的限制 红黑

    2024年01月21日
    浏览(36)
  • 数据结构之进阶二叉树（二叉搜索树和AVL树、红黑树的实现）超详细解析，附实操图和搜索二叉树的实现过程图

    数据结构之进阶二叉树（二叉搜索树和AVL树、红黑树的实现）超详细解析，附实操图和搜索二叉树的实现过程图

    绪论​ “生命有如铁砧，愈被敲打，愈能发出火花。——伽利略”；本章主要是数据结构 二叉树的进阶知识，若之前没学过二叉树建议看看这篇文章一篇掌握二叉树，本章的知识从浅到深的 对搜索二叉树的使用进行了介绍和对其底层逻辑的实现进行了讲解 ，希望能对你有所

    2024年02月04日
    浏览(36)
  • 【C++】详解红黑树并模拟实现

    【C++】详解红黑树并模拟实现

    前言：        上篇文章我们一起学习了AVL树比模拟实现，我们发现AVL树成功地把时间复杂度降低到了O(logN)。但是同时我们不难发现一个问题，在构建AVL树中我们也付出了不小的代价，频繁的旋转操作导致效率变低。为了解决这个问题，我们本章将迎来更为实用的红黑树，他

    2024年02月09日
    浏览(31)
  • 【数据结构】红黑树的删除（抽丝剥茧，带你理清每一种情况）

    【数据结构】红黑树的删除（抽丝剥茧，带你理清每一种情况）

     红黑树的删除，较AVL树的删除比较抽象，同时也跟红黑树的插入的区别较大，但大体上的思路还是基于普通二叉搜索树的基础上进行讨论的。 浅浅的铺垫一下: 需要清楚普通二叉树的删除，可见AVL树的删除文章开头。 四种旋转的操作（只需操作）得熟记于心，可见AVL树的插

    2024年04月27日
    浏览(23)
  • 【C++】红黑树模拟实现插入功能（包含旋转和变色）

    【C++】红黑树模拟实现插入功能（包含旋转和变色）

    本篇主要讲解红黑树的模拟实现，实现之后再封装成map和set。 红黑树中所用到的旋转功能均源自我的上一篇博客，本篇中不会再详谈旋转，若对于旋转不了解的同学可以先看看上一篇博客：【C++】AVL树模拟实现插入功能 前一篇的AVL树，是严格平衡的一棵二叉搜索树，也就是

    2024年02月13日
    浏览(40)
  • 【高阶数据结构】红黑树 {概念及性质；红黑树的结构；红黑树的实现；红黑树插入操作详细解释；红黑树的验证}

    【高阶数据结构】红黑树 {概念及性质；红黑树的结构；红黑树的实现；红黑树插入操作详细解释；红黑树的验证}

    红黑树（Red Black Tree） 是一种自平衡二叉查找树，在每个结点上增加一个存储位表示结点的颜色，可以是Red或Black。 通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路径会比其他路径长出俩倍，因而是接近平衡的。 AVL树 VS 红黑树 红黑树是

    2024年02月09日
    浏览(39)
  • 【C++】 使用红黑树模拟实现STL中的map与set

    【C++】 使用红黑树模拟实现STL中的map与set

    前面的文章我们学习了红黑树，也提到了C++STL中的map和set的底层其实就是用的红黑树来实现的（而map和set的使用我们前面也学过了）。 既然红黑树我们也学习过了，那这篇文章我们就用红黑树来简单实现一下STL中的map和set，重点是学习它的框架。 上一篇文章我们实现了红黑

    2024年02月12日
    浏览(21)
  • 二叉树、二叉查找树、平衡树和红黑树概念及其性质

    二叉树、二叉查找树、平衡树和红黑树概念及其性质

      在所有的树结构，基本上都遵循左小右大的原则。本文分享二叉树、二叉查找树、平衡树和红黑树概念及其性质。   二叉树（Binary Tree）是指每个节点最多只有两个分支的树结构（即不存在分支大于 2 的节点），如下图所示：   这是一棵拥有 6 个节点深度为 2（深度

    2024年02月08日
    浏览(29)
  • 数据结构——常见二叉树的分类（完全二叉树、满二叉树、平衡二叉树、二叉搜索树、红黑树）

    数据结构——常见二叉树的分类（完全二叉树、满二叉树、平衡二叉树、二叉搜索树、红黑树）

    专业术语 中文 描述 Root 根节点 一棵树的顶点 Child 孩子结点 一个结点含有的子树的根节点称为该结点的子节点 Leaf 叶子结点 没有孩子的节点 Degree 度 一个节点包含子树的数量 Edge 边 一个节点与另外一个节点的连接 Depth 深度 根节点到这个节点经过边的数量 Height 节点高度 从

    2024年02月03日
    浏览(35)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

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

二维码1

领取红包

二维码2

领红包