二叉搜索树再升级——红黑树

二叉搜索树再升级——红黑树

  • 红黑树的概念
  • 红黑树的插入
  • uncle为granfather的右孩子
    • uncle结点为红色
    • uncle结点为空或黑色
  • uncle为granfather的左孩子

红黑树的概念

之前我们学习了AVL树，这是一种判断左右子树高度来严格控制总体树的高度的树。条件相对来说比较苛刻。我们今天要学习的红黑树，它不是通过左右子树高度来控制总体高度，而是通过结点的颜色来控制树的高度。

从字面意思上来说，红黑树，就是树的结点要么是黑的，要么是红的。
在这里插入图片描述但是这个红黑树的红色结点和黑色结点不是想怎么排就怎么排，红黑结点的插入顺序是有讲究的：

  1. 每个结点不是红色就是黑色
  2. 根节点是黑色的
  3. 如果一个节点是红色的，则它的两个孩子结点是黑色的
  4. 对于每个结点，从该结点到其所有后代叶结点的简单路径上均包含相同数目的黑色结点
  5. 每个叶子结点都是黑色的(此处的叶子结点指的是空结点)

其中2,3是控制树的高度的手段。我们来看第2条，第2条说白了就是：不能出现连续的红色结点。
在这里插入图片描述
对于第3条，我们研究两种极端情况：
在这里插入图片描述对于我们来说，左边这种全部是黑色结点的路径为最短路径，右边这种一黑一红的路径我们称为最长路径。如果我们以每条路径上的黑色结点作为我们的路径长度，那么我们我们一棵树每一条的路径长度都应该在N~2N之间。这样保证了树的高度。
这里注意第5点，这里的叶子结点指的是空节点，空节点是黑色。
在这里插入图片描述

红黑树的插入

了解完红黑树的基本概念之后，我们来上手写一下红黑树，我们先把红黑树的结点封装好：

//红黑树的颜色因子
enum Color
{
	RED,
	BLACK
};

//红黑树结点封装
template <class K,class V>
struct RBTreeNode
{
	RBTreeNode<K, V>* _leftchild;
	RBTreeNode<K, V>* _rightchild;
	RBTreeNode<K, V>* _parent;
	Color _col; //颜色因子
	pair<K, V> _kv;

	RBTreeNode(const pair<K,V>& kv)
		:_leftchild(nullptr)
		,_rightchild(nullptr)
		,_parent(nullptr)
		,_col(RED)
		,_kv(kv)
	{

	}
};

我们也来看看红黑树的插入：首先红黑树是搜索二叉树，插入的逻辑和之前的搜索二叉树的逻辑是一样的。

//红黑树
template <class K,class V>
class RBTree
{
	typedef RBTreeNode<K, V> _Node;
private:
	bool Insert(const pair<K,V>& kv)
	{
		if (_root == nullptr)
		{
			_root = new _Node(kv);
			return true;
		}

		_Node* parent = nullptr;
		_Node* cur = _root;

		while (cur)
		{
			if (cur->_kv.first < kv.first)
			{
				parent = cur;
				cur = cur->_rightchild;
			}
			else if (cur->_kv.first < kv.first)
			{
				parent = cur;
				cur = cur->_leftchild;
			}
			else
			{
				return false;
			}
		}

		cur = new _Node(kv);
		
		if (cur->_kv.first < parent->_kv.first)
		{
			parent->_leftchild = cur;
			cur->_parent = parent;
		}
		else if (cur->_kv.first > parent->_kv.first)
		{
			parent->_rightchild = cur;
			cur->_parent = parent;
		}

		//失衡，调整
		while ()
		{

		}
	}

private:
	_Node* _root = nullptr;
};

那么问题来了，我们是插入黑色结点好呢？还是红色结点好呢？
这里注意一下，如果直接插入黑色结点，可能会直接导致某一条路径上的黑色结点直接加一，直接导致整棵树失衡。所以这是一种不明智的做法。
所以明智的做法就是，我们插入红色结点，之后如果有失衡，还有回旋的余地。

我们有两种情况要考虑：
第一种：插入结点的父亲结点是黑色
在这里插入图片描述

这个时候我们可以完全不用管，因为我们并没有改变任何一条黑色路径上的黑色结点的数量，整棵树在整体上还是平衡的。

第二种：插入结点的父亲结点是红色
在这里插入图片描述

