【C++map和set容器：AVL树、红黑树详解并封装实现map和set】

[本节目标]

map和set底层结构

AVL树

红黑树

红黑树模拟实现STL中的map和set

1.底层结构

前面对map/multimap/set/multiset进行了简单的介绍，在其文档介绍中发现，这几个容器有个共同点是：其底层都是按照二叉搜索树来实现的，但是二叉搜索树有其自身的缺陷，假如往树中插入的元素有序或者接近有序，二叉搜索树就会退化成单支树，时间复杂度会退化成O(N)，因此 map、set等关联式容器的底层结构是对二叉树进行了平衡处理，即采用平衡树来实现。

2.AVL树

2.1 AVL树的概念

二叉搜索树虽可以缩短查找的效率，但如果数据有序或接近有序二叉搜索树将退化为单支树，查找元素相当于在顺序表中搜索元素，效率低下。因此，两位俄罗斯的数学家G.M.Adelson-Velskii 和E.M.Landis在1962年

发明了一种解决上述问题的方法：当向二叉搜索树中插入新结点后，如果能保证每个结点的左右子树高度之差的绝对值不超过1(需要对树中的结点进行调整)，即可降低树的高度，从而减少平均搜索长度。

一棵AVL树或者是空树，或者是具有以下性质的二叉搜索树：

它的左右子树都是AVL树
左右子树高度之差(简称平衡因子(右子树高度-左子树高度))的绝对值不超过1(-1/0/1)

如果一棵二叉搜索树是高度平衡的，它就是AVL树。如果它有n个结点，其高度可保持在 $O(log_2 n)$，搜索时间复杂度O($log_2 n$)。这里提一个问题，为什么高度差要不超过1，为什么不能是0，这样树更平衡呀，虽然这样的树更平衡，但是条件太苛刻了，如果我们插入的结点个数为2，那么就做不到相等了，最优就是高度差为1。

2.2 AVL树节点的定义

template<class K,class V>
struct AVLTreeNode
{
	AVLTreeNode<K, V>* _left;
	AVLTreeNode<K, V>* _right;
	AVLTreeNode<K, V>* _parent;
	int _bf;//balance factor
	pair<K, V> _kv;

	AVLTreeNode(const pair<K,V>& kv)
		:_left(nullptr)
		,_right(nullptr)
		,_parent(nullptr)
		,_bf(0)
		,_kv(kv)
	{}
};

2.3 AVL树的插入

AVL树就是在二叉搜索树的基础上引入了平衡因子，因此AVL树也可以看成是二叉搜索树。那么 AVL树的插入过程可以分为两步：

1. 按照二叉搜索树的方式插入新节点

2. 调整节点的平衡因子

我们先来看一下新插入的节点会影响那些节点的平衡因子呢？新增节点的部分祖先节点

下面我们再来看一下平衡因子的更新规则。

现在我们就按照上面的规则写一下AVL树插入的代码，先来画一下插入的三种情况的平衡因子图

直接上手代码

bool Insert(const pair<K, V>& kv)
{
	//1. 先按照二叉搜索树的规则将节点插入到AVL树中
	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->_right;
		}
		else if (cur->_kv.first > kv.first)
		{
			parent = cur;
			cur = cur->_left;
		}
		else
		{
			//如果要插入的值和当前值相等，那就不能插入了
			return false;
		}
	}
	//此时_cur为空
	cur = new Node(kv);
	if (parent->_kv.first < kv.first)//要插入的值比当前值大
	{
		parent->_right = cur;
	}
	else//要插入的值比当前值小
	{
		parent->_left = cur;
	}
	cur->_parent = parent;
	//2. 新节点插入后，AVL树的平衡性可能会遭到破坏，此时就需要更新平衡因子，并检测是否\
		破坏了AVL树的平衡性

	/*
			cur插入后，parent的平衡因子一定需要调整，在插入之前，parent
			的平衡因子分为三种情况：-1，0, 1, 分以下两种情况：
			1. 如果cur插入到parent的左侧，只需给parent的平衡因子-1即可
			2. 如果cur插入到parent的右侧，只需给parent的平衡因子+1即可

			此时：parent的平衡因子可能有三种情况：0，正负1， 正负2
			1. 如果parent的平衡因子为0，说明插入之前parent的平衡因子为正负1，插入后被调整
		成0，此时满足AVL树的性质，插入成功

			2. 如果parent的平衡因子为正负1，说明插入前parent的平衡因子一定为0，插入后被更
		新成正负1，此时以parent为根的树的高度增加，需要继续向上更新

			3. 如果parent的平衡因子为正负2，则parent的平衡因子违反平衡树的性质，需要对其进
		行旋转处理
		*/

	while (parent)
	{
		// 更新双亲的平衡因子
		if (parent->_left == cur)
		{
			parent->_bf--;
		}
		else
		{
			parent->_bf++;
		}
		// 更新后检测双亲的平衡因子
		if (parent->_bf == 0)//满足AVL树的性质
		{
			break;
		}
		else if(parent->_bf == -1 || parent->_bf == 1)
		{
			// 插入前双亲的平衡因子是0，插入后双亲的平衡因为为1 或者 -1 ，
			// 说明以双亲为根的二叉树的高度增加了一层，因此需要继续向上调整
			cur = cur->_parent;
			parent = parent->_parent;
		}
		else if (parent->_bf == -2 || parent->_bf == 2)
		{
			//双亲的平衡因子为正负2，违反了AVL树的平衡性，
			// 需要对以pParent为根的树进行旋转处理
		}
		else
		{
			//插入之前AVL树就存在问题
			assert(false);
		}
	}
	return true;
}

2.4 AVL树的旋转

旋转的目的：

1.保持搜索规则
2、当前树从不平衡旋转为平衡
3、降低当前树的高度

如果在一棵原本是平衡的AVL树中插入一个新节点，可能造成不平衡，此时必须调整树的结构，使之平衡化。根据节点插入位置的不同，AVL树的旋转分为四种：

1. 新节点插入较高右子树的右侧---右右：左单旋

上面这个图是我们的抽象图，a/b/c分别是高度为h的AVL子树，我们来画一下具象图方便理解。

所以现在我们就理解上面的抽象图了，我们可以发现一个规律，经过旋转之后的的树的高度恢复到插入之前树的高度了，所以此时我们不需要对上层的bf进行调整，当进行旋转之后，我们直接退出循环即可。

按照上面的图，我们就可以直接开始写我们的代码了。

void RotateL(Node* parent)
{
	Node* subR = parent->_right;
	Node* subRL = subR->_left;

	parent->_right = subRL;
	subR->_left = parent;
}

我们来看看此时的代码是否存在问题，上面的写法虽然将我们的树进行左旋了，但是此时我们的树结构时三叉连，还存储了parent，所以我们这里需要更新一下每个节点parent。

void RotateL(Node* parent)
{
	Node* subR = parent->_right;
	Node* subRL = subR->_left;

	parent->_right = subRL;
	subRL->_parent = parent;

	subR->_left = parent;
	parent->_parent = subR;
}

我们再来看看我们的代码有没有什么问题呢？首先我们这里的parent和subR不可能为空，因为此时的平衡因子是2才进入了这个函数，但是这里的subRL为不为空我们就不清楚了，所以我们就需要对subRL不为空才执行parent的更新。

