概念及定义

红黑树的概念

红黑树，顾名思义就是在每个结点上增加一个存储位表示结点颜色，其是一颗最长路径的长度不超过最短路径的长度的2倍的二叉搜索树，因而红黑树是近似平衡的。在红黑树中，为了便于规范，将空结点（NIL）认为是叶子节点，保证叶子结点一定是黑色的。

红黑树的性质

• 1.每个结点不是红色就是黑色
• 2.根节点是黑色的
• 3. 如果一个结点是红色的，则它的两个孩子结点一定是黑色的
• 4. 对于每个结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数目的黑色结点
• 5.每个叶子结点都是黑色的（需要注意的是，这里的叶子节点指的是空结点）
  由性质三知道红黑树中不存在连续的两个红色结点，由此推出在一条路径上红色结点的数量一定不会超过黑色结点的数量；而由性质四知道红黑树的每条路径上都有着相同数量的黑色结点。进一步的，我们可以得出结论：红黑树的最短路径为全是黑色结点，最长路径为全是红色结点。如此即可保证红黑树的最长路径不超过最短路径的两倍。
  ⏰【补充】路径的概念：树的路径为根节点到叶子结点的那条路径（但是在红黑树的概念理解中，我们将空结点认为是叶子结点）

红黑树的结点定义

与AVL树并无太大的不同，红黑树的结点只是在AVL树的基础上增加了颜色的定义（这里我们还是使用key-value模型的二叉搜索树），其中颜色用枚举表示：

enum Color
{
	BLACK,
	RED
};
template <class T>
//template 
struct RBTreeNode
{
	typedef RBTreeNode<K, V> Node;

	Node* _left;
	Node* _right;
	Node* _parent;
	//T _data;
	pair<K, V> _kv;
	Color _color;

	//RBTreeNode(const T& data)
	RBTreeNode(const pair<K, V> kv)
		:_left(nullptr)
		,_right(nullptr)
		,_parent(nullptr)
		//,_data(data)
		,_kv(kv)
		,_color(RED)
	{}
};

在这里结点颜色默认设置为红色，是为了方便后续插入，在保证红黑树性质的情况下，通过插入红色结点可以更好的保证性质四不被破坏，而如果插入黑色结点，那么保证每条路径的黑色结点数量相等操作将非常繁琐。

红黑树的结构

template <class K, class V>

class RBTree
{
public:
	//typedef RBTreeNode Node;
	typedef RBTreeNode<K,V> Node;
	RBTree()
		:_root(nullptr)
	{}
private:
	Node* _root;
};

其实在STL中，红黑树的实现是还有一个header结点的，其中根节点的_parent指向header，header的_parent也指向根节点；而header的_left指向红黑树中最小的结点（最左下的结点），_right指向红黑树中最大的结点（最右下的结点），但为了简便，我们这里就不实现header结点的相关功能了。

红黑树的应用

红黑树最典型的应用就是实现C++STL中的map和set；其次还有Java库，Linux内核以及其他的一些内核都是用红黑树实现的。

红黑树与AVL树的比较

红黑树与AVL树都是平衡的二叉树：

• AVL树是严格平衡的，而红黑树是近似平衡的
• AVL树和红黑树的查找时间复杂度都是O(log2N)
• 由于红黑树旋转次数更少，因此在增删过程中性能较优

插入操作

在AVL树的基础下，红黑树的插入操作其实就不难了。

1、寻找要插入的位置

此步我们这钱已经多次介绍介绍，即若key值大于当前结点的key值，则向右寻找；若小于，则向左寻找；若相等，说明数据冗余，返回false。

2.判断是否符合红黑树的规则

由于我们产生新结点时将其颜色设置为红色，而每条路径上黑色结点数量相等这条规则就交给调整时保证。
故判断是否为红黑树就转换为判断是否存在连续红色的结点。

• 对于新插入的结点，若其父亲颜色为黑色，则满足红黑树的规则，无需调整。
• 而若其父亲颜色为红色，则规则被破坏，需要调整。

