【C++】AVL树/红黑树实现及map与set的封装-易微帮

在这里插入图片描述

前言
【C++】二叉树进阶（二叉搜索树）这篇文章讲述了关于二叉搜索树知识，但是二叉搜索树有其自身的缺陷，假如往树中插入的元素有序或者接近有序，二叉搜索树就会退化成单支树，时间复杂度会退化成O(N)，因此map、set等关联式容器的底层结构是对二叉树进行了平衡处理，即采用平衡树来实现，AVL树和红黑树都在不同程度下优化了二叉搜索树。在这篇文章中【C++】─篇文章带你熟练掌握 map 与 set 的使用我们对map与set的使用进行了详细的讲解，那么这篇文章会在实现AVL树的基础上对map与set进行封装。

一、AVL 树

1.1 AVL树的概念

二叉搜索树虽可以缩短查找的效率，但如果数据有序或接近有序二叉搜索树将退化为单支树，查
找元素相当于在顺序表中搜索元素，效率低下。因此，两位俄罗斯的数学家G.M.Adelson-Velskii
和E.M.Landis在1962年发明了一种解决上述问题的方法：当向二叉搜索树中插入新结点后，如果能保证每个结点的左右子树高度之差的绝对值不超过1(需要对树中的结点进行调整)，即可降低树的高度，从而减少平均搜索长度。

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

它或是它的左右子树都是AVL树
左右子树的高度差（平衡因子）的绝对值不超过1

在这里插入图片描述

如果一棵二叉搜索树是高度平衡的，它就是AVL树。如果它有n个结点，其高度可保持在 $O(log_2 n)$ ，搜索时间复杂度O( $log_2 n$ )

1.2 AVL树节点的定义

由于AVL树比红黑树稍逊一筹，后面set和map的封装不会使用AVL树，所以这里AVL树将会简单的进行编写。

template<class K, class V>
struct AVLTreeNode
{
	AVLTreeNode* _left;
	AVLTreeNode* _right;
	AVLTreeNode* _parent;

	pair<K, V> _kv;

	int _bf;  // 平衡因子

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

	}
};

1.3 AVL树的插入

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

找到新节点应该插入的位置进行链接(这里写的AVL树不允许插入相同的元素)
插入新节点后，若出现某棵树的平衡因子异常的情况，则需要进行调整

这里的左旋、右旋等在下面AVL树的旋转进行讲解

template<class K, class V>
class AVLTree
{
	typedef AVLTreeNode<K, V> Node;
public:
	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->_left;
			}
			else if (cur->_kv.first < kv.first)
			{
				parent = cur;
				cur = cur->_right;
			}
			// 有相同的K，插入失败
			else
			{
				return false;
			}
		}


		// 插入新节点
		cur = new Node(kv);

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

		// 平衡旋转
		while (parent)
		{
			if (parent->_left == cur)
			{
				parent->_bf--;
			}
			else
			{
				parent->_bf++;
			}

			// 如果当前树插入新节点后的平衡因子变为0
			// 那么说明新插入的节点并没有使当前树的高度增加
			// 更不会对当前节点到根节点路径上节点的平衡因子造成影响
			// 所以说这里break不需要继续处理
			if (parent->_bf == 0)
			{
				break;
			}
			// 当父节点的平衡因子为1/-1时，那么说明这个新插入的节点影响了父节点的高度
			// 也有可能影响新插入节点以上节点的平衡因子，向上判断该节点是否影响上面树的平衡性
			// 若影响上面树的平衡性，那么需要旋转来平衡树，使其平衡
			else if (parent->_bf == 1 || parent->_bf == -1)
			{
				if (parent == _root)
					break;
				cur = parent;
				parent = parent->_parent;
			}
			else if (parent->_bf == 2 || parent->_bf == -2)
			{
				// 右右高，左单旋
				if (parent->_bf == 2 && cur->_bf == 1)
				{
					RotateL(parent);
					break;
				}
				// 左左高，右单旋
				else if (parent->_bf == -2 && cur->_bf == -1)
				{
					RotateR(parent);
					break;
				}
				// 右左高，右左双旋，先将当前节点右单旋，再将父亲节点左单旋
				else if (parent->_bf == 2 && cur->_bf == -1)
				{
					RotateRL(parent);
					break;
				}
				// 左右高，左右双旋，先将当前节点左单旋，再将父亲节点右旋单旋
				else if (parent->_bf == -2 && cur->_bf == 1)
				{
					RotateLR(parent);
					break;
				}
				else
				{
					assert(false);
				}
			}
			// 当父亲节点的平衡因子为其他值时，那么这棵树一定是出现了问题
			else
			{
				assert(false);
			}
		}
		return true;
	}

private:
	Node* _root = nullptr;
};

1.4 AVL树的旋转

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

这里无论是在t1还是t2插入一个新节点都是右单旋，只有平衡因子的区别，这里介绍一下再t1的情况。

t1、t2和t3都是高度为 h（h>=0）的AVL树，首先在新节点未插入时，节点10的平衡因子为0，节点20的平衡因子为-1，此时所有树都满足AVL树的条件。当在t1上插入一个节点，就导致节点10的平衡因子为-1,节点20的平衡因子为-2，此时节点20为根的这颗数违反了AVL树的规则，需要进行选择调整。

首先，t2这颗树上的节点都是比20小、比10大的节点，使t2变为节点20的左，再将节点20变为节点10的右，就能够使整体树的高度与之前的一样，但是这里的树可能是一颗完整的树，也有可能是一颗子树，若是子树需要处理好旋转后与上面节点的连接问题，详细的如何连接大家可以看下面代码。

注意：当树进行旋转后，树中的某些节点的平衡因子会进行变化，所以大家在旋转后需要对节点的平衡因子做好调整。

在这里插入图片描述

template<class K, class V>
class AVLTree
{
	typedef AVLTreeNode<K, V> Node;
private:
	// 右单旋
	void RotateR(Node* parent)
	{
		Node* subL = parent->_left;
		Node* subLR = subL->_right;

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

		Node* Pparent = parent->_parent;
		subL->_right = parent;

		parent->_parent = subL;

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

		parent->_bf = subL->_bf = 0;
	}

	Node* _root = nullptr;
};

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

这里无论是在t2还是t3插入一个新节点都是左单旋，只有平衡因子的区别，这里介绍一下再t3的情况。

t1、t2和t3都是高度为 h（h>=0）的AVL树，首先在新节点未插入时，节点20的平衡因子为0，节点10的平衡因子为1，此时所有树都满足AVL树的条件。当在t3上插入一个节点，就导致节点20的平衡因子为1，节点10的平衡因子为2,此时节点20为根的这颗数违反了AVL树的规则，需要进行选择调整。