void RotateL(Node* parent)
{
	Node* subR = parent->_right;
	Node* subRL = subR->_left;

	parent->_right = subRL;
	if(subRL != nullptr)
		subRL->_parent = parent;

	subR->_left = parent;
	parent->_parent = subR;
}

此时我们的代码还有问题嘛？刚开始我们的根节点是parent，但是此时我们的根节点是subR，但是按照上面的程序，此时的subR的_parent依然指向parent，所以此时我们就要更新subR的_parent，如果传入的praent就是根节点，那么让subR变成我们的根节点，如果传入的是子树，那么还要与父节点进行链接，所以一开始我们就要保存parent的父节点ppnode，然后判断parent是ppnode的左还是右进行判断。

void RotateL(Node* parent)
{
	Node* ppnode = parent->_parent;
	Node* subR = parent->_right;
	Node* subRL = subR->_left;

	parent->_right = subRL;
	if(subRL != nullptr)
		subRL->_parent = parent;

	subR->_left = parent;
	parent->_parent = subR;

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

此时我们的程序还有问题嘛？有，我们还没有更新我们的平衡因子。

void RotateL(Node* parent)
{
	Node* ppnode = parent->_parent;
	Node* subR = parent->_right;
	Node* subRL = subR->_left;

	parent->_right = subRL;
	if(subRL != nullptr)
		subRL->_parent = parent;

	subR->_left = parent;
	parent->_parent = subR;

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

	//更新平衡因子
	parent->_bf = 0;
	subR->_bf = 0;
}

2.新节点插入较高左子树的左侧---左左：右单旋

有了上面的左单旋，我们这里的右单旋就很好写啦

//右单旋
void RotateR(Node* parent)
{
	Node* ppnode = parent->_parent;
	Node* subL = parent->_left;
	Node * subLR = subL->_right;

	parent->_left = subLR;
	if (subLR != nullptr)
		subLR->_parent = parent;

	subL->_right = parent;
	parent->_parent = subL;

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

	//更新平衡因子
	parent->_bf = 0;
	subL->_bf = 0;
}

3. 新节点插入较高左子树的右侧---左右：先左单旋再右单旋

基于上面的情况，此时我们仅仅使用单旋是不能解决的，此时需将b拆成60+b子树+c子树，然后再先左单旋再右单旋解决。

此时我们再来画一下具象图理解一下。

通过上面的具象图我们就可以总结左右双旋的规则

//左右双旋
void RotateLR(Node* parent)
{
    RotateL(parent->_left);
    RotateL(parent);
}

其实对于这里的旋转其实比较简单，但是对于平衡因子的更新比较麻烦。

观察上面的图我们发现可以分为三种情况，区分这三种情况我们利用查看插入之前60的平衡因子进行判断.

//左右双旋
void RotateLR(Node* parent)
{
	//平衡因子调整 - 单旋会修改平衡因子
	//查看插入之后的平衡因子进行判断
	Node* subL = parent->_left;
	Node* subLR = subL->_right;
	int bf = subLR->_bf;

	RotateL(parent->_left);
	RotateR(parent);

	if (bf == -1)
	{
		subLR->_bf = 0;
		subL->_bf = 0;
		parent->_bf = 1;
	}
	else if(bf == 1)
	{
		subLR->_bf = 0;
		subL->_bf = -1;
		parent->_bf = 0;
	}
	else if (bf == 0)
	{
		subLR->_bf = 0;
		subL->_bf = 0;
		parent->_bf = 0;
	}
	else
	{
		assert(false);
	}
}

4. 新节点插入较高右子树的左侧---右左：先右单旋再左单旋

有了上面的左右双旋，这里的右左双旋就轻松多了，我们直接来看平衡因子的调整

根据上面的平衡因子的调整关系，我们就可以写我们的代码了。

//右左双旋
void RotateRL(Node* parent)
{
	Node* subR = parent->_right;
	Node* subRL = subR->_left;
	int bf = subRL->_bf;

	RotateR(parent->_right);
	RotateL(parent);

	if (bf == 1)
	{
		subRL->_bf = 0;
		subR->_bf = 0;
		parent->_bf = -1;
	}
	else if (bf == -1)
	{
		subRL->_bf = 0;
		subR->_bf = 1;
		parent->_bf = 0;
	}
	else if (bf == 0)
	{
		subRL->_bf = 0;
		subR->_bf = 0;
		parent->_bf = 0;
	}
	else
	{
		assert(false);
	}
}

总结：

假如以parent为根的子树不平衡，即parent的平衡因子为2或者-2，分以下情况考虑

1. parent的平衡因子为2，说明parent的右子树高，设parent的右子树的根为subR

当subR的平衡因子为1时，执行左单旋
当subR的平衡因子为-1时，执行右左双旋

2. parent的平衡因子为-2，说明parent的左子树高，设parent的左子树的根为subL

当subL的平衡因子为-1是，执行右单旋
当subL的平衡因子为1时，执行左右双旋

旋转完成后，原pParent为根的子树个高度降低，已经平衡，不需要再向上更新。

template<class K, class V>
class AVLTree
{
	typedef AVLTreeNode<K, V> Node;
public:
	bool Insert(const pair<K, V>& kv)
	{
		//1. 先按照二叉搜索树的规则将节点插入到AVL树中
		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->_right;
			}
			else if (cur->_kv.first > kv.first)
			{
				parent = cur;
				cur = cur->_left;
			}
			else
			{
				//如果要插入的值和当前值相等，那就不能插入了
				return false;
			}
		}
		//此时_cur为空
		cur = new Node(kv);
		if (parent->_kv.first < kv.first)//要插入的值比当前值大
		{
			parent->_right = cur;
		}
		else//要插入的值比当前值小
		{
			parent->_left = cur;
		}
		cur->_parent = parent;
		//2. 新节点插入后，AVL树的平衡性可能会遭到破坏，此时就需要更新平衡因子，并检测是否\
			破坏了AVL树的平衡性
		while (parent)
		{
			// 更新双亲的平衡因子
			if (parent->_left == cur)
			{
				parent->_bf--;
			}
			else
			{
				parent->_bf++;
			}
			// 更新后检测双亲的平衡因子
			if (parent->_bf == 0)//满足AVL树的性质
			{
				break;
			}
			else if(parent->_bf == -1 || parent->_bf == 1)
			{
				// 插入前双亲的平衡因子是0，插入后双亲的平衡因为为1 或者 -1 ，
				// 说明以双亲为根的二叉树的高度增加了一层，因此需要继续向上调整
				cur = cur->_parent;
				parent = parent->_parent;
			}
			else if (parent->_bf == -2 || parent->_bf == 2)
			{
				//双亲的平衡因子为正负2，违反了AVL树的平衡性，
				// 需要对以pParent为根的树进行旋转处理
				if (parent->_bf == 2 && cur->_bf == 1)//左单旋
				{
					RotateL(parent);
				}
				else if (parent->_bf == -2 && cur->_bf == -1)//右单旋
				{
					RotateR(parent);
				}
				else if (parent->_bf == -2 && cur->_bf == 1)//左右双旋
				{
					RotateLR(parent);
				}
				else
				{
					RotateRL(parent);
				}
				break;
			}
			else
			{
				//插入之前AVL树就存在问题
				assert(false);
			}
		}
		return true;
	}
private: 
	Node* _root = nullptr;
};

2.5 AVL树的验证

