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

文章目录

  • 一、红黑树的概念
  • 二、红黑树的性质
  • 三、红黑树节点的定义
  • 四、红黑树结构
  • 五、红黑树的插入操作
  • 六、红黑树的调整
    • 1.叔叔存在且为红
    • 2.叔叔不存在或者存在且为黑
    • 3.插入完整代码
    • 4.总结
  • 七、红黑树的验证
  • 八、红黑树的删除
  • 九、红黑树与AVL树的比较
  • 十、红黑树的应用
  • 十一、红黑树的代码实现
    • 1.RBTree.h
    • 2.RBTree.cpp

一、红黑树的概念

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

在这里插入图片描述

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

二、红黑树的性质

红黑树有如下性质：

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

2.根节点是黑色的

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

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

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

在这里插入图片描述

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

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

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

在这里插入图片描述

三、红黑树节点的定义

红黑树的节点的结构和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域指向红黑树中最大的节点，如下：

在这里插入图片描述

我们下面在实现红黑树的时候不会向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为叔叔节点)

在这里插入图片描述

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

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

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

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

在这里插入图片描述

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

h==0

在这里插入图片描述

h==1

在这里插入图片描述

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

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

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

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

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

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

在这里插入图片描述

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

在这里插入图片描述

在这里插入图片描述

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

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

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

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

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

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

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

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

在这里插入图片描述

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，继续向上调整。

在这里插入图片描述

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

在这里插入图片描述

解决方式：

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

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

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

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

在这里插入图片描述

解决方式：

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内核还有，其他一些库

十一、红黑树的代码实现

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

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/28071.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

LVS+Keepalived 高可用群集实战部署

LVS+Keepalived 高可用群集实战部署

LVSKeepalived 高可用群集实战部署 一、LVSKeepalived 高可用群集1.LVS2、Keepalived工作原理和作用3、Keepalived体系主要模块及其作用4、Keepalived实现原理剖析5、VRRP &#xff08;虚拟路由冗余协议&#xff09; LVSKeepalived 高可用群集部署&#xff08;抢占模式&#xf…
阅读更多...
[nlp] OPT与GPT-2的差异

[nlp] OPT与GPT-2的差异

Meta AI 开源1750亿参数大模型- OPT，FlagAI一键调用！ - 知乎简介Meta AI 开源 OPT系列模型，其中最大模型1750 亿参数（需申请访问权限）媲美 GPT-3。OPT系列模型包括了多组不同参数规模的模型权重，如图： OPT开源了一系列大模型，但是实际调用这些模型有很高的技术门槛。为…
阅读更多...
PortSwigger web缓存中毒（Cache Poisoning）

PortSwigger web缓存中毒（Cache Poisoning）

一、什么web缓存中毒&#xff1f; Web缓存中毒&#xff08;Web Cache Poisoning&#xff09;是一种攻击技术&#xff0c;攻击者通过操纵Web应用程序的缓存系统&#xff0c;将恶意或欺骗性内容注入到合法的缓存中&#xff0c;以欺骗用户或绕过安全控制。 Web缓存中毒的原理是利用…
阅读更多...
scala

scala

面向对象 Scala 的面向对象思想和Java 的面向对象思想和概念是一致的。 Scala 中语法和 Java 不同&#xff0c;补充了更多的功能。 6.1类和对象详解 6.1.1组成结构 构造函数: 在创建对象的时候给属性赋值 成员变量: 成员方法(函数) 局部变量 代码块 6.1.2构造器 每个…
阅读更多...
【宝塔建站】Ubuntu下使用宝塔面板一键搭建Z-Blog个人博客

【宝塔建站】Ubuntu下使用宝塔面板一键搭建Z-Blog个人博客