首先，t2这颗树上的节点都是比20小、比10大的节点，使t2变为节点10的右，再将节点10变为节点20的左，就能够使整体树的高度与之前的一样，但是这里的树可能是一颗完整的树，也有可能是一颗子树，若是子树需要处理好旋转后与上面节点的连接问题，详细的如何连接大家可以看下面代码。

注意：当树进行旋转后，树中的某些节点的平衡因子会进行变化，所以大家在旋转后需要对节点的平衡因子做好调整。
在这里插入图片描述

template<class K, class V>
class AVLTree
{
	typedef AVLTreeNode<K, V> Node;
private:
	// 左单旋
	void RotateL(Node* parent)
	{
		Node* subR = parent->_right;
		Node* subRL = subR->_left;

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

		Node* Pparent = parent->_parent;
		parent->_parent = subR;
		subR->_left = parent;

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

		parent->_bf = subR->_bf = 0;
	}

	Node* _root = nullptr;
};

1.4.3 新节点插入较高左子树的右侧—左右高：先左单旋再右单旋

这里无论是在t2还是t3插入一个新节点都是左右双旋，只有平衡因子的区别，所以这里只画了在插入t3插入的这种情况，插入t2的情况，大家可以自己下来试试。

t1、t4是高度为 h 的AVL树，t2和t3都是高度为 h-1（h>=1）的AVL树，首先在新节点未插入时，节点20的平衡因子为0，节点10的平衡因子为0，节点30的平衡因子为-1，此时所有树都满足AVL树的条件。当在t3上插入一个节点，就导致节点20的平衡因子为1，节点10的平衡因子为1，节点30的平衡因子为-2,此时节点30为根的这颗数违反了AVL树的规则，需要进行旋转调整。

当我们知道这里需要进行旋转调整，但是只有一边高的时候能够使用单旋，而这里是两边高，那么这里就将将这棵树处理为一边高就可以使用单旋了。

看下图，首先这里对节点10这棵树使用左单旋就可以使节点30的这棵树变为只有左左高，再对节点30这棵树进行右单旋，这么做能够使整体树的高度与之前的一样，但是这里的树可能是一颗完整的树，也有可能是一颗子树，若是子树需要处理好旋转后与上面节点的连接问题，详细的如何连接大家可以看下面代码。

注意：当树进行旋转后，树中的某些节点的平衡因子会进行变化，所以大家在旋转后需要对节点的平衡因子做好调整。
在这里插入图片描述

template<class K, class V>
class AVLTree
{
	typedef AVLTreeNode<K, V> Node;
private:
	// 左右双旋
	void RotateLR(Node* parent)
	{
		Node* subL = parent->_left;
		Node* subLR = subL->_right;
		int bf = subLR->_bf;

		RotateL(subL);
		RotateR(parent);

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

	Node* _root = nullptr;
};

1.4.4 新节点插入较高右子树的左侧—右左高：先右单旋再左单旋

这里无论是在t2还是t3插入一个新节点都是右左双旋，只有平衡因子的区别，所以这里只画了在插入t3插入的这种情况，插入t2的情况，大家可以自己下来试试。

t1、t4是高度为 h 的AVL树，t2和t3都是高度为 h-1（h>=1）的AVL树，首先在新节点未插入时，节点20的平衡因子为0，节点30的平衡因子为0，节点10的平衡因子为1，此时所有树都满足AVL树的条件。当在t3上插入一个节点，就导致节点20的平衡因子为1，节点30的平衡因子为-1,节点10的平衡因子为2,此时节点30为根的这颗数违反了AVL树的规则，需要进行旋转调整。

当我们知道这里需要进行旋转调整，但是只有一边高的时候能够使用单旋，而这里是两边高，那么这里就将将这棵树处理为一边高就可以使用单旋了。

看下图，首先这里对节点20这棵树使用右单旋就可以使节点10的这棵树变为只有右右高，再对节点10这棵树进行左单旋，这么做能够使整体树的高度与之前的一样，但是这里的树可能是一颗完整的树，也有可能是一颗子树，若是子树需要处理好旋转后与上面节点的连接问题，详细的如何连接大家可以看下面代码。

注意：当树进行旋转后，树中的某些节点的平衡因子会进行变化，所以大家在旋转后需要对节点的平衡因子做好调整。
在这里插入图片描述

template<class K, class V>
class AVLTree
{
	typedef AVLTreeNode<K, V> Node;
private:
	// 右左双旋
	void RotateRL(Node* parent)
	{
		Node* subR = parent->_right;
		Node* subRL = subR->_left;
		int bf = subRL->_bf;

		RotateR(subR);
		RotateL(parent);

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

	Node* _root = nullptr;
};

1.5 AVL树的验证

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

验证其为二叉搜索树
如果中序遍历可得到一个有序的序列，就说明为二叉搜索树
验证其为平衡树
(a) 每个节点子树高度差的绝对值不超过1(注意节点中如果没有平衡因子)
(b) 节点的平衡因子是否计算正确

在下面函数的实现中，大家可以发现都嵌套了一个函数，由于函数按照递归实现的，而递归的实现是需要根节点的，封装外是无法访问的根节点的，但是封装内是可以直接访问根节点的，所以嵌套了一层。

template<class K, class V>
class AVLTree
{
	typedef AVLTreeNode<K, V> Node;
public:
	// 中序变量
	void InOrder()
	{
		_InOrder(_root);
	}
	
	// 判断是否为AVL树
	bool IsBalance()
	{
		return _IsBalance(_root);
	}
	
	// 计算树的高度
	int Height()
	{
		return _Height(_root);
	}

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

		bool left = _IsBalance(root->_left);
		if (!left) return left;

		bool right = _IsBalance(root->_right);
		if (!right) return right;

		if (_Height(root->_right) - _Height(root->_left) != root->_bf)
			cout << root->_kv.first << ":" << "平衡因子异常" << endl;

		return left && right &&
			abs(_Height(root->_left) - _Height(root->_right) < 2);
	}

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

		int left = _Height(root->_left);
		int right = _Height(root->_right);

		return  left > right ? left + 1 : right + 1;
	}

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

		_InOrder(root->_left);

		cout << root->_kv.first << endl;
		_InOrder(root->_right);

	}

	Node* _root = nullptr;
};

1.6 AVL树的性能

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

1.7 AVL树的整体实现

#pragma once