AVL树是在二叉搜索树的基础上加入了平衡性的限制，因此要验证AVL树，可以分两步：

验证其为二叉搜索树，如果中序遍历可得到一个有序的序列，就说明为二叉搜索树

所以我们可以再写一个中序遍历的代码来验证是否有序。

void _InOder(Node* root)
{
	if (root == nullptr)
		return;
	_InOder(root->_left);
	cout << root->_kv.first << " ";
	_InOder(root->_right);
}

void InOder()
{
	_InOder(_root);
}

再来写一个测试的代码

void TestAVLTree1()
{
	int a[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };
	AVLTree<int,int> t;
	for (auto e : a)
	{
		t.Insert(make_pair(e,e));
	}
	t.InOder();
}

运行结果：

从运行结果来看，此时我们的程序是有序的，说明此时的树是搜索二叉树，但是此时的树不一定是AVL树，因为有序只是AVL树的特点之一，而且此时我们还不知道树的形状，不能根据平衡因子判定是否是AVL树，这里我们可以通过监视窗口先看根节点是谁，然后再看左子树和右子树，然后根据一层一层的看，画出相应的树然后判断是不是AVL树，但是比较麻烦，我们这里能不能通过在中序遍历的时候同时打印出平衡因子去查看呢？

这里其实是不能的，因为这里的bf是靠我们自己的代码控制的，有可能我们的代码写错了导致bf暂时没有出现问题，从而导致我们对数进行错误判断成了AVL树。验证其为平衡树我们是求出左子树和右子树的高度，如节点子树高度差的绝对值不超过1，那么该树就是AVL树，并且此时我们还能检查一下我们的平衡因子的正确性。

int Height(Node* root)
{
	if (root == nullptr)
		return 0;
	int leftHeight = Height(root->_left);//求左子树高度
	int rightHeight = Height(root->_right);//求右子树高度
		
	//返回左右子树高的那个高度 + 根节点
	return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
}

bool _IsBalance(Node* root)
{
	//root节点判断
	if(root == nullptr)
		return true;
	int leftHeight = Height(root->_left);//求左子树高度
	int rightHeight = Height(root->_right);//求右子树高度
	if (abs(rightHeight - leftHeight >= 2))
	{
		//高度差异常
		return false;
	}
	if (rightHeight - leftHeight != root->_bf)
	{
		//平衡因子异常
		return false;
	}
	//root节点无异常
	//再判断root->_left和root->_right
	//如果左右子树都符合，那么此时就是AVL树
	return _IsBalance(root->_left) && _IsBalance(root->_right);
}

bool IsBalance()
{
	return _IsBalance(_root);
}

然后我们再来测试一下

void TestAVLTree1()
{
	int a[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };
	AVLTree<int,int> t;
	for (auto e : a)
	{
		t.Insert(make_pair(e,e));
	}
	t.InOder();
	if (t.IsBalance())
	{
		cout << "当前树是AVL树！" << endl;
	}
	else
	{
		cout << "当前树非AVL树！" << endl;
	}
}

我们上面的代码有没有优化的空间呢？我们先来看一下上面的代码的缺陷，我们上面在root验证AVL树的时候，先是需要求出左树root->left和右树root->right的高度，然后再判断当前节点root是否满足AVL树的特点，由于我们求解高度是采用递归的写法，在求解左树root->left高度之前我们还需要求解左树的root->left->left左子树和root->left->right右子树高度，然后在我们判断root->left左树是否满足AVL树的特征时，我们又要再去递归求出root->left->left左子树和root->left->right右子树高度，这样就出现了大量的重复计算，其实我们上面的写法是按照前序遍历的思路来写的，这样写就会很亏。如果我们按照后序遍历的思路来写呢？

bool _IsBalance(Node* root)
{
	if (root == nullptr)
		return true;

	// 如果左右子树有一个不符合AVL，就不是AVL树
	if (!_IsBalance(root->_left) || !_IsBalance(root->_right))
	{
		return false;
	}

	int leftHeight = Height(root->_left);//求左子树高度
	int rightHeight = Height(root->_right);//求右子树高度

	if (abs(rightHeight - leftHeight >= 2))
	{
		//高度差异常
		return false;
	}
	if (rightHeight - leftHeight != root->_bf)
	{
		//平衡因子异常
		return false;
	}
	return true;
}

但是其实效率并没有提高，该重复计算的依然重复计算，只不过和前序颠倒了一下顺序，我们要清楚我们这里的出现的问题是在计算高度的时候出现了重复计算，这源自于递归的写法，所以我们可以不使用上面的递归的写法，换另一种思路去解决，我们依然使用后序遍历的思路，然后本层判断完，带回本层的树高度大的+1给上一层，上层就能直接求得本层的高度了。

bool _IsBalance(Node* root,int& height)
{
	if (root == nullptr)
	{
		height = 0;
		return true;
	}
			
	int leftHeight = 0;
	int rightHeight = 0;

	// 如果左右子树有一个不符合AVL，就不是AVL树
	if (!_IsBalance(root->_left,leftHeight) 
        || !_IsBalance(root->_right,rightHeight))
	{
		return false;
	}

	if (abs(rightHeight - leftHeight >= 2))
	{
		//高度差异常
		return false;
	}
	if (rightHeight - leftHeight != root->_bf)
	{
		//平衡因子异常
		return false;
	}

	height = leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;

	return true;
}

bool IsBalance()
{
	int height = 0;
	return _IsBalance(_root,height);
}

我们来画一下递归图来理解一下

此时我们的来运行一下测试代码

如果未来我们不小心在写错了一个平衡因子的更新呢？我们该怎么测试呢？比如我们故意注释掉右左双旋的平衡因子更新，看看程序此时会出现什么问题？

void TestAVLTree1()
{
	int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };
	AVLTree<int,int> t;
	for (auto e : a)
	{
		t.Insert(make_pair(e,e));
	}
	t.InOder();
	if (t.IsBalance())
	{
		cout << "当前树是AVL树！" << endl;
	}
	else
	{
		cout << "当前树非AVL树！" << endl;
	}
}

看看运行结果：

此时这颗树就不是AVL树了，但是我们不知道原因呀！我们可以在出问题的地方加一些打印信息！

此时我们再来看看输出结果。

此时上面显示的是6平衡因子异常，那我们就能断定是插入6影响了当前AVL树的结构嘛，这里是不能的，因为有可能原本插入6都是满足的，插入下一个值导致元素6左旋或者右旋不满足AVL树的结构了，所以我们可以在每插入一个值后进行一次AVL判断。

void TestAVLTree1()
{
	int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };
	AVLTree<int,int> t;
	for (auto e : a)
	{
		t.Insert(make_pair(e,e));
		cout << e << " " << t.IsBalance() << endl;
	} 
	t.InOder();
	if (t.IsBalance())
	{
		cout << "当前树是AVL树！" << endl;
	}
	else
	{
		cout << "当前树非AVL树！" << endl;
	}
}

此时我们再来测试一下

此时我们可以看出是插入14的时候出现了问题，此时教你们一招，能让我们快速定位到问题点。

然后我们根据监视窗口画出插入14之前的AVL树。

总结：

1、先看是插入谁导致出现的问题
2、打条件断点r画出插入前的树
3、单步跟踪，对比图一分析细节原因

不知道有没有仔细观看，我们上面的测试的时候更换了一组测试用例，原因是第一组的数据没有触发双旋的场景，所以我们更换了一组测试数据，所以建议用随机值来测试上面的程序。