这个时候，违反了规则3，不能出现连续的红色结点，这个时候该怎么办呢？此时我们知道7这个结点是一定要变成黑色的：
在这里插入图片描述
这个时候7这条路径上的黑色结点莫名奇妙多了一个，为了使各路黑色结点均衡，我们将6这个结点变成红色：
在这里插入图片描述这个时候5这条的黑色结点又会莫名其妙少一个，这个时候我们可以将5这个结点变成黑色：
在这里插入图片描述
这样是不是就好啦？
我们上面只是做了一个简单的分析，我们现在来认真分析一下：

uncle为granfather的右孩子

uncle结点为红色

我们这里把每个结点标好名字：约定:cur为当前节点，p为父节点，g为祖父节点，u为叔叔节点
在这里插入图片描述当uncle结点为红色，parent结点为红色时，这时候我们这时候有连续的红色结点，这个时候我们将一层一层的变色，直到结点为根结点，根节点为黑色截止。

我们再来解释一下为什么直到根节点变色才结束：
如果此时的g为根节点：
在这里插入图片描述
这个时候虽然个没有变色，但是g为根节点，就代表每一条路径都加了一个黑色结点，每条路径上的黑色结点数量都是一样的。

如果此时的g不为根结点，而是一棵子树，就没法保证每一条路径上都增加一个黑色结点，所以这个时候变成红色结点是最保险的。
在这里插入图片描述
为了让情况变简单，我们在变色结束的时候，直接对根节点进行变黑处理：

		//出现连续红色结点，失衡，调整
		while (parent && parent->_col == RED)
		{
			//记录祖父
			//    g
			//  p   u
			//c
			_Node* grandfather = parent->_parent;

			//找叔叔结点
			if (grandfather->_leftchild == parent)
			{
				_Node* uncle = grandfather->_rightchild;
				if (uncle && uncle->_col == RED)
				{
					parent->_col = uncle->_col = BLACK;
					grandfather->_col = RED;

					//向上迭代
					cur = grandfather;
					parent = cur->_parent;
				}
			}
		}

		_root->_col = BLACK;
		return true;

uncle结点为空或黑色

此时还有第二种情况：如果uncle结点为空，或者uncle结点为黑色。
我们先来看uncle结点为空的情况：
在这里插入图片描述

这个时候，我们发现单纯的变色已经解决不了问题了，这个时候，我们的想办法让这棵树平衡一点。诶？我们之前学习AVL树的时候，学习过如何让一棵树平衡，以上面的树为例，以g的视角来看，我是左子树高，所以我要进行左左旋：
在这里插入图片描述
这个时候高度平衡一些了，这个时候我们要处理的就是颜色问题，因为这个时候就只有颜色不平衡了，很简单，变色就是。
在这里插入图片描述
第一种情况我们已经讨论了，我们现在来看第二种情况，uncle结点为黑。

在这里插入图片描述
这个也是，树不平衡，首先进行旋转：
在这里插入图片描述这个时候进变色处理：
在这里插入图片描述可能这个图还是有点抽象，我们看第一棵子树，我们考虑一下：这棵树原本就是这样的吗？
在这里插入图片描述如果这棵树原本就是这样的，那么，左边的黑色结点树比右边的黑色结点树要少1，肯定是不平衡的，那说明一个问题，这棵树的状态肯定还在变化之中。那么说明这棵树一开始的状态是这样的：

在这里插入图片描述
然后变色变上去：
在这里插入图片描述
这里注意一下，如果这棵树为AVL树其实从p开始就要开始调整了，因为这时候树的高度已经失衡了。但是红黑树是依据每条路径上黑色结点的数量来判定的。这时候黑色结点的数量是满足要求，但是因为不能出现连续的红色结点，所以我们以g开始旋转：

在这里插入图片描述
这个时候变色：
在这里插入图片描述其中注意，为了保持上面的图是平衡的红黑树，所以c为带一个黑结点的红黑树，d和c要么为空，要么为一个红色结点。

