红黑树——RBTree

红黑树的概念：

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

红黑树的性质

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

为什么满足上面的性质，红黑树就能保证，最长路径中的节点个数不会超过最短路径上节点数的两倍？
原因：因为红黑树是用颜色来保持平衡的，而且红色节点不能连续，并且从根节点到任意一个叶子节点其路径上的黑色节点个数都相等。

红黑树节点的定义

//红黑树结点的定义
template<class K, class V>
struct RBTreeNode
{
   
	//三叉链
	RBTreeNode<K, V>* _left;
	RBTreeNode<K, V>* _right;
	RBTreeNode<K, V>* _parent;

	//存储的键值对
	pair<K, V> _kv;

	//结点的颜色
	int _col; //红/黑

	//构造函数
	RBTreeNode(const pair<K, V>& kv)
		:_left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
		, _kv(kv)
		, _col(RED)
	{
   }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

红黑树的插入

按照二叉搜索树规则对新节点进行插入

//插入函数
	pair<Node*, bool> Insert(const pair<K, V>& kv)
	{
   
		if (_root == nullptr) //若红黑树为空树，则插入结点直接作为根结点
		{
   
			_root = new Node(kv);
			_root->_col = BLACK; //根结点必须是黑色
			return make_pair(_root, true); //插入成功
		}
		//1、按二叉搜索树的插入方法，找到待插入位置
		Node* cur = _root;
		Node* parent = nullptr;
		while (cur)
		{
   
			if (kv.first < cur->_kv.first) //待插入结点的key值小于当前结点的key值
			{
   
				//往该结点的左子树走
				parent = cur;
				cur = cur->_left;
			}
			else 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24