void TestAVLTree2()
{
	const int N = 1000;
	vector<int> v;
	v.reserve(N);
	srand(time(0));

	for (size_t i = 0; i < N; i++)
	{
		v.push_back(rand() + i);
		//cout << v.back() << endl;
	}
	AVLTree<int, int> t;
	for (auto e : v)
	{
		t.Insert(make_pair(e, e));
		//cout << "Insert:" << e << "->" << t.IsBalance() << endl;
	}
	if (t.IsBalance())
	{
		cout << "当前树是AVL树！" << endl;
	}
	else
	{
		cout << "当前树非AVL树！" << endl;
	}
}

我们再来测试一下AVL树的其他性能，比如树的查找效率，插入效率，树的高度大小和节点个数

int _Height(Node* root)
{
	if (root == nullptr)
		return 0;
	int leftHeight = _Height(root->_left);//求左子树高度
	int rightHeight = _Height(root->_right);//求右子树高度
		
	//返回左右子树高的那个高度 + 根节点
	return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
}

int Height()
{
	return _Height(_root);
}

size_t Size()
{
	return _Size(_root);
}

size_t _Size(Node* root)
{
	if (root == NULL)
		return 0;

	return _Size(root->_left)
		+ _Size(root->_right) + 1;
}

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

然后我们来测试一下

void TestAVLTree3()
{
	const int N = 1000000;
	vector<int> v;
	v.reserve(N);
	srand(time(0));

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

	size_t begin2 = clock();
	AVLTree<int, int> t;
	for (auto e : v)
	{
		t.Insert(make_pair(e, e));
		//cout << "Insert:" << e << "->" << t.IsBalance() << endl;
	}
	size_t end2 = clock();

	cout << "Insert:" << end2 - begin2 << endl;

	if (t.IsBalance())
	{
		cout << "当前树是AVL树！" << endl;
	}
	else
	{
		cout << "当前树非AVL树！" << endl;
	}

	cout << "Height:" << t.Height() << endl;
	cout << "Size:" << t.Size() << endl;

	size_t begin1 = clock();
	// 确定在的值
	for (auto e : v)
	{
		t.Find(e);
	}

	// 随机值
	for (size_t i = 0; i < N; i++)
	{
		t.Find((rand() + i));
	}

	size_t end1 = clock();

	cout << "Find:" << end1 - begin1 << endl;
}

我们来测试一下结果

我们上面的代码不是产生了十万个节点嘛，为什么这里的size大小是635238，因为我们的插入逻辑是如果值相等就不插入了，而我们产生了十万个节点当然存在重复值，所以我们这里节点个数才会少一点，我们上面查找的时候，先查找了树中的每一个值，然后再随机产生了十万个值进行查找，显示结果是仅仅查找了19毫秒，说明我们这里的查找效率极高，我们可以看到这里的插入稍稍慢一点，这里稍微差一点并不是在查找要插入位置的消耗上，而是在创建节点的消耗了大量时间。

2.6 AVL树的删除(了解)

因为AVL树也是二叉搜索树，可按照二叉搜索树的方式将节点删除，然后再更新平衡因子，只不错与删除不同的时，删除节点后的平衡因子更新，最差情况下一直要调整到根节点的位置。

2.7 AVL树的性能

AVL树是一棵绝对平衡的二叉搜索树，其要求每个节点的左右子树高度差的绝对值都不超过1，这样可以保证查询时高效的时间复杂度，即$log_2 (N)$。但是如果要对AVL树做一些结构修改的操作，性能非常低下，比如：插入时要维护其绝对平衡，旋转的次数比较多，更差的是在删除时，有可能一直要让旋转持续到根的位置。因此：如果需要一种查询高效且有序的数据结构，而且数据的个数为静态的(即不会改变)，可以考虑AVL树，但一个结构经常修改，就不太适合。

3.红黑树

3.1 红黑树的概念

红黑树，是一种二叉搜索树，但在每个结点上增加一个存储位表示结点的颜色，可以是Red或 Black。通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路径会比其他路径长出两倍（假设最短路径是h，最长路径是2h，其他路径就是介于[h,2h]之间），因而是接近平衡的。

3.2 红黑树的性质

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

思考：为什么满足上面的性质，红黑树就能保证：其最长路径中节点个数不会超过最短路径节点个数的两倍？这里我们可以用极端场景分析，根据上面的性质，最短路径无非就是全黑，最长路径就是一黑一红搭配，此时最差情况下最长路径中节点个数才是最短路径节点个数的两倍。对比AVL树，高度很是接近logN，对于红黑树，高度接近2*logN，所以红黑树的搜索效率相对比AVL树差一点，但是几乎可以忽略不计，因为logN足够小，差距很小，但是插入同样的数据，AVL树高度更低，是通过更多旋转得到的。

注意：这里的路径是根走到空节点，而不是叶子节点。

3.3 红黑树节点的定义

// 节点的颜色
enum Colour
{
	RED,
	BLACK
};

// 红黑树节点的定义
template<class K, class V>
struct RBTreeNode
{
	RBTreeNode<K, V>* _left;
	RBTreeNode<K, V>* _right;
	RBTreeNode<K, V>* _parent;
	pair<K, V> _kv;
	Colour _col;

	RBTreeNode(const pair<K, V>& kv)
		:_left(nullptr)
		,_right(nullptr)
		,_parent(nullptr)
		,_kv(kv)
		,_col(RED)
	{}
};

思考：在节点的定义中，为什么要将节点的默认颜色给成红色的？这里我们可以想象一下，如果我们将插入的节点的默认颜色设置为黑色，那么该条路径上的黑色节点就会增加一个，为了满足对于每个结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数目的黑色结点，所以其他路径就必须增加要一个由红色变成黑色节点，但是有时候我们插入的节点没有红色节点，无法变色为黑色节点，就比如下面场景，插入一个值为1的黑色节点，此时就不满足红黑树的特点。

3.4 红黑树的插入操作

红黑树是在二叉搜索树的基础上加上其平衡限制条件，因此红黑树的插入可分为两步：

1. 按照二叉搜索的树规则插入新节点
2. 检测新节点插入后，红黑树的性质是否造到破坏

因为新节点的默认颜色是红色，因此：如果其双亲节点的颜色是黑色，没有违反红黑树任何性质，则不需要调整；但当新插入节点的双亲节点颜色为红色时，就违反了性质三不能有连在一起的红色节点，此时需要对红黑树分情况来讨论：

约定:cur为当前节点，p为父节点，g为祖父节点，u为叔叔节点

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

p/u是g的左或者右都不影响，cur是p的左或者右也不影响，处理的方式都是一样的。

上面的抽象图我们还不是很理解，我们这里来画一下具象图来好好好理解一下。

a/b/c/d/e都为空树情况：

a/b的位置是红色的，而c/d/e都是具有一一个黑色节点的红黑树(子树)的情况：

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

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

我们来画一下上面的具象图

u存在且为黑的时候再插入一个节点的时候，我们会发现此时的已经违背规则了，此时红黑树有一条路径会比其他路径长出两倍，此时只能通过旋转解决。

解决方式：p为g的左孩子，cur为p的左孩子，则进行右单旋转；相反， p为g的右孩子，cur为p的右孩子，则进行左单旋转 p、g变色--p变黑，g变红

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