了解完基本的思路之后，我们开始来写代码：

			//找叔叔结点
			if (grandfather->_leftchild == parent)
			{
				_Node* uncle = grandfather->_rightchild;
				if (uncle && uncle->_col == RED)
				{
					parent->_col = uncle->_col = BLACK;
					grandfather->_col = RED;

					//向上迭代
					cur = grandfather;
					parent = cur->_parent;
				}
				else if (!uncle || uncle->_col == BLACK)
				{
					//旋转+变色
					//    g
					//  p
					//c
					if (cur == parent->_leftchild)
					{
						//进行左左旋
						RoateLL(grandfather); //AVL树中的左左旋
						parent->_col = BLACK;
						grandfather->_col = RED;
					}
				}

那我们在AVL树中有双旋，那么在红黑树中有双旋吗？答案是有的，这就是我们的第三种情况：
第三种情况：
在这里插入图片描述这种情况我们先进行一个右右旋，在进行一个左左旋就好啦！
在这里插入图片描述
在这里插入图片描述

			//找叔叔结点
			if (grandfather->_leftchild == parent)
			{
				_Node* uncle = grandfather->_rightchild;
				if (uncle && uncle->_col == RED)
				{
					parent->_col = uncle->_col = BLACK;
					grandfather->_col = RED;

					//向上迭代
					cur = grandfather;
					parent = cur->_parent;
				}
				else if (!uncle || uncle->_col == BLACK)
				{
					//旋转+变色
					//    g
					//  p
					//c
					if (cur == parent->_leftchild)
					{
						//进行左左旋
						RoateLL(grandfather); //AVL树中的左左旋
						parent->_col = BLACK;
						grandfather->_col = RED;
					}
					else if (cur == parent->_leftchild)
						//    g
						//  p
						//     c
					{
						RoateRR(parent);
						RoateLL(grandfather);
						cur->_col = BLACK;
						grandfather = RED;
					}
					break; //黑色为终结态，变色完之后跳出
				}

到目前为止，我们只分析了parent为grandfather的左孩子的情况，现在我们来讨论一下parent为grandfather右孩子的情况。

uncle为granfather的左孩子

我们来看具体的图片：

在这里插入图片描述
这个我们对照着uncle为右孩子的方式来看，上图的话就单纯的变色就好了：
在这里插入图片描述当uncle结点为空或者为黑的时候。
在这里插入图片描述在这里插入图片描述

			else if (grandfather->_rightchild == parent)
			{
				//   g
				// u   p
				//       c
				_Node* uncle = grandfather->_leftchild;
				if (uncle && uncle->_col == RED)
				{
					parent->_col = uncle->_col = RED;
					grandfather->_col = BLACK;

					cur = grandfather;
					parent = cur ->_parent;
				}
				else if (!uncle || uncle->_col == BLACK)
				{
					//  g
					//    p
					//      c
					if (cur == parent->_rightchild)
					{
						//进行右右旋
						RoateRR(grandfather);
						parent->_col = BLACK;
						grandfather->_col = RED;
					}
					//   g         //  g
					//     p       //    c
					//   c         //      p
					else if (cur == parent->_leftchild)
					{
						//进行左左旋
						RoateLL(parent);
						//进行右右旋
						RoateRR(grandfather);

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

附上完整的插入代码：

	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->_rightchild;
			}
			else if (cur->_kv.first > kv.first)
			{
				parent = cur;
				cur = cur->_leftchild;
			}
			else
			{
				return false;
			}
		}

		cur = new _Node(kv);
		
		
		if (cur->_kv.first < parent->_kv.first)
		{
			parent->_leftchild = cur;
			cur->_parent = parent;
		}
		else if (cur->_kv.first > parent->_kv.first)
		{
			parent->_rightchild = cur;
			cur->_parent = parent;
		}

		//出现连续红色结点，失衡，调整
		while (parent && parent->_col == RED)
		{
			//记录祖父
			//    g
			//  p   u
			//c
			_Node* grandfather = parent->_parent;

			//找叔叔结点
			if (grandfather->_leftchild == parent)
			{
				_Node* uncle = grandfather->_rightchild;
				if (uncle && uncle->_col == RED)
				{
					parent->_col = uncle->_col = BLACK;
					grandfather->_col = RED;

					//向上迭代
					cur = grandfather;
					parent = cur->_parent;
				}
				else if (!uncle || uncle->_col == BLACK)
				{
					//旋转+变色
					//    g
					//  p
					//c
					if (cur == parent->_leftchild)
					{
						//进行左左旋
						RoateLL(grandfather); //AVL树中的左左旋
						parent->_col = BLACK;
						grandfather->_col = RED;
					}
					else if (cur == parent->_rightchild)
						//    g
						//  p
						//     c
					{
						RoateRR(parent);
						RoateLL(grandfather);
						cur->_col = BLACK;
						grandfather ->_col= RED;
					}
					break; //黑色为终结态，变色完之后跳出
				}
			}
			else if (grandfather->_rightchild == parent)
			{
				//   g
				// u   p
				//       c
				_Node* uncle = grandfather->_leftchild;
				if (uncle && uncle->_col == RED)
				{
					parent->_col = uncle->_col = RED;
					grandfather->_col = BLACK;

					cur = grandfather;
					parent = cur ->_parent;
				}
				else if (!uncle || uncle->_col == BLACK)
				{
					//  g
					//    p
					//      c
					if (cur == parent->_rightchild)
					{
						//进行右右旋
						RoateRR(grandfather);
						parent->_col = BLACK;
						grandfather->_col = RED;
					}
					//   g         //  g
					//     p       //    c
					//   c         //      p
					else if (cur == parent->_leftchild)
					{
						//进行左左旋
						RoateLL(parent);
						//进行右右旋
						RoateRR(grandfather);

						cur->_col = BLACK;
						grandfather->_col = RED;
					}
					break;
				}
			}	
		}
		_root->_col = BLACK;
		return true;
	}
	void RoateLL(_Node* parent) //左左旋
	  //   p
	 // subL
	//cur
	{
		_Node* subL = parent->_leftchild;
		_Node* subLR = subL->_rightchild;

		//改变指向
		subL->_rightchild = parent;
		parent->_leftchild = subLR;

		if (subLR)
			subLR->_parent = parent;

		//记录爷爷结点
		_Node* grandfather = parent->_parent;

		parent->_parent = subL;

		if (_root == parent)
		{
			_root = subL;
			subL->_parent = nullptr;
		}
		else
		{
			if (grandfather->_leftchild == parent)
			{
				grandfather->_leftchild = subL;
			}
			else if (grandfather->_rightchild == parent)
			{
				grandfather->_rightchild = subL;
			}
			subL->_parent = grandfather;
		}
	}

	void RoateRR(_Node* parent) //右右旋
	{
		_Node* subR = parent->_rightchild;
		_Node* subRL = subR->_leftchild;

		//改变指向
		subR->_leftchild = parent;
		parent->_rightchild = subRL;

		if (subRL)
			subRL->_parent = parent;

		//记录祖父
		_Node* grandfather = parent->_parent;

		parent->_parent = subR;

		if (_root == parent)
		{
			_root = subR;
			subR->_parent = nullptr;
		}
		else
		{
			if (grandfather->_leftchild == parent)
			{
				grandfather->_leftchild = subR;
			}
			else if (grandfather->_rightchild == parent)
			{
				grandfather->_rightchild = subR;
			}
			subR->_parent = grandfather;
		}
	}

我们可以用大量的数据简单测试一下：

int main()
{
	const int N = 10000;
	vector<int> v;
	v.reserve(N);
	srand(time(0));

	for (size_t i = 0; i < N; i++)
	{
		v.push_back(rand());
		//cout << v.back() << endl;
	}

	RBTree<int, int> t;
	for (auto e : v)
	{
		t.Insert(make_pair(e, e));
		//cout << "Insert:" << e << "->" << t.IsBalance() << endl;
	}
	t.InOrder();
}

在这里插入图片描述但是这样只能保证这棵树是二叉搜索树，但如何证明这棵树是一棵平衡的红黑树呢？我么可以统计一条路径上的黑色结点数量，然后对比每一条路径的黑色结点是否相等。

	bool Check(_Node* node,int blacknum,const int refVal)
	{
		if (node == nullptr)
		{
			if (refVal != blacknum)
			{
				return false;
			}
			cout << "黑色结点的数量：" << blacknum << endl;
			return true;
		}

		//检查是否有连续的红色结点
		if (node->_col == RED)
		{
			if (node->_parent->_col == RED)
			{
				cout << "有连续的红色结点" << endl;
				return false;
			}
		}

		//黑色结点
		if (node->_col == BLACK)
		{
			++blacknum;
		}

		return Check(node->_leftchild, blacknum, refVal) &&
			Check(node->_rightchild, blacknum, refVal);
	}

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

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

		记录容器
		//vector<int> v;

		//Check(_root,0,v);

		//int first = v[0];
		//int total = 0;
		//for (auto e : v)
		//{
		//	total += e;
		//}
		//if (total != first * v.size())
		//{
		//	cout << "此树不平衡" << endl;
		//	return false;
		//}
		//else
		//{
		//	return true;
		//}
		int blacknum = 0; //先统计一条路径上的黑色结点数量
		int refVal = 0;
		_Node* cur = _root;

		while (cur)
		{
			if (cur->_col == BLACK)
				refVal++;

			cur = cur->_leftchild;
		}

		return Check(_root, blacknum,refVal);
	}

在这里插入图片描述
附上源码：

#pragma once
#include<iostream>
#include<vector>
using namespace std;

//红黑树的颜色因子
enum Color
{
	RED,
	BLACK
};

//红黑树结点封装
template <class K,class V>
struct RBTreeNode
{
	RBTreeNode<K, V>* _leftchild;
	RBTreeNode<K, V>* _rightchild;
	RBTreeNode<K, V>* _parent;
	Color _col; //颜色因子
	pair<K, V> _kv;

	RBTreeNode(const pair<K,V>& kv)
		:_leftchild(nullptr)
		,_rightchild(nullptr)
		,_parent(nullptr)
		,_col(RED)
		,_kv(kv)
	{

	}
};

//红黑树
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;
		}

		_Node* parent = nullptr;
		_Node* cur = _root;

		while (cur)
		{
			if (cur->_kv.first < kv.first)
			{
				parent = cur;
				cur = cur->_rightchild;
			}
			else if (cur->_kv.first > kv.first)
			{
				parent = cur;
				cur = cur->_leftchild;
			}
			else
			{
				return false;
			}
		}

		cur = new _Node(kv);
		
		
		if (cur->_kv.first < parent->_kv.first)
		{
			parent->_leftchild = cur;
			cur->_parent = parent;
		}
		else if (cur->_kv.first > parent->_kv.first)
		{
			parent->_rightchild = cur;
			cur->_parent = parent;
		}

		//if (cur == parent->_leftchild)
		//{
		//	parent->_leftchild = cur;
		//	cur->_parent = parent;
		//}
		//else if (cur == parent->_rightchild)
		//{
		//	parent->_rightchild = cur;
		//	cur->_parent = parent;
		//}

		//出现连续红色结点，失衡，调整
		while (parent && parent->_col == RED)
		{
			//记录祖父
			//    g
			//  p   u
			//c
			_Node* grandfather = parent->_parent;

			//找叔叔结点
			if (grandfather->_leftchild == parent)
			{
				_Node* uncle = grandfather->_rightchild;
				if (uncle && uncle->_col == RED)
				{
					parent->_col = uncle->_col = BLACK;
					grandfather->_col = RED;

					//向上迭代
					cur = grandfather;
					parent = cur->_parent;
				}
				else if (!uncle || uncle->_col == BLACK)
				{
					//旋转+变色
					//    g
					//  p
					//c
					if (cur == parent->_leftchild)
					{
						//进行左左旋
						RoateLL(grandfather); //AVL树中的左左旋
						parent->_col = BLACK;
						grandfather->_col = RED;
					}
					else if (cur == parent->_rightchild)
						//    g
						//  p
						//     c
					{
						RoateRR(parent);
						RoateLL(grandfather);
						cur->_col = BLACK;
						grandfather ->_col= RED;
					}
					break; //黑色为终结态，变色完之后跳出
				}
			}
			else if (grandfather->_rightchild == parent)
			{
				//   g
				// u   p
				//       c
				_Node* uncle = grandfather->_leftchild;
				if (uncle && uncle->_col == RED)
				{
					parent->_col = uncle->_col = RED;
					grandfather->_col = BLACK;

					cur = grandfather;
					parent = cur ->_parent;
				}
				else if (!uncle || uncle->_col == BLACK)
				{
					//  g
					//    p
					//      c
					if (cur == parent->_rightchild)
					{
						//进行右右旋
						RoateRR(grandfather);
						parent->_col = BLACK;
						grandfather->_col = RED;
					}
					//   g         //  g
					//     p       //    c
					//   c         //      p
					else if (cur == parent->_leftchild)
					{
						//进行左左旋
						RoateLL(parent);
						//进行右右旋
						RoateRR(grandfather);

						cur->_col = BLACK;
						grandfather->_col = RED;
					}
					break;
				}
			}	
		}
		_root->_col = BLACK;
		return true;
	}
	void RoateLL(_Node* parent) //左左旋
	  //   p
	 // subL
	//cur
	{
		_Node* subL = parent->_leftchild;
		_Node* subLR = subL->_rightchild;

		//改变指向
		subL->_rightchild = parent;
		parent->_leftchild = subLR;

		if (subLR)
			subLR->_parent = parent;

		//记录爷爷结点
		_Node* grandfather = parent->_parent;

		parent->_parent = subL;

		if (_root == parent)
		{
			_root = subL;
			subL->_parent = nullptr;
		}
		else
		{
			if (grandfather->_leftchild == parent)
			{
				grandfather->_leftchild = subL;
			}
			else if (grandfather->_rightchild == parent)
			{
				grandfather->_rightchild = subL;
			}
			subL->_parent = grandfather;
		}
	}

	void RoateRR(_Node* parent) //右右旋
	{
		_Node* subR = parent->_rightchild;
		_Node* subRL = subR->_leftchild;

		//改变指向
		subR->_leftchild = parent;
		parent->_rightchild = subRL;

		if (subRL)
			subRL->_parent = parent;

		//记录祖父
		_Node* grandfather = parent->_parent;

		parent->_parent = subR;

		if (_root == parent)
		{
			_root = subR;
			subR->_parent = nullptr;
		}
		else
		{
			if (grandfather->_leftchild == parent)
			{
				grandfather->_leftchild = subR;
			}
			else if (grandfather->_rightchild == parent)
			{
				grandfather->_rightchild = subR;
			}
			subR->_parent = grandfather;
		}
	}


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

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

		_InOrder(root->_leftchild);
		cout << root->_kv.first << endl;
		_InOrder(root->_rightchild);
	}

	bool Check(_Node* node, int blacknum, const int refVal)
	{
		if (node == nullptr)
		{
			if (refVal != blacknum)
			{
				return false;
			}
			cout << "黑色结点的数量：" << blacknum << endl;
			return true;
		}

		//检查是否有连续的红色结点
		if (node->_col == RED)
		{
			if (node->_parent->_col == RED)
			{
				cout << "有连续的红色结点" << endl;
				return false;
			}
		}

		//黑色结点
		if (node->_col == BLACK)
		{
			++blacknum;
		}

		return Check(node->_leftchild, blacknum, refVal) &&
			Check(node->_rightchild, blacknum, refVal);
	}

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

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

		记录容器
		//vector<int> v;

		//Check(_root,0,v);

		//int first = v[0];
		//int total = 0;
		//for (auto e : v)
		//{
		//	total += e;
		//}
		//if (total != first * v.size())
		//{
		//	cout << "此树不平衡" << endl;
		//	return false;
		//}
		//else
		//{
		//	return true;
		//}
		int blacknum = 0;
		int refVal = 0;
		_Node* cur = _root;

		while (cur)
		{
			if (cur->_col == BLACK)
				refVal++;

			cur = cur->_leftchild;
		}

		return Check(_root, blacknum, refVal);
	}