#include <iostream>
#include <assert.h>
#include <vector>
#include <string>

using namespace std;

template<class K, class V>
struct AVLTreeNode
{
	AVLTreeNode* _left;
	AVLTreeNode* _right;
	AVLTreeNode* _parent;

	pair<K, V> _kv;

	int _bf;  // 平衡因子

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

template<class K, class V>
class AVLTree
{
	typedef AVLTreeNode<K, V> Node;
public:
	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->_left;
			}
			else if (cur->_kv.first < kv.first)
			{
				parent = cur;
				cur = cur->_right;
			}
			// 有相同的K，插入失败
			else
			{
				return false;
			}
		}

		// 插入新节点
		cur = new Node(kv);

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

		// 平衡旋转
		while (parent)
		{
			if (parent->_left == cur)
			{
				parent->_bf--;
			}
			else
			{
				parent->_bf++;
			}

			// 如果当前树插入新节点后的平衡因子变为0
			// 那么说明新插入的节点并没有使当前树的高度增加
			// 更不会对当前节点到根节点路径上节点的平衡因子造成影响
			// 所以说这里break不需要继续处理
			if (parent->_bf == 0)
			{
				break;
			}
			// 当父节点的平衡因子为1/-1时，那么说明这个新插入的节点影响了父节点的高度
			// 也有可能影响新插入节点以上节点的平衡因子，向上判断该节点是否影响上面树的平衡性
			// 若影响上面树的平衡性，那么需要旋转来平衡树，使其平衡
			else if (parent->_bf == 1 || parent->_bf == -1)
			{
				if (parent == _root)
					break;
				cur = parent;
				parent = parent->_parent;
			}
			else if (parent->_bf == 2 || parent->_bf == -2)
			{
				// 右右高，左单旋
				if (parent->_bf == 2 && cur->_bf == 1)
				{
					RotateL(parent);
					break;
				}
				// 左左高，右单旋
				else if (parent->_bf == -2 && cur->_bf == -1)
				{
					RotateR(parent);
					break;
				}
				// 右左高，右左双旋，先将当前节点右单旋，再将父亲节点左单旋
				else if (parent->_bf == 2 && cur->_bf == -1)
				{
					RotateRL(parent);
					break;
				}
				// 左右高，左右双旋，先将当前节点左单旋，再将父亲节点右旋单旋
				else if (parent->_bf == -2 && cur->_bf == 1)
				{
					RotateLR(parent);
					break;
				}
				else
				{
					assert(false);
				}
			}
			// 当父亲节点的平衡因子为其他值时，那么这棵树一定是出现了问题
			else
			{
				assert(false);
			}
		}
		return true;
	}

	void InOrder()
	{
		_InOrder(_root);
	}

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

		_InOrder(root->_left);

		cout << root->_kv.first << endl;
		_InOrder(root->_right);

	}

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

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

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

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

		bool left = _IsBalance(root->_left);
		if (!left) return left;

		bool right = _IsBalance(root->_right);
		if (!right) return right;

		if (_Height(root->_right) - _Height(root->_left) != root->_bf)
			cout << root->_kv.first << ":" << "平衡因子异常" << endl;

		return left && right &&
			abs(_Height(root->_left) - _Height(root->_right) < 2);
	}

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

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


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

		int left = _Height(root->_left);
		int right = _Height(root->_right);

		return  left > right ? left + 1 : right + 1;
	}

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

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

		Node* Pparent = parent->_parent;
		subL->_right = parent;

		parent->_parent = subL;

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

		parent->_bf = subL->_bf = 0;
	}

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

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

		Node* Pparent = parent->_parent;
		parent->_parent = subR;
		subR->_left = parent;

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

		parent->_bf = subR->_bf = 0;
	}

	// 左右双旋
	void RotateLR(Node* parent)
	{
		Node* subL = parent->_left;
		Node* subLR = subL->_right;
		int bf = subLR->_bf;

		RotateL(subL);
		RotateR(parent);

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

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

		RotateR(subR);
		RotateL(parent);

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

	Node* _root = nullptr;
};

二、红黑树

2.1 红黑树的概念

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

2.2 红黑树的性质

红黑树中的根节点必定为黑色节点
红黑树上的节点不是黑色节点就是红色节点
红黑树中可以存在连续黑色节点，但是不能出现连续红色节点
红黑树中的每一条路径上的黑色节点的数目相同

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

解答：由于红黑树中的所有路径上的黑色节点数目相同，红黑树中又不能出现连续的红色节点，所以红色节点插入在黑色节点之间或是黑色节点的后面。最短路径的一定是路径上的所有节点都为黑色节点，最长路径一定是在最短路径的基础上，每两个黑色节点中插入一个红色节点，再在最后一个黑色节点后面插入一个红色节点，所以最长路径的节点个数不会超过最短路径的两倍。

2.3 红黑树节点的定义

enum Color
{
	RED,
	BLACK
};

template<class T>
struct RBTreeNode
{
	RBTreeNode* _left;
	RBTreeNode* _right;
	RBTreeNode* _parent;
	T _date;
	Color _col;

	RBTreeNode(const T& date)
		: _right(nullptr)   // 节点的右孩子
		, _left(nullptr)    // 节点的左孩子
		, _parent(nullptr)  // 节点的父亲
		, _col(RED)         // 节点的颜色
		, _date(date)       // 节点存储的内容
		{}
};

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

解答：由于红黑树上每条路径上的黑色节点的数量是相同的，插入一个节点而节点的颜色是黑色，就会导致插入黑色节点的那个路径上的黑色节点的数量比其他路径上的黑色节点数量多上一个，那么这颗树就会出现问题。而插入节点的颜色为红色，可以出现问题，就算出现问题最多就是出现连续的两个红色节点，可以通过变色、旋转来解决连续红色节点的问题，操作起来更加的简单。

2.4 红黑树的结构

在这里插入图片描述

2.5 红黑树的插入操作

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

按照二叉搜索的树规则插入新节点
检测新节点插入后，红黑树的性质是否造到破坏
因为新节点的默认颜色是红色，因此：如果其双亲节点的颜色是黑色，没有违反红黑树任何性质，则不需要调整；但当新插入节点的双亲节点颜色为红色时，就违反了性质三不能有连在一起的红色节点，此时需要对红黑树分情况来讨论：

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

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

在这里插入图片描述

问题：c和p均为红，违反了性质三，此处能否将p直接改为黑？
解答：不可以，将p直接改为黑色，会使含有p节点的路径多一个黑色节点，违反了每条路径有相同黑色节点数量的原则。

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

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