我们来画一下上面的具象图

此时解决就需要双旋来解决

解决方式：p为g的左孩子，cur为p的右孩子，则针对p做左单旋转再对g做右单旋转；相反， p为g的右孩子，cur为p的左孩子，则针对p做右单旋转再对g做左单旋转。

template<class K, class V>
class RBTree
{
	typedef RBTreeNode<K, V> Node;
public:
	bool Insert(const pair<K, V>& kv)
	{
		//1. 先按照二叉搜索树的规则将节点插入到AVL树中
		if (_root == nullptr)
		{
			//第一个值直接插入
			//如果是_root，颜色给成黑色
			_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为空
		cur = new Node(kv);//默认新增节点是红色
		//此处可以不用写cur->_col = RED;因为构造函数处已经控制好了
		if (parent->_kv.first < kv.first)//要插入的值比当前值大
		{
			parent->_right = cur;
		}
		else//要插入的值比当前值小
		{
			parent->_left = cur;
		}
		cur->_parent = parent;

		//如果parent的颜色是红色进入循环，否则直接退出
		while (parent && parent->_col == RED)
		{
			//这里不需要判断grandfather是存在
			//进入循环时cur为插入的时候此时树一定是红黑树
			//插入cur后，cur为红，parent为红，此时parent不可能为根
			//那么grandfather一定存在且为黑
			Node* grandfather = parent->_parent;
			if (parent == grandfather->_left)//父亲是爷爷的左边
			{
				Node* uncle = grandfather->_right;
				//叔叔存在且为红
				if (uncle && uncle->_col == RED)
				{
					//父亲和叔叔都变黑，爷爷变红
					parent->_col = BLACK;
					uncle->_col = BLACK;
					grandfather->_col = RED;

					//继续往上处理
					cur = grandfather;
					parent = cur->_parent;
				}
				//叔叔存在且为黑或者叔叔不存在
				else
				{
					/*
								g				p
							p		u  ==>  c		g
						c								u
					*/
					//右单旋 + 变色
					if(cur == parent->_left)
					{
						RotateR(grandfather);
						parent->_col = BLACK;
						grandfather->_col = RED;
					}
					
					/*
							g					g				c
						p		u  ==>		c		u ==>	p		g
							c			p								u
					*/
					//p为旋转点进行左单旋，g为旋转点进行右单旋
					else
					{
						RotateL(parent);
						RotateR(grandfather);
						cur->_col = BLACK;
						grandfather->_col = RED;
					}
					//此时parent为红色，不能退出循环，需要手动退出
					break;
				}
			}
			else
			{
				Node* uncle = grandfather->_left;
				//叔叔存在且为红
				if (uncle && uncle->_col == RED)
				{
					//父亲和叔叔都变黑，爷爷变红
					parent->_col = BLACK;
					uncle->_col = BLACK;
					grandfather->_col = RED;

					//继续往上处理
					cur = grandfather;
					parent = cur->_parent;
				}
				else
				{
					/*
							g						p
						u		p      ==>		g		c
									c		u
					*/
					//左单旋 + 变色
					if(cur == parent->_right)
					{
						RotateL(grandfather);
						parent->_col = BLACK;
						grandfather->_col = RED;
					}

					/*
							g				g						c
						u		p  ==>  u		c      ==>		g		p
							c						p		u
					*/
					//右单旋 + 左单旋 + 变色
					else
					{
						RotateR(parent);
						RotateL(grandfather);
						cur->_col = BLACK;
						grandfather->_col = RED;
					}
					break;
				}
			}
		}
		_root->_col = BLACK;
		return true;
	}

	//左单旋
	void RotateL(Node* parent)
	{
		Node* ppnode = parent->_parent;
		Node* subR = parent->_right;
		Node* subRL = subR->_left;

		parent->_right = subRL;
		if (subRL != nullptr)
			subRL->_parent = parent;

		subR->_left = parent;
		parent->_parent = subR;

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

	//右单旋
	void RotateR(Node* parent)
	{
		Node* ppnode = parent->_parent;
		Node* subL = parent->_left;
		Node* subLR = subL->_right;

		parent->_left = subLR;
		if (subLR != nullptr)
			subLR->_parent = parent;

		subL->_right = parent;
		parent->_parent = subL;

		if (parent == _root)
		{
			_root = subL;
			subL->_parent = nullptr;
		}
		else
		{
			if (ppnode->_left == parent)
			{
				ppnode->_left = subL;
			}
			else
			{
				ppnode->_right = subL;
			}
			subL->_parent = ppnode;
		}
	}
private:
	Node* _root = nullptr;
};

3.5 红黑树的验证

红黑树的检测分为两步：

1. 检测其是否满足二叉搜索树(中序遍历是否为有序序列)
2. 检测其是否满足红黑树的性质

当我们要检查是否满足红黑树的性质的时候，我们能不能直接求出最短路径和最长路径，然后判断有没有超过2倍来判断一棵树是否是红黑树呢？我们来看下这种图

我们可以看到上面的红黑树是是满足最长路径的长度是不超过最短路径长度的2倍，但是上面的树依然违背了红黑树的性质，不满足每条路径上的黑色节点个数相同，所以我们就不能利用上面的规则判断一颗红黑树。其实我们能发现如果一棵树满足红黑树颜色的规则，那么就能保证最长路径的长度是不超过最短路径长度的2倍，所以我们根本不需要上面的规则，直接判断颜色是否符合即可。

1.根是黑色的
2.没有连续的红色节点
3.每条路径上的黑色节点的数量相等

首先我们来解决第一条性质：根是黑色的

bool IsBalance()
{
	if (_root && _root->_col == RED)
	{
		cout << "违反红黑树性质二：根节点必须为黑色" << endl;
		return false;
	}
	return Check(_root);
}

再来解决第二条性质：没有连续的红色节点

bool Check(Node* root)
{
	//空树也是红黑树
	if (root == nullptr)
		return true;

	//红色节点一定有父亲，所以这里不需要判空
	if (root->_col == RED && root->_parent->_col == RED)
	{
		cout << "违反性质三：不在一起的红色节点" << endl;
		return false;
	}
	return Check(root->_left)
		&& Check(root->_right);
}

我们这里是使用的前序遍历，如果当前节点和父亲节点都是红色，那么这里就违反规则。

再来解决第三条性质：每条路径上的黑色节点的数量相等

先来看第一种思路，来一个全局遍历path记录每条路径上的黑色节点的个数，再来一个vector去存储每条路径上的黑色节点的个数，然后遍历vector的所有元素是不是相同的

int path;//全局变量
vector<int> v;//存储每条路径的黑色节点的个数
void _CountBlack(Node* root)
{
	if (root == nullptr)
	{
		v.push_back(path);
		return;
	}

	if (root->_col == BLACK)
	{
		path++;
	}
	_CountBlack(root->_left);
	_CountBlack(root->_right);
	//恢复现场
	if (root->_col == BLACK )
	{
		path--;
	}	
}

void CountBlack()
{
	_CountBlack(_root);
	for (auto e : v)
	{
		cout << e << " ";
	}
	cout << endl;
	v.resize(0);
	path = 0;
}

我们可以来一组数据测试上面的性质3

void TestRBTree1()
{
	int a[] = { 13, 8, 17,1,11,15,25,6,22,27 };
	RBTree<int, int> t;
	for (auto e : a)
	{
		t.Insert(make_pair(e, e));
	}
	t.InOder(); cout << endl;
	t.CountBlack();
	t.CountBlack();
}

代码的运行结果：

根据上面的代码所构建的红黑树，我们发现节点数量是符合的。

由于我们这里使用的全局变量，为了下次的调用，需要每次将path和vector清空，这样才不会影响下次调用。但是上面全局变量最好不要用，它会影响我们的线程安全，所以我们这里换一种思路，先随便求一条路径的黑色节点的个数作为基准值，利用前序递归求出每条路径的黑色节点的个数，我们这里可以直接将每层的黑色节点传参，待它返回上一层自动清理现场，就不需要单独处理了，当节点为空的时候，就可以直接比较黑色节点个数和我们基准值是否相同。

bool Check(Node* cur, int blackNum, int refBlackNum)
{
	//空树也是红黑树
	if (cur == nullptr)
	{
		if (refBlackNum != blackNum)
		{
			cout << "违反性质四：每条路径中黑色节点的个数必须相同" << endl;
			return false;
		}

		//cout << blackNum << endl;
		return true;
	}
	//红色节点一定有父亲，所以这里不需要判空
	if (cur->_col == RED && cur->_parent->_col == RED)
	{
		cout << "违反红黑树性质二：根节点必须为黑色" << endl;
		return false;
	}

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

	return Check(cur->_left, blackNum, refBlackNum)
		&& Check(cur->_right, blackNum, refBlackNum);
}

bool IsBalance()
{
	if (_root && _root->_col == RED)
	{
		cout << "违反红黑树性质二：根节点必须为黑色" << endl;
		return false;
	}
			
	int refBlackNum = 0;//基准值
	Node* cur = _root;
	while (cur)
	{
		if (cur->_col == BLACK)
			refBlackNum++;

		cur = cur->_left;
	}

	return Check(_root, 0, refBlackNum);
}

然后我们来测试一下

void TestRBTree1()
{
	int a[] = { 13,8,17,1,11,15,25,6,22,27 };
	RBTree<int, int> t;
	for (auto e : a)
	{
		t.Insert(make_pair(e, e));
	}
	t.InOder();

	if (t.IsBalance())
	{
		cout << "当前树是红黑树！" << endl;
	}
	else
	{
		cout << "当前树非红黑树！" << endl;
	}
}

为了观看每个节点的颜色是否符合上面的红黑树图，我们中序遍历的时候输出一下节点的颜色

void _InOder(Node* root)
{
	if (root == nullptr)
		return;
	_InOder(root->_left);
	cout << root->_kv.first << ":" <<root->_col << endl;
	_InOder(root->_right);
}

void InOder()
{
	_InOder(_root);
}

现在我们再来测试一下

首先中序遍历为有序，然后我们中序还打印了节点的颜色，并且符合我们下面的红黑树。

然后我们再来测试一下其他功能

size_t Size()
{
	return _Size(_root);
}

size_t _Size(Node* root)
{
	if (root == NULL)
		return 0;

	return _Size(root->_left)
		+ _Size(root->_right) + 1;
}

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

int _Height(Node* root)
{
	if (root == nullptr)
		return 0;

	int leftHeight = _Height(root->_left);
	int rightHeight = _Height(root->_right);

	return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
}

int Height()
{
	return _Height(_root);
}

来一个测试代码

void TestRBLTree2()
{
	const int N = 1000000;
	vector<int> v;
	v.reserve(N);
	srand(time(0));

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

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

	cout << "Insert:" << end2 - begin2 << endl;

	if (t.IsBalance())
	{
		cout << "当前树是红黑树！" << endl;
	}
	else
	{
		cout << "当前树非红黑树！" << endl;
	}

	cout << "Height:" << t.Height() << endl;
	cout << "Size:" << t.Size() << endl;

	size_t begin1 = clock();
	// 确定在的值
	for (auto e : v)
	{
		t.Find(e);
	}

	// 随机值
	for (size_t i = 0; i < N; i++)
	{
		t.Find((rand() + i));
	}

	size_t end1 = clock();

	cout << "Find:" << end1 - begin1 << endl;
}

再来看一下效果

此时的树的高度稍微比AVL树高一点，这也符合我们之前的结论。

3.6 红黑树的删除

红黑树的删除本节不做讲解，有兴趣的同学可参考：《算法导论》或者《STL源码剖析》

红黑树 - _Never_ - 博客园 (cnblogs.com)

3.7 红黑树与AVL树的比较

我们这里来测试一下一百万个随机值的结果

红黑树和AVL树都是高效的平衡二叉树，增删改查的时间复杂度都是O($log_2 N$)，红黑树不追求绝对平衡，其只需保证最长路径不超过最短路径的2倍，相对而言，降低了插入和旋转的次数，所以在经常进行增删的结构中性能比AVL树更优，而且红黑树实现比较简单，所以实际运用中红黑树更多。

4.红黑树模拟实现STL中的map和set

4.1 初建map和set的框架

为了同时支持map和set都能够使用红黑树作为底层实现原理，所以我们这里需要给上模板去实现不同的容器set和map，所以我们这里的实现比较的大小的逻辑就要修改，对于set可以直接比较，但是对于map的pair虽然支持比较，但是我们期望比较的是first，对于second不需要参与比较，所以我们这里就单独写一个仿函数，获取要比较的元素。

所以我们的红黑树结点的定义和插入逻辑的代码需要修改一下。

template<class T>
struct RBTreeNode
{
	RBTreeNode<T>* _left;
	RBTreeNode<T>* _right;
	RBTreeNode<T>* _parent;
	Colour _col;
	T _data;

	RBTreeNode(const T& data)
		:_left(nullptr)
		,_right(nullptr)
		,_parent(nullptr)
		,_col(RED)
		, _data(data)
	{}
};

// set->RBTree<K, K, SetKeyOfT>
// map->RBTree<K, pair<K,T>, MapKeyOfT>
//KeyOfT >仿函数，取出T对象中的key
template<class K, class T, class KeyOfT>
class RBTree
{
	typedef RBTreeNode<T> Node;
public:
	bool Insert(const T& data)
	{
		//1. 先按照二叉搜索树的规则将节点插入到AVL树中
		if (_root == nullptr)
		{
			//第一个值直接插入
			//如果是_root，颜色给成黑色
			_root = new Node(data);
			_root->_col = BLACK;
			return true;
		}
		KeyOfT kot;
		Node* parent = nullptr;
		Node* cur = _root;
		while (cur)
		{
			//如果data是key，那可以直接比较
			//如果data是pair，期待的是first进行比较
			//pair是支持比较大小的，
			/*
				template <class T1, class T2>
				bool operator<  (const pair<T1,T2>& lhs, const pair<T1,T2>& rhs)
				{ return lhs.first<rhs.first || (!(rhs.first<lhs.first) && lhs.second<rhs.second); }
				比较规则是:first小就小，first不小，second小就小
				但是我们期望的只是用first进行比较，second不参与比较
				需要仿函数解决
			*/

			if (kot(cur->_data) < kot(data))//取出要比较的元素
			{
				parent = cur;
				cur = cur->_right;
			}
			else if (kot(cur->_data) > kot(data))
			{
				parent = cur;
				cur = cur->_left;
			}
			else
			{
				//如果要插入的值和当前值相等，那就不能插入了
				return false;
			}
		}
		//此时_cur为空
		cur = new Node(data);//默认新增节点是红色
		//此处可以不用写cur->_col = RED;因为构造函数处已经控制好了
		if (kot(parent->_data) < kot(data))//要插入的值比当前值大
		{
			parent->_right = cur;
		}
		else//要插入的值比当前值小
		{
			parent->_left = cur;
		}
		cur->_parent = parent;
        //其他代码不用修改，和之前一样
    }
private:
	Node* _root = nullptr;
};

我们发现我们上面好像只用了第二个模板参数，第一个模板参数好像根本就没有使用，那我们能不能不要第一个模板参数呢？后面迭代器讲解了我们再来解释。

4.2 红黑树的迭代器

迭代器的好处是可以方便遍历，是数据结构的底层实现与用户透明。如果想要给红黑树增加迭代器，需要考虑以前问题：

operator++和operator--

我们先来看一下我们这里迭代器++的逻辑如何控制，首先我们知道初始位置肯定是这棵树的最左节点，那么下一个节点该如何寻找呢？我们可以从对红黑树进行中序遍历后，可以得到一个有序的序列出发。

Self& operator++()
{
	if (_node->_right != nullptr)
	{
		//右子树的中序第一个(最左节点)
		Node* subLeft = _node->_right;
		while (subLeft->_left != nullptr)
		{
			subLeft = subLeft->_left;
		}
		_node = subLeft;
	}
	else
	{
		//右为空
		//祖先里面孩子是父亲左的那个节点
		Node* cur = _node;
		Node* parent = _node->_parent;
		while (parent && cur == parent->_right)
		{
			cur = parent;
			parent = parent->_parent;
		}
		_node = parent;
	}

	return *this;
}

我们这里的迭代器减减的逻辑和迭代器加加的逻辑完全相反，但是由于我们上面给的end()的位置是空，所以我们这里不能直接--end()，只能自己再写一个代码去找到最后一个元素的迭代器再去减减，或者也可以单独处理一下，但是如果此时为空树，我们需要再单独处理一下，就比较麻烦。

Self& operator--()
{
	//说明此时的位置是end()
	if (_node == nullptr)
	{
		//_node指向最后结点
		//唯一的问题就是空树，也指向空
	}

	//和++逻辑相反
	return *this;
}

库里面因为对end()位置的迭代器进行--操作，必须要能找最后一个元素，因此最好的方式是将end()放在头结点的右的位置，使用一个带哨兵位的结点，指向end()：

begin()与end()

STL明确规定，begin()与end()代表的是一段前闭后开的区间，而对红黑树进行中序遍历后，可以得到一个有序的序列，因此：begin()可以放在红黑树中最小节点(即最左侧节点)的位置，end()放在最大节点(最右侧节点)的下一个位置，关键是最大节点的下一个位置在哪块？我们这里先将end()设置为空，按照我们上面的迭代器++的逻辑，当访问到这棵树的最右节点，此时的树的当前结点cur始终都是parent的右，按照此时右为空的逻辑，那么最终parent就会走到空，cur就会走到根节点，此时_node也就为nullptr，刚好给end()构造为空。

typedef RBTreeIterator<T> iterator;

iterator begin()
{
	//找最左节点
	Node* subLeft = _root;
	while (subLeft != nullptr && subLeft->_left != nullptr)
	{
		subLeft = subLeft->_left;
	}
	return iterator(subLeft);//构造
}

iterator end()
{
	return iterator(nullptr);
}

我们再来完善一下迭代器的其他接口

template<class T>
struct RBTreeIterator
{
	typedef RBTreeNode<T> Node;
	typedef RBTreeIterator<T> Self;

	RBTreeIterator(Node* node)
		:_node(node)
	{}

	T& operator*()
	{
		return _node->_data;
	}

	T* operator->()
	{
		return &_node->_data;
	}

	Self& operator++()
	{
		if (_node->_right != nullptr)
		{
			//右子树的中序第一个(最左节点)
			Node* subLeft = _node->_right;
			while (subLeft->_left != nullptr)
			{
				subLeft = subLeft->_left;
			}
			_node = subLeft;
		}
		else
		{
			//右为空
			//祖先里面孩子是父亲左的那个节点
			Node* cur = _node;
			Node* parent = _node->_parent;
			while (parent && cur == parent->_right)
			{
				cur = parent;
				parent = parent->_parent;
			}
			_node = parent;
		}

		return *this;
	}

	bool operator!=(const Self& s)
	{
		return _node != s._node;
	}

private:
	Node* _node;
};

如果我们要实现const迭代器呢？只需要添加两个模板参数即可

template<class T,class Ptr,class Ref>
struct RBTreeIterator
{
	typedef RBTreeNode<T> Node;
	typedef RBTreeIterator<T,Ptr,Ref> Self;

	RBTreeIterator(Node* node)
		:_node(node)
	{}

	Ref operator*()
	{
		return _node->_data;
	}

	Ptr operator->()
	{
		return &_node->_data;
	}
private:
	Node* _node;
};

typedef RBTreeIterator<T,T*,T&> iterator;
typedef RBTreeIterator<T,const T*,const T&> const_iterator;

const_iterator begin() const
{
	//找最左节点
	Node* subLeft = _root;
	while (subLeft != nullptr && subLeft->_left != nullptr)
	{
		subLeft = subLeft->_left;
	}
	return const_iterator(subLeft);//构造
}

const_iterator end() const
{
	return const_iterator(nullptr);
}

4.3 完善set和map框架

#include "RBTree.h"

namespace yu
{
	template<class K>
	class set
	{
		struct SetKeyOfT
		{
			const K& operator()(const K& key)
			{
				return key;
			}
		};
	public:
		//typename告诉编译器这是一个类型，而不是一个静态成员变量
		typedef typename RBTree<K, K, SetKeyOfT>::iterator iterator;

		iterator begin()
		{
			return _t.begin();
		}

		iterator end()
		{
			return _t.end();
		}

		bool insert(const K& key)
		{
			return _t.Insert(key);
		}

	private:
		RBTree<K, K, SetKeyOfT> _t;
	};

	void test_set1()
	{
		set<int> s;
		int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };
		for (auto e : a)
		{
			s.insert(e);
		}
		set<int>::iterator it = s.begin();
		while (it != s.end())
		{
			cout << *it << " ";
			++it;
		}
	}
}

然后我们来测试一下结果，这里迭代器加加的逻辑是按照中序，因此有序即可判断。

此时符合我们的预期，那我们再来看下面的测试代码。

void test_set1()
{
	set<int> s;
	int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };
	for (auto e : a)
	{
		s.insert(e);
	}
	set<int>::iterator it = s.begin();
	while (it != s.end())
	{
		if (*it % 2 == 0)
			*it += 100;
		cout << *it << " ";
		++it;
	}
}