3.对于规则被破坏的情况，进行调整

在规则被破坏的前提下， 总共存在三种情况：1.只需变色；2.单旋+变色；3.双旋+变色。由于旋转操作在AVL树中已经详细介绍，若不清楚则可参考之前AVL树中关于旋转的内容：AVL树的旋转

• 情况一：若parent，grandparent以及ubcle结点存在，其中p、u为红色，g为黑色，此时只需变色，将parent和uncle变为黑色，grandparent变为红色，由于g所在的树可能为一棵子树，故此时仍需向上调整。
  

• 情况二：p存在为红色，g存在为黑色，u存在为黑色/u不存在，其中旋转为单旋情况。左边高->右单旋；若右边高->左单旋，旋转完后，p变为黑色，g变为红色
  

• 情况三：p存在为红色，g存在为黑色，u存在为黑色/u不存在，其中cur为双旋情况。双旋之后，cur为黑色，parent和grandparent为红色。

插入操作代码实现

综上所述，红黑树的代码实现如下：

	bool Insert(const pair<K,V>& kv)
	{
		if (_root == nullptr)
		{
			//_root = new Node(data);
			_root = new Node(kv);

			_root->_color = BLACK;
			return true;
		}
		Node* cur = _root;
		Node* parent = _root;
		//找到要找到的位置
		while (cur)
		{
			//KeyOfT kot;
			//if (kot(cur->_data) < kot(data))
			if(cur->_kv.first < kv.first)
			{
				parent = cur;
				cur = cur->_right;
			}
			//else if(kot(cur->_data) > kot(data))
			else if(cur->_kv.first > kv.first)
			{
				parent = cur;
				cur = cur->_left;
			}
			else//数据冗余，插入失败
			{
				return false;
			}
		}
		//cur为要插入的位置
		//cur = new Node(data);
		cur = new Node(kv);
		cur->_color = RED;
		cur->_parent = parent;
		//Node* newnode = cur;//保存当前的cur位置
		//if (kot(cur->_data) < kot(data))
		if(parent->_kv.first < kv.first)
		{
			parent->_right = cur;
		}
		else
		{
			parent->_left = cur;
		}
		while (parent && parent->_color == RED)
		{
			//由于parent存在且颜色为红，故panret一定不为根
			//那么grandfather一定存在
			Node* grandparent = parent->_parent;
			
			if (parent == grandparent->_left)
			{
				Node* uncle = grandparent->_right;

				//parent为红色，则grandfather一定不是红色，否则破坏规则
				if (uncle && uncle->_color == RED)
				{
					//情况一，uncle存在且为红
					cur->_color = RED;
					parent->_color = BLACK;
					uncle->_color = BLACK;
					grandparent->_color = RED;
					//此时仍需继续向上调整
					cur = grandparent;
					parent = cur->_parent;
				}
				else
				{
					if (cur == parent->_left)
					{
						//情况二，uncle不存在或为黑
						//右单旋
						RotateR(grandparent);
						//更新颜色
						parent->_color = BLACK;
						grandparent->_color = RED;
					}
					else//情况三
					{
						//左右双旋
						RotateL(parent);
						RotateR(grandparent);
						cur->_color = BLACK;
						grandparent->_color = RED;
					}
					//调整后符合红黑树规则，跳出循环
					break;
				}
			}
			else
			{
				Node* uncle = grandparent->_left;
				if (uncle && uncle->_color == RED)
				{
					//情况一，uncle存在且为红
					cur->_color = RED;
					parent->_color = BLACK;
					uncle->_color = BLACK;
					grandparent->_color = RED;
					//此时仍需继续向上调整
					cur = grandparent;
					parent = cur->_parent;
				}
				else
				{
					if (cur == parent->_right)//情况二
					{
						//左单旋
						RotateL(grandparent);
						//更新颜色
						parent->_color = BLACK;
						grandparent->_color = RED;
					}
					else//情况三
					{
						//右左双旋
						RotateR(parent);
						RotateL(grandparent);
						cur->_color = BLACK;
						grandparent->_color = RED;
					}
					//调整后符合红黑树规则，跳出循环
					break;
				}
			}
		}
		_root->_color = BLACK;//不论如何，直接将根节点颜色置为黑色
		return true;
	}