说明:u的情况有两种

如果u节点不存在，则c一定是新插入节点，因为如果c不是新插入节点，则c和p一定有一个节点的颜色是黑色，就不满足性质4:每条路径黑色节点个数相同。
如果u节点存在，则其一定是黑色的，那么c节点原来的颜色一定是黑色的，现在看到其是红色的原因是因为c的子树在调整的过程中将c节点的颜色由黑色改成红色。

在这里插入图片描述

p为g的左孩子，c为p的左孩子，则进行右单旋转；相反，
p为g的右孩子，c为p的右孩子，则进行左单旋转
p、g变色–p变黑，g变红

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

在这里插入图片描述

p为g的左孩子，c为p的右孩子，则针对p做左单旋转，变为情况二，再进行一次右单旋；
p为g的右孩子，c为p的左孩子，则针对p做右单旋转，变为情况二，再进行一次左单旋。

template<class K, class T>
class RBTree
{
public:
	typedef RBTreeNode<T> Node;

	// 在红黑树中插入值为data的节点，插入成功返回true，否则返回false
	// 注意：为了简单起见，本次实现红黑树不存储重复性元素
	pair<iterator,bool> Insert(const T& date)
	{
		if (nullptr == _root)
		{
			_root = new Node(date);
			_root->_col = BLACK;
			return make_pair(iterator(_root),true);
		}

		Node* cur = _root;
		Node* parent = cur->_parent;
		KofT koft;

		while (cur)
		{
			if (koft(cur->_date) > koft(date))
			{
				parent = cur;
				cur = cur->_left;
			}
			else if (koft(cur->_date) < koft(date))
			{
				parent = cur;
				cur = cur->_right;
			}
			else 
			{
				return make_pair(iterator(cur),false);
			}
		}

		// 插入新节点
		cur = new Node(date);
		// 由于后面cur可能会随着旋转而改变
		// 这里定义一个newNode记录一下
		Node* newNode = cur;

		cur->_parent = parent;
		if (koft(parent->_date) > koft(date))
		{
			parent->_left = cur;
		}
		else
		{
			parent->_right = cur;
		}

		// 有向上处理的情况，可能存在parent不存在的情况
		while (parent && parent->_col == RED)
		{
			Node* grandfather = parent->_parent;
			//        g
			//		p   u
			//   c

			if (parent == grandfather->_left)
			{
				Node* uncle = grandfather->_right;
				// 叔叔存在且叔叔的颜色为红色
				// 变色完后子树的根节点为红色，并且该节点的父亲节点的颜色可能为红色
				// 需要向上调整
				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);

						grandfather->_col = RED;
						cur->_col = BLACK;
					}
					break;
				}
			}
			
			// (parent == grandfather->_right)
			else
			{
				//        g
				//	    u   p
				//			  c
				Node* uncle = grandfather->_left;
				// 叔叔存在且为红色
				// 叔叔和父亲变为黑色，祖父变为红色
				// 由于祖父的父亲可能为红色，继续向上处理
				if (uncle && uncle->_col == RED)
				{
					parent->_col = uncle->_col = BLACK;
					grandfather->_col = RED;

					cur = grandfather;
					parent = cur->_parent;
				}
				// 叔叔不存在或叔叔存在且为黑色色
				// 旋转处理，旋转后父亲变黑，祖父变红
				// 子树的根节点为黑色不需要继续处理
				else
				{
					//        g
					//	    u   p
					//			  c
					if (cur == parent->_right)
					{
						RotateL(grandfather);

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

						cur->_col = BLACK;
						grandfather->_col = RED;
					}
					
					break;
				}
				
			}
			// 将根节点变为黑色
		}
		_root->_col = BLACK;
		return make_pair(iterator(newNode) , true);
	}

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

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

		Node* Pparent = parent->_parent;
		subL->_right = parent;

		parent->_parent = subL;

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

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

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

		Node* Pparent = parent->_parent;
		parent->_parent = subR;
		subR->_left = parent;

		if (parent == _root)
		{
			_root = subR;
			subR->_parent = nullptr;
		}
		else
		{
			subR->_parent = Pparent;
			if (Pparent->_left == parent)
			{
				Pparent->_left = subR;
			}
			else
			{
				Pparent->_right = subR;
			}
		}
	}
private:
	Node* _root = nullptr;
	size_t _size;
};

2.6 红黑树的验证

红黑树的检测分为两步：

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

template<class K, class T, class KofT>
class RBTree
{
public:
	typedef RBTreeNode<T> Node;

	// 检测红黑树是否为有效的红黑树，注意：其内部主要依靠_IsValidRBTRee函数检测
	bool IsValidRBTRee()
	{
		if (nullptr == _root)
		{
			return false;
		}

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

		int blackCount = 0;
		Node* cur = _root;
		while (cur)
		{
			if (cur->_col == BLACK)
			{
				blackCount++;
			}

			cur = cur->_left;
		}
		return _IsValidRBTRee(_root, blackCount, 0);
	}
	
	// 中序遍历
	void InOrder()
	{
		_InOrder(_root);
	}
private:
	void _InOrder(Node* pRoot)
	{
		if (pRoot == nullptr)
		{
			return;
		}

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

	bool _IsValidRBTRee(Node* pRoot, size_t blackCount, size_t pathBlack)
	{
		// 判断是否每条路径黑色节点是否相同
		if (nullptr == pRoot)
		{
			if (blackCount != pathBlack)
			{
				cout << "有路径黑色节点不相同" << endl;
				return false;
			}
			else
			{
				return true;
			}
		}

		if (pRoot->_col == BLACK)
			pathBlack++;

		// 判断是否出现连续红色节点
		if (pRoot->_col == RED && pRoot->_parent->_col == RED)
		{
			cout << "有连续红色节点" << endl;
			return false;
		}

		return _IsValidRBTRee(pRoot->_left, blackCount, pathBlack)
			&& _IsValidRBTRee(pRoot->_right, blackCount, pathBlack);
	}
private:
	Node* _root = nullptr;
	size_t _size;
};

2.7 红黑树与AVL树的比较

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

三、红黑树的模拟实现

3.1 红黑树中迭代器的实现

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

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

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

	Ptr operator->()
	{
		return &_node->_date;
	}

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

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