我们来看一下运行结果。

我们发现此时结果不是有序的，此时也不是我们的红黑树，这里的结点的值是不允许修改的，我们可以在迭代器里面的*操作符重载加上const修饰表示不可被修改，也可以通过传入模板第二个参数的时候传入const，此时const相当于间接*操作符重载加上const。

namespace yu
{
	template<class K>
	class set
	{
		struct SetKeyOfT
		{
			const K& operator()(const K& key)
			{
				return key;
			}
		};
	public:
		//typename告诉编译器这是一个类型，而不是一个静态成员变量
		typedef typename RBTree<K, const K, SetKeyOfT>::iterator iterator;

		iterator begin()
		{
			return _t.begin();
		}

		iterator end()
		{
			return _t.end();
		}

		bool insert(const K& key)
		{
			return _t.Insert(key);
		}

	private:
		RBTree<K, const K, SetKeyOfT> _t;
	};

	void test_set1()
	{
		set<int> s;
		int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };
		for (auto e : a)
		{
			s.insert(e);
		}
		set<int>::iterator it = s.begin();
		while (it != s.end())
		{
			if (*it % 2 == 0)
				*it += 100;
			cout << *it << " ";
			++it;
		}
	}
}

我们来看一下测试结果。

现在我们来解释一下第一个模板参数为什么需要的原因，第二个模板参数只能通过我们的仿函数获取到相应的key，并不能获取到这个key的类型，当我们需要find的时候就需要参数的类型，此时对于map和set所查找的都是key，类型都是相同的。