private:
	_Node* _root = nullptr;
};

#define _CRT_SECURE_NO_WARNINGS 1
#include"RBTree.h"

int main()
{
	const int N = 10000;
	vector<int> v;
	v.reserve(N);
	srand(time(0));

	for (size_t i = 0; i < N; i++)
	{
		v.push_back(rand());
		//cout << v.back() << endl;
	}

	RBTree<int, int> t;
	for (auto e : v)
	{
		t.Insert(make_pair(e, e));
		//cout << "Insert:" << e << "->" << t.IsBalance() << endl;
	}
	t.InOrder();
	t.isTrue();
}

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

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

相关文章

黑马点评笔记 redis缓存三大问题解决

黑马点评笔记 redis缓存三大问题解决

文章目录 缓存问题缓存穿透问题的解决思路编码解决商品查询的缓存穿透问题 缓存雪崩问题及解决思路缓存击穿问题及解决思路问题分析使用锁来解决代码实现 逻辑过期方案代码实现 缓存问题 我们熟知的是用到缓存就会遇到缓存三大问题&#xff1a; 缓存穿透缓存击穿缓存雪崩 接…
阅读更多...
Kafka 常用功能总结（不断更新中....）

Kafka 常用功能总结（不断更新中....）

kafka 用途 业务中我们经常用来两个方面 1.发送消息 2.发送日志记录 kafka 结构组成 broker&#xff1a;可以理解成一个单独的服务器&#xff0c;所有的东西都归属到broker中 partation&#xff1a;为了增加并发度而做的拆分&#xff0c;相当于把broker拆分成不同的小块&…
阅读更多...
基于Python实现汽车销售数据可视化+预测【500010086.1】