	// 左子树 根 右子树
	// 若当前节点的右树不为空，则指向当前节点的最右节点
	// 若当前节点右树为空，则沿着这条路径向上查找
	// 找到孩子是父亲左的祖先，使迭代器指向这个祖先
	Self& operator++()
	{
		Node* cur = this->_node;

		if (nullptr != cur->_right)
		{
			// 指向右树
			cur = cur->_right;
			// 指向右树最左节点
			while (cur && cur->_left)
			{
				cur = cur->_left;
			}

			_node = cur;
		}
		else
		{
			Node* parent = cur->_parent;

			// cur为根节点时，parent为空
			// 所以这里要判断parent是否为空
			while (parent && cur == parent->_right)
			{
				cur = parent;
				parent = cur->_parent;
			}
			// 找到了cur是parent左

			_node = parent;
		}
		return *this;
	}

	// 右子树 根 左子树
	// 若当前节点的左子树不为空，则找到左子树的最右节点
	// 若当前节点的左子树为空，则沿着这条路径向上查找
	// 找到孩子是父亲的右的祖先节点，使迭代器指向这个节点
	Self& operator--()
	{
		Node* cur = _node;

		if (nullptr != cur->_left)
		{
			cur = cur->_left;

			while (cur && cur->_right)
			{
				cur = cur->_right;
			}

			_node = cur;
		}
		else
		{
			Node* parent = cur->parent;

			// cur为根节点时，parent为空
			// 所以这里要判断parent是否为空
			while (parent && cur == parent->_left)
			{
				cur = parent;
				parent = cur->_parent;
			}

			_node = parent;
		}
		return *this;
	}

private:
	Node* _node;
};

3.2 红黑树中clear、size 和 empty 的实现

template<class K, class T, class KofT>
class RBTree
{
public:
	typedef RBTreeNode<T> Node;

	bool Empty()const
	{
		return _root == nullptr;
	}

	void Clear()
	{
		_Clear(_root);
	}

	size_t Size()const
	{
		return _size;
	}
private:
	size_t _Size(Node* pRoot)
	{
		if (pRoot == nullptr)
		{
			return 0;
		}

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

	void _Clear(Node*& pRoot)
	{
		if (pRoot == nullptr)
			return;

		_Clear(pRoot->_left);
		_Clear(pRoot->_right);
		delete pRoot;
		pRoot = nullptr;
	}
private:
	Node* _root = nullptr;
	size_t _size;
};

3.3 获得红黑树中的最左/右节点

template<class K, class T, class KofT>
class RBTree
{
public:
	typedef RBTreeNode<T> Node;
	// 获取红黑树最左侧节点
	Node* LeftMost()
	{
		Node* cur = _root;
		while (cur && cur->_left)
		{
			cur = cur->_left;
		}

		return cur;
	}

	// 获取红黑树最右侧节点
	Node* RightMost()
	{
		Node* cur = _root;
		while (cur && cur->_right)
		{
			cur = cur->_right;
		}

		return cur;
	}

private:
	Node* _root = nullptr;
	size_t _size;
};

3.4 红黑树中 begin 和 end 的实现

template<class K, class T, class KofT>
class RBTree
{
public:
	typedef RBTreeNode<T> Node;
	typedef __TreeIterator<T, T&, T*> iterator;
	typedef __TreeIterator<T, const T&, const T*> const_iterator;

	iterator begin()
	{
		Node* cur = _root;

		while (cur && cur->_left)
		{
			cur = cur->_left;
		}

		return iterator(cur);
	}

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

	const_iterator begin()const
	{
		Node* cur = _root;

		while (cur && cur->_left)
		{
			cur = cur->_left;
		}

		return const_iterator(cur);
	}

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

private:
	Node* _root = nullptr;
	size_t _size;
};

3.5 红黑树中 insert 的实现

这里类模版参数中的KofT是为了后面set和map封装，由于插入节点时需要有元素的比较，set是直接使用K直接进行比较，而map是取pair<K,V>中的K，那么两种对象比较方式不同，而将insert写两遍不方便，那么换一个思路，那么就写一个仿函数，可以让set取到K，map取到pair<K,V>中的K，而这个仿函数在封装set和map中写到，并在创建对象时将仿函数传给KofT。

template<class K, class T, class KofT>
class RBTree
{
public:
	typedef RBTreeNode<T> Node;
	typedef __TreeIterator<T, T&, T*> iterator;
	typedef __TreeIterator<T, const T&, const T*> const_iterator;

	// 在红黑树中插入值为data的节点，插入成功返回true，否则返回false
	// 注意：为了简单起见，本次实现红黑树不存储重复性元素

	// 这里pair的返回值应该是pair<iterator,bool>
	// 但是由于set封装中的，无论是iterator还是const_iterator
	// 实际上都是const_iterator，而这里的iterator并不能用来构造const_iterator
	// 我们可以写一个iterator用来构造const_iterator
	// 但是这里为了方便就返回一个节点的指针Node*
	// Node* 无论是iterator还是const_iterator都能构造
	pair<Node*, bool> Insert(const T& date)
	{
		if (nullptr == _root)
		{
			_root = new Node(date);
			_root->_col = BLACK;
			_size++;
			return make_pair(_root, true);
		}

		Node* cur = _root;
		Node* parent = cur->_parent;
		KofT koft;

		while (cur)
		{
			if (koft(cur->_date) > koft(date))
			{
				parent = cur;
				cur = cur->_left;
			}
			else if (koft(cur->_date) < koft(date))
			{
				parent = cur;
				cur = cur->_right;
			}
			else
			{
				return make_pair(cur, false);
			}
		}

		// 插入新节点
		cur = new Node(date);
		// 由于后面cur可能会随着旋转而改变
		// 这里定义一个newNode记录一下
		Node* newNode = cur;

		cur->_parent = parent;
		if (koft(parent->_date) > koft(date))
		{
			parent->_left = cur;
		}
		else
		{
			parent->_right = cur;
		}

		// 有向上处理的情况，可能存在parent不存在的情况
		while (parent && parent->_col == RED)
		{
			Node* grandfather = parent->_parent;
			//        g
			//		p   u
			//   c


			if (parent == grandfather->_left)
			{
				Node* uncle = grandfather->_right;
				// 叔叔存在且叔叔的颜色为红色
				// 变色完后子树的根节点为红色，并且该节点的父亲节点的颜色可能为红色
				// 需要向上调整
				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);

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


					break;
				}
			}