iterator find(const K& key)
{
	KeyOfT kot;
	Node* cur = _root;
	while (cur)
	{
		if (kot(cur->_data) < key)
		{
			cur = cur->_right;
		}
		else if (kot(cur->_data) > key)
		{
			cur = cur->_left;
		}
		else
		{
			return iterator(cur);
		}
	}
	return iterator(nullptr);
}

我们再来一下map的框架

#include "RBTree.h"

namespace yu
{
	template<class K, class V>
	class map
	{
		struct MapKeyOfT
		{
			const K& operator()(const pair<K,V>& kv)
			{
				return kv.first;
			}
		};
	public:
		//typename告诉编译器这是一个类型，而不是一个静态成员变量
		typedef typename RBTree<K, pair<const K, V>, MapKeyOfT>::iterator iterator;

		iterator begin()
		{
			return _t.begin();
		}

		iterator end()
		{
			return _t.end();
		}

		bool insert(const pair<K, V>& kv)
		{
			return _t.Insert(kv);
		}

		iterator find(const K& key)
		{
			return _t.Find(key)
		}
	private:
		RBTree<K, pair<const K,V>, MapKeyOfT> _t;
	};

	void test_map1()
	{
		map<int,int> m;
		int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };
		for (auto e : a)
		{
			m.insert(make_pair(e,e));
		}
		map<int,int>::iterator it = m.begin();
		while (it != m.end())
		{
			cout << it->first << ":" << it->second << " ";
			++it;
		}
	}
}