验证是否为红黑树

⏰1.根节点为黑色

• 首先判断，根节点的颜色，若根节点为红色，破坏规则二，返回false。

	bool IsRBTree()
	{
		if (_root == nullptr)//空树也是红黑树
			return true;
		//检测性质二：根节点是黑色
		if (_root->_color != BLACK)
		{
			cout << "违反规则二，根结点为红色" << endl;
			return false;
		}
		//判断性质三、四
		//...
	}

⏰2.不存在连续的两个红色结点

• 其次，对于规则三，若存在连续的两个红色结点，说明规则三被破坏了，返回false。
  这里需要注意的是，若去判断红色结点的孩子结点是否为红色，则还需要判断孩子是否存在；因此改为判断红色结点的父亲是否为红色，这样就可以简化代码及操作。

bool Check_RED_RED(Node* root)
	{
		//由于在调用函数中已经检测了根节点的合法性
		//故此处的root结点必不为红色
		if (root == nullptr)
			return true;
		if (root->_color == RED && root->_parent->_color == RED)
		{
			cout << "违反规则三，有连续的红色结点" << endl;
			return false;
		}
		return Check_RED_RED(root->_left) && Check_RED_RED(root->_right);
	}

⏰3.每条路径的黑色结点数量都相等

判断规则四的思路为先计算一条路径的黑色结点数量，然后遍历其他各条路径，对比黑色结点的数量，若不相等，则返回false。

//benchMark：基准值
	bool Check_BlackNum(Node* root, int benchMark, int blacknum)
	{
		if (root == nullptr)//到空结点，此时blacknum为该条路径的黑色结点数量
		{
			if (blacknum == benchMark)
				return true;
			else
				return false;
		}
		if (root->_color == BLACK)
			blacknum++;
		return Check_BlackNum(root->_left, benchMark, blacknum);
	}

⏰验证红黑树代码实现

	bool IsRBTree()
	{
		if (_root == nullptr)//空树也是红黑树
			return true;
		//检测性质二：根节点是黑色
		if (_root->_color != BLACK)
		{
			cout << "违反规则二，根结点为红色" << endl;
			return false;
		}
		//计算最左路径上黑色结点的数量作为基准值
		int benchMark = 0;
		Node* cur = _root;
		while (cur)
		{
			if (cur->_color == BLACK)
				benchMark++;
			cur = cur->_left;
		}
		int blacknum = 0;
		return Check_RED_RED(_root) && Check_BlackNum(_root, benchMark, blacknum);
	}

用红黑树封装实现map和set

在介绍完红黑树后，我们立刻来封装实现map和set。由此，接下来我们来实现红黑树的迭代器。

红黑树的迭代器

红黑树作为关联式容器，其迭代器与list类似，也是封装一个指针，来保证各结点的访问。

template <class T, class Ref, class Ptr>//自身，引用（实现*重载），指针（实现->重载）,便于范围for
struct RBTreeIterator
{
	typedef RBTreeIterator<T, Ref, Ptr> Self;
	typedef RBTreeNode<T> Node;

	Node* _node;
	RBTreeIterator(Node* node = nullptr)
		:_node(node)
	{}
	//实现其他功能
private:
};

• 重载*和->

	//让迭代器具有类似指针的功能
	Ref operator*()
	{
		return _node->_data;
	}
	Ptr operator->()
	{
		return &_node->_data;
	}

• 迭代器的移动

	//前置++
	Self& operator++()
	{
		Increment();
		return *this;
	}
	//后置++
	Self operator++(int)
	{
		Self tmp = *this;
		Increment();
		return tmp;
	}
	//前置--
	Self& operator--()
	{
		Decrement();
		return *this;
	}
	//后置--
	Self operator--(int)
	{
		Self tmp = this;
		Decrement();
		return *this;
	}