文章目录 1.前言2.网站搭建2.1. 网页下载和安装2.2.网页测试2.3.cpolar的安装和注册 3.本地网页发布3.1.Cpolar临时数据隧道3.2.Cpolar稳定隧道&#xff08;云端设置&#xff09;3.3.Cpolar稳定隧道&#xff08;本地设置&#xff09; 4.公网访问测试5.结语 1.前言 Ubuntu系统作…
阅读更多...
【深度学习】pytorch pth模型转为onnx模型后出现冗余节点“identity”，onnx模型的冗余节点“identity”

【深度学习】pytorch pth模型转为onnx模型后出现冗余节点“identity”，onnx模型的冗余节点“identity”

情況描述 onnx模型的冗余节点“identity”如下图。 解决方式 首先&#xff0c;确保您已经安装了onnx-simplifier库&#xff1a; pip install onnx-simplifier然后&#xff0c;您可以按照以下方式使用onnx-simplifier库&#xff1a; import onnx from onnxsim import simp…
阅读更多...
STM32F407软件模拟I2C实现MPU6050通讯（CUBEIDE）

STM32F407软件模拟I2C实现MPU6050通讯（CUBEIDE）

STM32F407软件模拟I2C实现MPU6050通讯&#xff08;CUBEIDE&#xff09; 文章目录 STM32F407软件模拟I2C实现MPU6050通讯&#xff08;CUBEIDE&#xff09;模拟I2C读写的实现mpu6050_iic.cmpu6050_iic.h代码分析 复位&#xff0c;读取温度&#xff0c;角度等函数封装mpu6050.cmpu…
阅读更多...
QT学习07：五种按钮控件

QT学习07：五种按钮控件

文章首发于我的个人博客&#xff1a;欢迎大佬们来逛逛 文章目录 抽象类&#xff1a;QAbstractButtonQPushButtonQToolButtonQCommandLinkButtonQRadioButtonQCheckBoxQButtonGroup 抽象类&#xff1a;QAbstractButton 是所有按钮类的祖先。 QAbstractButton的信号&#xff1a…
阅读更多...
深入理解CSS字符转义行为

深入理解CSS字符转义行为

深入理解CSS字符转义行为 深入理解CSS字符转义行为 前言为什么要转义&#xff1f;CSS 转义什么是合法css的表达式 左半部分右半部分 练习参考链接 前言 在日常的开发中&#xff0c;我们经常写css。比如常见的按钮: <button class"btn"></button>&am…
阅读更多...
【MySQL】 IS NOT NULL 和 != NULL 的区别？

【MySQL】 IS NOT NULL 和 != NULL 的区别？

背景 最近在开发小伙伴的需求&#xff0c;遇到了一个数据库统计的问题&#xff0c; is not null 结果正确 &#xff01;null 结果就不对&#xff0c;然后就激发了获取真理的想法&#xff0c;那必须的查查 咋回事嘞&#xff1f; 开整 在用MySQL的过程中&#xff0c;你是否存…
阅读更多...
大学物理（上）-期末知识点结合习题复习（4）——质点运动学-动能定理 力做功 保守力与非保守力 势能 机械能守恒定律 完全弹性碰撞

大学物理（上）-期末知识点结合习题复习（4）——质点运动学-动能定理 力做功 保守力与非保守力 势能 机械能守恒定律 完全弹性碰撞

目录 1.力做功 恒力作用下的功 变力的功 2.动能定理 3.保守力与非保守力 4.势能 引力的功与弹力的功 引力势能与弹性势能 5.保守力做功与势能的关系 6.机械能守恒定律 7.完全弹性碰撞 题1 题目描述 题解 题2 题目描述 题解 1.力做功 物体在力作用下移动做功…
阅读更多...
AWS CodeWhisperer 简单介绍

AWS CodeWhisperer 简单介绍

一、何为AWS CodeWhisperer Amazon CodeWhisperer能够理解以自然语言&#xff08;英语&#xff09;编写的注释&#xff0c;并能实时生成多条代码建议&#xff0c; 以此提高开发人员生产力。 二、主要功能 Amazon CodeWhisperer 的主要功能&#xff0c;包括代码生成、引用追踪…
阅读更多...
36.SpringBoot实用篇—运维