前面我们也学到过，map是支持operator[]操作的，所以我们这里还要实现一下，我们前面学习过operator[]，它是利用insert进行修改的，所以我们这里修改一下insert。

pair<iterator,bool> Insert(const T& data)
{
	//1. 先按照二叉搜索树的规则将节点插入到AVL树中
	if (_root == nullptr)
	{
		//第一个值直接插入
		//如果是_root，颜色给成黑色
		_root = new Node(data);
		_root->_col = BLACK;
		return return make_pair(iterator(_root),true);
	}
	KeyOfT kot;
	Node* parent = nullptr;
	Node* cur = _root;
	while (cur)
	{
		//如果data是key，那可以直接比较
		//如果data是pair，期待的是first进行比较
		//pair是支持比较大小的，
		/*
			template <class T1, class T2>
			bool operator<  (const pair<T1,T2>& lhs, const pair<T1,T2>& rhs)
			{ return lhs.first<rhs.first || (!(rhs.first<lhs.first) && lhs.second<rhs.second); }
			比较规则是:first小就小，first不小，second小就小
			但是我们期望的只是用first进行比较，second不参与比较
			需要仿函数解决
		*/

		if (kot(cur->_data) < kot(data))//取出要比较的元素
		{
			parent = cur;
			cur = cur->_right;
		}
		else if (kot(cur->_data) > kot(data))
		{
			parent = cur;
			cur = cur->_left;
		}
		else
		{
			//如果要插入的值和当前值相等，那就不能插入了
			//return false;
			return return make_pair(iterator(cur), false);
		}
	}
	//此时_cur为空
	cur = new Node(data);//默认新增节点是红色
	Node* temp = cur;
	//此处可以不用写cur->_col = RED;因为构造函数处已经控制好了
	if (kot(parent->_data) < kot(data))//要插入的值比当前值大
	{
		parent->_right = cur;
	}
	else//要插入的值比当前值小
	{
		parent->_left = cur;
	}
	cur->_parent = parent;

	//如果parent的颜色是红色进入循环，否则直接退出
	while (parent && parent->_col == RED)
	{
		//这里不需要判断grandfather是存在
		//进入循环时cur为插入的时候此时树一定是红黑树
		//插入cur后，cur为红，parent为红，此时parent不可能为根
		//那么grandfather一定存在且为黑
		Node* grandfather = parent->_parent;
		if (parent == grandfather->_left)//父亲是爷爷的左边
		{
			Node* uncle = grandfather->_right;
			//叔叔存在且为红
			if (uncle && uncle->_col == RED)
			{
				//父亲和叔叔都变黑，爷爷变红
				parent->_col = BLACK;
				uncle->_col = BLACK;
				grandfather->_col = RED;

				//继续往上处理
				cur = grandfather;
				parent = cur->_parent;
			}
			//叔叔存在且为黑或者叔叔不存在
			else
			{
				/*
							g				p
						p		u  ==>  c		g
					c								u
				*/
				//右单旋 + 变色
				if(cur == parent->_left)
				{
					RotateR(grandfather);
					parent->_col = BLACK;
					grandfather->_col = RED;
				}
					
				/*
						g					g				c
					p		u  ==>		c		u ==>	p		g
						c			p								u
				*/
				//p为旋转点进行左单旋，g为旋转点进行右单旋
				else
				{
					RotateL(parent);
					RotateR(grandfather);
					cur->_col = BLACK;
					grandfather->_col = RED;
				}
				//此时parent为红色，不能退出循环，需要手动退出
				break;
			}
		}
		else
		{
			Node* uncle = grandfather->_left;
			//叔叔存在且为红
			if (uncle && uncle->_col == RED)
			{
				//父亲和叔叔都变黑，爷爷变红
				parent->_col = BLACK;
				uncle->_col = BLACK;
				grandfather->_col = RED;

				//继续往上处理
				cur = grandfather;
				parent = cur->_parent;
			}
			else
			{
				/*
						g						p
					u		p      ==>		g		c
								c		u
				*/
				//左单旋 + 变色
				if(cur == parent->_right)
				{
					RotateL(grandfather);
					parent->_col = BLACK;
					grandfather->_col = RED;
				}

				/*
						g				g						c
					u		p  ==>  u		c      ==>		g		p
						c						p		u
				*/
				//右单旋 + 左单旋 + 变色
				else
				{
					RotateR(parent);
					RotateL(grandfather);
					cur->_col = BLACK;
					grandfather->_col = RED;
				}
				break;
			}
		}
	}
	_root->_col = BLACK;
	//return true;
	return make_pair(iterator(temp), true);
}

然后我们用代码测试一下

void test_map2()
{
	string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜",
   "苹果", "香蕉", "苹果", "香蕉" };
	map<string, int> countMap;
	for (auto& e : arr)
	{
		countMap[e]++;
	}
 
	for (auto& kv : countMap)
	{
		cout << kv.first << ":" << kv.second << endl;
	}
}

看一下测试的结果