private:
	void Decrement()//迭代器以中序向前走一步
	{
		//1.若结点的左子树存在，则找左子树中最右下的结点
		if (_node->_left)
		{
			_node = _node->_left;
			while (_node->_right)
				_node = _node->_right;
		}
		else
		{
			//2.若结点的左孩子不存在，则向上寻找直到其不为父亲的左孩子
			Node* parent = _node->_parent;
			while (parent && parent->_left == _node)
			{
				_node = parent;
				parent = _node->_parent;
			}
			_node = parent;
		}
	}
	void Increment()//迭代器以中序向后走一步
	{
		//1.若结点的右子树存在,则找右子树中最左下的结点
		if (_node->_right)
		{
			_node = _node->_right;
			while (_node->_left)
			{
				_node = _node->_left;
			}
		}
		else//2.若结点的右子树不存在，则找到结点不是其父亲右孩子的结点
		{
			Node* parent = _node->_parent;
			while (parent && parent->_right == _node)
			{
				_node = parent;
				parent = _node->_parent;
			}
			_node = parent;
		}
	}

• 迭代器的比较

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

改造红黑树

这里有个问题，如何用一个红黑树实现Key模型的set及Key-Value模型的map。
因此，在红黑树中，我们将模板参数修改为：

template <class K, class T, class KeyOfT>

其中，K为key值，T对于set实例化来说是key值，而对于map实例化来说则是pair键值对。KeyOfT（从T中提取key值），此参数是为了便于插入时的比较，因为插入的参数修改为：bool Insert(T& data)。

	iterator begin()
	{
		//中序遍历的第一个结点		
		return iterator(LeftMost());
	}
	iterator end()
	{
		return iterator(nullptr);
	}
	Node* LeftMost()//中序遍历的第一个结点
	{
		Node* left = _root->_left;
		while (left && left->_left)
			left = left->_left;
		return left;
	}
	Node* RightMost()中序遍历的最后一个结点
	{
		Node* right = _root->_right;
		while (right && right->_right)
			right = right->_right;
		return right;
	}

set的封装实现

map内部直接封装了红黑树，实现key模型的二叉搜索树，所有接口直接调用红黑树的接口即可：

	template <class K>
	class Set
	{
	public:
		struct SetKeyofT
		{
			const K& operator()(const K& key)//对set而言，T为key，直接返回key值进行插入比较即可
			{
				return key;
			}
		};
		typedef typename RBTree<K, K, SetKeyofT>::iterator iterator;

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

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

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

	private:
		//Set内部封装红黑树，K和T参数都传入key值即可
		//Set内部再定义SetKeyofT结构体，里面重载了()操作符
		//返回Set对应的key值
		RBTree<K, K, SetKeyofT> _t;
	};

map的封装实现

map 的封装实现与set并无太大的区别，只不过map中重载了[]下标访问限定符：

	class Map
	{
	public:
		struct MapKeyofT
		{
			const K& operator()(const pair<const K, V>& data)
			{
				return data.first;
			}
		};
		typedef typename RBTree<K, pair<const K, V>, MapKeyofT>::iterator iterator;
		iterator begin()
		{
			return _t.begin();
		}
		iterator end()
		{
			return _t.end();
		}
		pair<iterator, bool> insert(const pair<K, V>& data)
		{
			return _t.Insert(data);
		}
		V& operator[](const K& key)
		{
			pair<iterator, bool> ret = _t.Insert(make_pair(key, V()));
			return ret.first->second;
		}
	private:
		//Map内部封装红黑树，K传入key值，T参数传入pair对象
		//Map内部再定义MapKeyofT结构体，里面重载了()操作符
		//返回Map对应的key值
		RBTree<K, pair<const K, V>, MapKeyofT> _t;
	};

代码实现

map和set封装实现的代码总览