基于Python实现汽车销售数据可视化+预测【500010086.1】

导入模块 import numpy as np import pandas as pd from pylab import mpl import plotly.express as px import matplotlib.pyplot as plt import seaborn as sns设置全局字体 plt.rcParams[font.sans-serif][kaiti]获取数据 total_sales_df pd.read_excel(r"./data/中…
阅读更多...
从根到叶：随机森林模型的深入探索

从根到叶：随机森林模型的深入探索

一、说明 在本综合指南中&#xff0c;我们将超越基础知识。当您盯着随机森林模型的文档时&#xff0c;您将不再对“节点杂质”、“加权分数”或“成本复杂性修剪”等术语感到不知所措。相反&#xff0c;我们将剖析每个参数&#xff0c;阐明其作用和影响。通过理论和 Python 实践…
阅读更多...
【STM32外设系列】GPS定位模块（ATGM336H）

【STM32外设系列】GPS定位模块（ATGM336H）

&#x1f380; 文章作者&#xff1a;二土电子 &#x1f338; 关注公众号获取更多资料&#xff01; &#x1f438; 期待大家一起学习交流&#xff01; 文章目录 一、GPS模块简介二、使用方法2.1 引脚介绍2.2 数据帧介绍2.3 关于不同的启动方式 三、前置知识3.1 strstr函数3.2…
阅读更多...
【洛谷算法题】P5714-肥胖问题【入门2分支结构】

【洛谷算法题】P5714-肥胖问题【入门2分支结构】

&#x1f468;‍&#x1f4bb;博客主页&#xff1a;花无缺 欢迎 点赞&#x1f44d; 收藏⭐ 留言&#x1f4dd; 加关注✅! 本文由 花无缺 原创 收录于专栏 【洛谷算法题】 文章目录 【洛谷算法题】P5714-肥胖问题【入门2分支结构】&#x1f30f;题目描述&#x1f30f;输入格式&a…
阅读更多...
实在智能携“TARS大模型”入选“2023中国数据智能产业AI大模型先锋企业”

实在智能携“TARS大模型”入选“2023中国数据智能产业AI大模型先锋企业”

近日&#xff0c;由数据猿与上海大数据联盟联合主办的“2023企业数智化转型升级发展论坛”在上海圆满收官。 论坛颁奖典礼上&#xff0c;《2023中国数据智能产业AI大模型先锋企业》等六大榜单正式揭晓&#xff0c;旨在表彰在AI领域为数智化升级取得卓越成就和突出贡献的企业&am…
阅读更多...
【Flask使用】全知识md文档，4大部分60页第3篇：Flask模板使用和案例

【Flask使用】全知识md文档，4大部分60页第3篇：Flask模板使用和案例

本文的主要内容&#xff1a;flask视图&路由、虚拟环境安装、路由各种定义、状态保持、cookie、session、模板基本使用、过滤器&自定义过滤器、模板代码复用&#xff1a;宏、继承/包含、模板中特有变量和函数、Flask-WTF 表单、CSRF、数据库操作、ORM、Flask-SQLAlchemy…
阅读更多...
深入浅出理解libevent——2万字总结

深入浅出理解libevent——2万字总结

概述 libevent,libev,libuv都是c实现的异步事件库&#xff0c;注册异步事件&#xff0c;检测异步事件&#xff0c;根据事件的触发先后顺序&#xff0c;调用相对应回调函数处理事件。处理的事件包括&#xff1a;网络 io 事件、定时事件以及信号事件。这三个事件驱动着服务器的运…
阅读更多...
中国智能汽车这一年，主打一个“卷”

中国智能汽车这一年，主打一个“卷”

文丨刘俊宏 “这才刚过去半年多&#xff0c;汽车行业又更新了一轮。”一位车评人在广州车展感叹道。 作为每年最后一个A级车展&#xff0c;广州车展向来被视为中国车市的“风向标”。相比上海车展“拥抱汽车行业新时代”、成都车展“驭见未来”的主题&#xff0c;广州车展“新…
阅读更多...
为什么鼠标按键释放后才执行对应的动作？

为什么鼠标按键释放后才执行对应的动作？

如果你留心观察的话&#xff0c;你会发现这样一个事实&#xff1a;大部分的软件的用户体验中&#xff0c;一般都是在鼠标按键释放后&#xff0c;才会执行相应的动作&#xff0c;而不是按下的时候。例如&#xff0c;当我们按下开始菜单的时候&#xff0c;不会有任何动作发生&…
阅读更多...
数据库基础入门 — SQL运算符

数据库基础入门 — SQL运算符

我是南城余&#xff01;阿里云开发者平台专家博士证书获得者&#xff01; 欢迎关注我的博客&#xff01;一同成长&#xff01; 一名从事运维开发的worker&#xff0c;记录分享学习。 专注于AI&#xff0c;运维开发&#xff0c;windows Linux 系统领域的分享&#xff01; 本…
阅读更多...
2023 年亚马逊黑色星期五和网络星期一的企业电子商务指南

2023 年亚马逊黑色星期五和网络星期一的企业电子商务指南

亚马逊黑色星期五和网络星期一 周末即将到来&#xff01;感恩节于 11 月 23 日举行&#xff0c;紧接着是 24 日黑色星期五和 27 日网络星期一。您的亚马逊业务准备好应对大量涌入了吗&#xff1f; 我们相信您已经准备好黑色星期五优惠并准备好库存&#xff0c;以确保您有足够的…
阅读更多...
一键重装系统Win10专业版教程

一键重装系统Win10专业版教程

在电脑操作过程中&#xff0c;用户如果遇到无法解决的系统问题&#xff0c;就可以考虑直接重新系统。现在&#xff0c;用户想要重新安装一下Win10专业版系统&#xff0c;但是不清楚具体的重装操作步骤。接下来小编给大家介绍轻松重装Win10专业版系统的详细步骤。 推荐下载 系统…
阅读更多...
怎么快速卸载office365

怎么快速卸载office365

怎么快速卸载office365 根据官网提供的两种解决方案即点即用或MSIMicrosoft Store 根据官网提供的两种解决方案 官网地址&#xff1a;https://support.microsoft.com/zh-cn/office/%E4%BB%8E-pc-%E5%8D%B8%E8%BD%BD-office-9dd49b83-264a-477a-8fcc-2fdf5dbf61d8#OfficeVersio…
阅读更多...
如何在AppLink配置金蝶云星空预算使用单流程

如何在AppLink配置金蝶云星空预算使用单流程

上一篇有提到金蝶云星空如何通过AppLink平台配置销售订单操作&#xff0c;这次来演示下如何“保存预算使用单”、“调拨单定时自动审核”以及“预算使用单反审核后删除”操作。 根据请求数据保存预算使用单 当webhook接收到数据时触发流程 步骤1&#xff1a;根据webhook的请…
阅读更多...
监控员工上网有什么软件丨三款好用的员工上网管理软件推荐

监控员工上网有什么软件丨三款好用的员工上网管理软件推荐

监控员工上网行为是企业管理中不可或缺的一部分&#xff0c;因此&#xff0c;选择一款好的监控员工上网的软件至关重要。目前市场上存在多种监控员工上网的软件&#xff0c;它们具有各种特点和功能&#xff0c;但企业需要仔细评估和选择。 一、域之盾软件 这是一款优秀的监控员…
阅读更多...
第十七章 Java链接数据库

第十七章 Java链接数据库

目录 1.登录MySQL 2.创建库和表 3.使用Java命令查询数据库操作 4.右击——点击“Build Path”——选择第四个——找到包的位置——导入成功 一、创建java项目 1.注册驱动 2.获取链接 3.获取statment对象 4.执行sql语句返回结果集 5.遍历结果集 6.关闭连接释放资源 封装…
阅读更多...
给项目快速接入链路追踪

给项目快速接入链路追踪

为什么需要链路追踪&#xff1f; 我们程序员在日常工作中&#xff0c;最常做事情之一就是修bug了。如果程序只是运行在单机上&#xff0c;我们最常用的方式就是在程序上打日志&#xff0c;然后程序运行的过程中将日志输出到文件上&#xff0c;然后我们根据日志去推断程序是哪一…
阅读更多...
事件溯源模式

事件溯源模式

概念解释 事件溯源&#xff08;Event Sourcing&#xff09;是一种设计模式&#xff0c;其核心思想是将系统的状态变化表示为一系列不可变的事件&#xff0c;并将这些事件存储在事件日志中。系统的当前状态可以通过重新应用&#xff08;回放&#xff09;这些事件来还原&#xf…
阅读更多...
最新文章

Copyright @ 2022~2023