			// (parent == grandfather->_right)
			else
			{
				//        g
				//	    u   p
				//			  c
				Node* uncle = grandfather->_left;
				// 叔叔存在且为红色
				// 叔叔和父亲变为黑色，祖父变为红色
				// 由于祖父的父亲可能为红色，继续向上处理
				if (uncle && uncle->_col == RED)
				{
					parent->_col = uncle->_col = BLACK;
					grandfather->_col = RED;

					cur = grandfather;
					parent = cur->_parent;
				}
				// 叔叔不存在或叔叔存在且为黑色色
				// 旋转处理，旋转后父亲变黑，祖父变红
				// 子树的根节点为黑色不需要继续处理
				else
				{
					//        g
					//	    u   p
					//			  c
					if (cur == parent->_right)
					{
						RotateL(grandfather);

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

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

					break;
				}

			}
			// 将根节点变为黑色
		}
		_root->_col = BLACK;
		_size++;
		return make_pair(newNode, true);
	}

	 在红黑树中插入值为data的节点，插入成功返回true，否则返回false
	 注意：为了简单起见，本次实现红黑树不存储重复性元素
	//pair<iterator,bool> Insert(const T& date)
	//{
	//	if (nullptr == _root)
	//	{
	//		_root = new Node(date);
	//		_root->_col = BLACK;
	//		_size++;
	//		return make_pair(iterator(_root),true);
	//	}

	//	Node* cur = _root;
	//	Node* parent = cur->_parent;
	//	KofT koft;

	//	while (cur)
	//	{
	//		if (koft(cur->_date) > koft(date))
	//		{
	//			parent = cur;
	//			cur = cur->_left;
	//		}
	//		else if (koft(cur->_date) < koft(date))
	//		{
	//			parent = cur;
	//			cur = cur->_right;
	//		}
	//		else 
	//		{
	//			return make_pair(iterator(cur),false);
	//		}
	//	}

	//	// 插入新节点
	//	cur = new Node(date);
	//	// 由于后面cur可能会随着旋转而改变
	//	// 这里定义一个newNode记录一下
	//	Node* newNode = cur;

	//	cur->_parent = parent;
	//	if (koft(parent->_date) > koft(date))
	//	{
	//		parent->_left = cur;
	//	}
	//	else
	//	{
	//		parent->_right = cur;
	//	}

	//	// 有向上处理的情况，可能存在parent不存在的情况
	//	while (parent && parent->_col == RED)
	//	{
	//		Node* grandfather = parent->_parent;
	//		//        g
	//		//		p   u
	//		//   c


	//		if (parent == grandfather->_left)
	//		{
	//			Node* uncle = grandfather->_right;
	//			// 叔叔存在且叔叔的颜色为红色
	//			// 变色完后子树的根节点为红色，并且该节点的父亲节点的颜色可能为红色
	//			// 需要向上调整
	//			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);

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

	//				break;
	//			}
	//		}
	//		
	//		
	//		// (parent == grandfather->_right)
	//		else
	//		{
	//			//        g
	//			//	    u   p
	//			//			  c
	//			Node* uncle = grandfather->_left;
	//			// 叔叔存在且为红色
	//			// 叔叔和父亲变为黑色，祖父变为红色
	//			// 由于祖父的父亲可能为红色，继续向上处理
	//			if (uncle && uncle->_col == RED)
	//			{
	//				parent->_col = uncle->_col = BLACK;
	//				grandfather->_col = RED;

	//				cur = grandfather;
	//				parent = cur->_parent;
	//			}
	//			// 叔叔不存在或叔叔存在且为黑色色
	//			// 旋转处理，旋转后父亲变黑，祖父变红
	//			// 子树的根节点为黑色不需要继续处理
	//			else
	//			{
	//				//        g
	//				//	    u   p
	//				//			  c
	//				if (cur == parent->_right)
	//				{
	//					RotateL(grandfather);

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

	//					cur->_col = BLACK;
	//					grandfather->_col = RED;
	//				}
	//				
	//				break;
	//			}
	//			
	//		}
	//		// 将根节点变为黑色
	//	}
	//	_size++;
	//	_root->_col = BLACK;
	//	return make_pair(iterator(newNode) , true);
	//}

private:
	Node* _root = nullptr;
	size_t _size;
};

3.6 红黑树中 find 的实现

template<class K, class T, class KofT>
class RBTree
{
public:
	typedef RBTreeNode<T> Node;
	typedef __TreeIterator<T, T&, T*> iterator;
	typedef __TreeIterator<T, const T&, const T*> const_iterator;

	// 检测红黑树中是否存在值为data的节点，存在返回该节点的地址，否则返回nullptr
	// Node* 无论是iterator还是const_iterator都能构造
	Node* Find(const K& k)
	{
		KofT koft;

		Node* cur = _root;
		while (cur)
		{
			if (koft(cur->_date) < k)
			{
				cur = cur->_right;
			}
			else if (koft(cur->_date) > k)
			{
				cur = cur->_left;
			}
			else
			{
				return cur;
			}
		}
		return nullptr;
	}

private:
	Node* _root = nullptr;
	size_t _size;
};

3.7 红黑树的整体实现

#pragma once
#include <iostream>
#include <string>
#include <vector>

#include<stdlib.h>

using namespace std;

enum Color
{
	RED,
	BLACK
};

template<class T>
struct RBTreeNode
{
	RBTreeNode* _left;
	RBTreeNode* _right;
	RBTreeNode* _parent;
	T _date;
	Color _col;

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

template<class T, class Ref ,class Ptr>
struct __TreeIterator
{
	typedef RBTreeNode<T> Node;
	typedef __TreeIterator<T , Ref , Ptr> Self;
	
	__TreeIterator(Node* node)
		:_node(node)
	{}

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

	Ptr operator->()
	{
		return &_node->_date;
	}

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

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

	// 左子树 根 右子树
	// 若当前节点的右树不为空，则指向当前节点的最右节点
	// 若当前节点右树为空，则沿着这条路径向上查找
	// 找到孩子是父亲左的祖先，使迭代器指向这个祖先
	Self& operator++()
	{
		Node* cur = this->_node;

		if (nullptr != cur->_right)
		{
			// 指向右树
			cur = cur->_right;
			// 指向右树最左节点
			while (cur && cur->_left)
			{
				cur = cur->_left;
			}

			_node = cur;
		}
		else
		{
			Node* parent = cur->_parent;

			// cur为根节点时，parent为空
			// 所以这里要判断parent是否为空
			while (parent && cur == parent->_right)
			{
				cur = parent;
				parent = cur->_parent;
			}
			// 找到了cur是parent左

			_node = parent;
		}
		return *this;
	}