36.SpringBoot实用篇—运维

目录 一、实用篇—运维。 &#xff08;1&#xff09;程序打包与运行&#xff08;Windows版&#xff09;。 &#xff08;2&#xff09;spring-boot-maven-plugin插件作用。 &#xff08;3&#xff09;程序打包与运行&#xff08;Linux版&#xff09;。 &#xff08;4&#…
阅读更多...
chatgpt赋能python：Python中如何处理多个输入

chatgpt赋能python：Python中如何处理多个输入

Python中如何处理多个输入 在编写Python程序时&#xff0c;我们经常需要从用户那里获取多个输入来执行某些操作。本文将介绍Python中的各种方法来处理多个输入。 从终端获取多个输入 Python中最简单的方式是从终端获取多个输入。下面是一个基本的例子&#xff1a; input_st…
阅读更多...
SpringSecurity实现前后端分离登录token认证详解

SpringSecurity实现前后端分离登录token认证详解

目录 1. SpringSecurity概述 1.1 权限框架 1.1.1 Apache Shiro 1.1.2 SpringSecurity 1.1.3 权限框架的选择 1.2 授权和认证 1.3 SpringSecurity的功能 2.SpringSecurity 实战 2.1 引入SpringSecurity 2.2 认证 2.2.1 登录校验流程 2.2.2 SpringSecurity完整流程 2.2.…
阅读更多...
Splashtop 与 Pax8 合作为 MSP 提供简化的远程支持解决方案

Splashtop 与 Pax8 合作为 MSP 提供简化的远程支持解决方案

2023年4月27日 科罗拉多州丹佛 Pax8 是一个行业领先的云商务市场&#xff0c;该公司今天宣布将通过 Pax8 市场在全球推出其全新运营供应商 Splashtop。Splashtop 的远程访问、支持以及端点监控和管理解决方案极具成本效益&#xff0c;而且功能强大&#xff0c;可以助力托管服务…
阅读更多...
002、体系结构之TiDB Server

002、体系结构之TiDB Server

TiDB Server 1、TiDB总览1.1、TiDB Server架构1.2、TiDB Server 主要功能&#xff1a; 2、SQL语句处理语句的解析和编译SQL层协议层上下文解析层逻辑优化器物理优化器本地执行器分布式执行器 3、如何将表的数据转成kv形式4、在线DDL相关模块5、GC机制与相关模块6、TiDB Server …
阅读更多...
你真的会写软件测试简历吗？为什么面试约不到，测试老鸟的建议...

你真的会写软件测试简历吗？为什么面试约不到，测试老鸟的建议...

目录&#xff1a;导读 前言一、Python编程入门到精通二、接口自动化项目实战三、Web自动化项目实战四、App自动化项目实战五、一线大厂简历六、测试开发DevOps体系七、常用自动化测试工具八、JMeter性能测试九、总结&#xff08;尾部小惊喜&#xff09; 前言 写好一份简历的三…
阅读更多...
Frida技术—逆向开发的屠龙刀

Frida技术—逆向开发的屠龙刀

简介 Frida是一种基于JavaScript的动态分析工具&#xff0c;可以用于逆向开发、应用程序的安全测试、反欺诈技术等领域。Frida主要用于在已安装的应用程序上运行自己的JavaScript代码&#xff0c;从而进行动态分析、调试、修改等操作&#xff0c;能够绕过应用程序的安全措施&a…
阅读更多...
mac下部署和访问 Kubernetes 仪表板（Dashboard）

mac下部署和访问 Kubernetes 仪表板（Dashboard）

简介 Dashboard 是基于网页的 Kubernetes 用户界面。 你可以使用 Dashboard 将容器应用部署到 Kubernetes 集群中&#xff0c;也可以对容器应用排错&#xff0c;还能管理集群资源。 你可以使用 Dashboard 获取运行在集群中的应用的概览信息&#xff0c;也可以创建或者修改 Kub…
阅读更多...
最新文章

Copyright @ 2022~2023