	// 右子树 根 左子树
	// 若当前节点的左子树不为空，则找到左子树的最右节点
	// 若当前节点的左子树为空，则沿着这条路径向上查找
	// 找到孩子是父亲的右的祖先节点，使迭代器指向这个节点
	Self& operator--()
	{
		Node* cur = _node;

		if (nullptr != cur->_left)
		{
			cur = cur->_left;

			while (cur && cur->_right)
			{
				cur = cur->_right;
			}

			_node = cur;
		}
		else
		{
			Node* parent = cur->parent;

			// cur为根节点时，parent为空
			// 所以这里要判断parent是否为空
			while (parent && cur == parent->_left)
			{
				cur = parent;
				parent = cur->_parent;
			}

			_node = parent;
		}
		return *this;
	}

private:
	Node* _node;
};

template<class K ,class T, class KofT>
class RBTree
{
public:
	typedef RBTreeNode<T> Node;
	typedef __TreeIterator<T , T& ,T*> iterator;
	typedef __TreeIterator<T, const T&, const T*> const_iterator;

	// 在红黑树中插入值为data的节点，插入成功返回true，否则返回false
	// 注意：为了简单起见，本次实现红黑树不存储重复性元素

	// 这里pair的返回值应该是pair<iterator,bool>
	// 但是由于set封装中的，无论是iterator还是const_iterator
	// 实际上都是const_iterator，而这里的iterator并不能用来构造const_iterator
	// 我们可以写一个iterator用来构造const_iterator
	// 但是这里为了方便就返回一个节点的指针Node*
	// Node* 无论是iterator还是const_iterator都能构造
	pair<Node*, bool> Insert(const T& date)
	{
		if (nullptr == _root)
		{
			_root = new Node(date);
			_root->_col = BLACK;
			_size++;
			return make_pair(_root, true);
		}

		Node* cur = _root;
		Node* parent = cur->_parent;
		KofT koft;

		while (cur)
		{
			if (koft(cur->_date) > koft(date))
			{
				parent = cur;
				cur = cur->_left;
			}
			else if (koft(cur->_date) < koft(date))
			{
				parent = cur;
				cur = cur->_right;
			}
			else
			{
				return make_pair(cur, false);
			}
		}

		// 插入新节点
		cur = new Node(date);
		// 由于后面cur可能会随着旋转而改变
		// 这里定义一个newNode记录一下
		Node* newNode = cur;

		cur->_parent = parent;
		if (koft(parent->_date) > koft(date))
		{
			parent->_left = cur;
		}
		else
		{
			parent->_right = cur;
		}

		// 有向上处理的情况，可能存在parent不存在的情况
		while (parent && parent->_col == RED)
		{
			Node* grandfather = parent->_parent;
			//        g
			//		p   u
			//   c


			if (parent == grandfather->_left)
			{
				Node* uncle = grandfather->_right;
				// 叔叔存在且叔叔的颜色为红色
				// 变色完后子树的根节点为红色，并且该节点的父亲节点的颜色可能为红色
				// 需要向上调整
				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);

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


					break;
				}
			}


			// (parent == grandfather->_right)
			else
			{
				//        g
				//	    u   p
				//			  c
				Node* uncle = grandfather->_left;
				// 叔叔存在且为红色
				// 叔叔和父亲变为黑色，祖父变为红色
				// 由于祖父的父亲可能为红色，继续向上处理
				if (uncle && uncle->_col == RED)
				{
					parent->_col = uncle->_col = BLACK;
					grandfather->_col = RED;

					cur = grandfather;
					parent = cur->_parent;
				}
				// 叔叔不存在或叔叔存在且为黑色色
				// 旋转处理，旋转后父亲变黑，祖父变红
				// 子树的根节点为黑色不需要继续处理
				else
				{
					//        g
					//	    u   p
					//			  c
					if (cur == parent->_right)
					{
						RotateL(grandfather);

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

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

					break;
				}

			}
			// 将根节点变为黑色
		}
		_root->_col = BLACK;
		_size++;
		return make_pair(newNode, true);
	}
	
	iterator begin()
	{
		Node* cur = _root;

		while (cur && cur->_left)
		{
			cur = cur->_left;
		}

		return iterator(cur);
	}

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

	const_iterator begin()const
	{
		Node* cur = _root;

		while (cur && cur->_left)
		{
			cur = cur->_left;
		}

		return const_iterator(cur);
	}

	const_iterator end()const
	{
		return const_iterator(nullptr);
	}
	 
	/*const_iterator begin()const
	{
		Node* cur = _root;

		while (cur && cur->_left)
		{
			cur = cur->_left;
		}

		return iterator(cur);
	}

	const_iterator end()const
	{
		return iterator(nullptr);
	}*/

	/*bool operator!=(iterator it)
	{
		return this->_node != it->_node;
	}

	bool operator==(iterator it)
	{
		return this->_node == it->_node;
	}*/
	
	// 检测红黑树中是否存在值为data的节点，存在返回该节点的地址，否则返回nullptr
	// Node* 无论是iterator还是const_iterator都能构造	
	Node* Find(const K& k)
	{
		KofT koft;

		Node* cur = _root;
		while (cur)
		{
			if (koft(cur->_date) < k)
			{
				cur = cur->_right;
			}
			else if (koft(cur->_date) > k)
			{
				cur = cur->_left;
			}
			else
			{
				return cur;
			}
		}
		return nullptr;
	}


	// 获取红黑树最左侧节点
	Node* LeftMost()
	{
		Node* cur = _root;
		while (cur && cur->_left)
		{
			cur = cur->_left;
		}

		return cur;
	}

	// 获取红黑树最右侧节点
	Node* RightMost()
	{
		Node* cur = _root;
		while (cur && cur->_right)
		{
			cur = cur->_right;
		}

		return cur;
	}

	// 检测红黑树是否为有效的红黑树，注意：其内部主要依靠_IsValidRBTRee函数检测
	bool IsValidRBTRee()
	{
		if (nullptr == _root)
		{
			return false;
		}

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

		int blackCount = 0;
		Node* cur = _root;
		while (cur)
		{
			if (cur->_col == BLACK)
			{
				blackCount++;
			}

			cur = cur->_left;
		}
		return _IsValidRBTRee(_root, blackCount, 0);
	}

	void InOrder()
	{
		_InOrder(_root);
	}

	size_t Size()const
	{
		return _size;
	}

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

	bool Empty()const
	{
		return _root == nullptr;
	}

	void Clear()
	{
		Destroy(_root);
	}
private:
	void _InOrder(Node* pRoot)
	{
		if (pRoot == nullptr)
		{
			return;
		}

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

	size_t _Height(Node* pRoot)
	{
		if (pRoot == nullptr)
		{
			return 0;
		}

		size_t HeightLeft = _Height(pRoot->_left);
		size_t HeightRight = _Height(pRoot->_right);

		return HeightLeft > HeightRight ? 
			HeightLeft + 1 : HeightRight + 1;
	}

	void Destroy(Node*& pRoot)
	{
		if (pRoot == nullptr)
			return;

		Destroy(pRoot->_left);
		Destroy(pRoot->_right);
		delete pRoot;
		pRoot = nullptr;
	}

	bool _IsValidRBTRee(Node* pRoot, size_t blackCount, size_t pathBlack)
	{
		// 判断是否每条路径黑色节点是否相同
		if (nullptr == pRoot)
		{
			if (blackCount != pathBlack)
			{
				cout << "有路径黑色节点不相同" << endl;
				return false;
			}
			else
			{
				return true;
			}
		}

		if (pRoot->_col == BLACK)
			pathBlack++;

		// 判断是否出现连续红色节点
		if (pRoot->_col == RED && pRoot->_parent->_col == RED)
		{
			cout << "有连续红色节点" << endl;
			return false;
		}

		return _IsValidRBTRee(pRoot->_left, blackCount, pathBlack)
			&& _IsValidRBTRee(pRoot->_right, blackCount, pathBlack);
	}

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

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

		Node* Pparent = parent->_parent;
		subL->_right = parent;

		parent->_parent = subL;

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

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

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

		Node* Pparent = parent->_parent;
		parent->_parent = subR;
		subR->_left = parent;

		if (parent == _root)
		{
			_root = subR;
			subR->_parent = nullptr;
		}
		else
		{
			subR->_parent = Pparent;
			if (Pparent->_left == parent)
			{
				Pparent->_left = subR;
			}
			else
			{
				Pparent->_right = subR;
			}
		}
	}
private:
	Node* _root = nullptr;
	size_t _size;
};

四、set 和 map 的封装

4.1 set的封装

#pragma once

#include"RBTree.h"

namespace aj
{
	template<class K>
	class set
	{
	public:
		struct SetKofT
		{
			const K& operator()(const K& k)
			{
				return k;
			}
		};

		// 对类模板取内嵌类型，加typename告诉编译器这里是类型
		typedef typename RBTree<K, K, SetKofT>::const_iterator iterator;
		typedef typename RBTree<K, K, SetKofT>::const_iterator const_iterator;

		pair<iterator, bool> insert(const K& k)
		{
			return _set.Insert(k);
		}

		size_t size()const
		{
			return _set.Size();
		}

		// 这里无论是iterator还是const_iterator
		// 实际上都是const_iterator
		// 由于set无论是const版本还是非const版本都不能进行修改
		// 所以这里不需要重载const版本
		iterator begin()const
		{
			return _set.begin();
		}

		iterator end()const
		{
			return _set.end();
		}

		/*const_iterator begin()const
		{
			return _set.begin();
		}

		const_iterator end()const
		{
			return _set.end();
		}*/

		bool operator!=(iterator it)
		{
			return this != it;
		}

		bool operator==(iterator it)
		{
			return this == it;
		}

		bool empty()const
		{
			return _set.Empty();
		}

		void clear()
		{
			_set.Clear();
		}

		iterator find(const K& k)
		{
			return _set.Find(k);
		}

		const_iterator find(const K& k)const
		{
			return _set.Find(k);
		}
	private:
		RBTree<const K, K, SetKofT> _set;
	};
}

4.2 map的封装

#pragma once

#include"RBTree.h"

namespace aj
{
	template<class K,class V>
	class map
	{
	public:
		struct MapKofT
		{
			const K& operator()(const pair<K, V>& k)
			{
				return k.first;
			}
		};

		// 这里pair中的K需要加const，是因为要和下面的成员变量类型相同
		typedef typename RBTree<K, pair<const K, V>, MapKofT>::iterator iterator;
		typedef typename RBTree<K, pair<const K, V>, MapKofT>::const_iterator const_iterator;

		pair<iterator, bool> insert(const pair<K, V>& k)
		{
			return _map.Insert(k);
		}

		size_t size() 
		{
			return _map.Size();
		}

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

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

		const_iterator begin()const
		{
			return _map.begin();
		}

		const_iterator end()const
		{
			return _map.end();
		}

		bool operator!=(iterator it)
		{
			return this != it;
		}

		bool operator==(iterator it)
		{
			return this == it;
		}

		bool empty()const
		{
			return _map.Empty();
		}

		void clear()
		{
			_map.Clear();
		}

		iterator find(const K& k)
		{
			return _map.Find(k);
		}

		const_iterator find(const K& k)const
		{
			return _map.Find(k);
		}

		V& operator[](const K& k)
		{
			// 如果k在_map中存在，则operator[]充当查找的作用
			// 如果k在_map中不存在，则operator[]充当插入的作用
			pair<iterator, bool> ret = _map.insert(make_pair(k,V()));
			return ret.first->second;
		}
	private:
		RBTree<K,pair<const K,V>, MapKofT> _map;
	};
}

结尾

如果有什么建议和疑问，或是有什么错误，大家可以在评论区中提出。
希望大家以后也能和我一起进步！！🌹🌹
如果这篇文章对你有用的话，希望大家给一个三连支持一下！！🌹🌹

在这里插入图片描述

【C++】AVL树/红黑树实现及map与set的封装

目录

一、AVL 树

1.1 AVL树的概念

1.2 AVL树节点的定义

1.3 AVL树的插入

1.4 AVL树的旋转

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

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

1.4.3 新节点插入较高左子树的右侧—左右高：先左单旋再右单旋

1.4.4 新节点插入较高右子树的左侧—右左高：先右单旋再左单旋

1.5 AVL树的验证

1.6 AVL树的性能

1.7 AVL树的整体实现

二、红黑树

2.1 红黑树的概念

2.2 红黑树的性质

2.3 红黑树节点的定义

2.4 红黑树的结构

2.5 红黑树的插入操作

2.6 红黑树的验证

2.7 红黑树与AVL树的比较

三、红黑树的模拟实现

3.1 红黑树中迭代器的实现

3.2 红黑树中clear、size 和 empty 的实现

3.3 获得红黑树中的最左/右节点

3.4 红黑树中 begin 和 end 的实现

3.5 红黑树中 insert 的实现

3.6 红黑树中 find 的实现

3.7 红黑树的整体实现

四、set 和 map 的封装

4.1 set的封装

4.2 map的封装

结尾

网站公告

今日签到

热门文章

最新发布