数据结构·红黑树

1. 红黑树的概念

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

        红黑树的平衡不像是AVL树那样的绝对平衡，红黑树是一种近似平衡，它避免了处理繁琐的平衡因子，同时它搜索的效率也基本没有影响，不过是最坏情况要搜索 2*logN 但是这从时间复杂度上看，与AVL树的绝对logN是一样的。

2. 红黑树的规则

        1. 每个节点不是红色就是黑色

        2. 根节点是黑色的

        3. 如果一个节点是红色的，则它的两个孩子节点是黑色的 (没有两个连续的红节点)

        4. 对于每个节点，从该节点到其所有后代叶节点的简单路径上，均包含相同数目的黑色节点

        5. 每个叶子节点下的空节点都是黑色的，我们管这类空节点叫NIL节点，主要是用来统计总路径用的

        只要满足前4条规则就可以满足红黑树中：“最长路径中节点个数不会超过最短路径节点个数的两倍” 的原则。在我们写树，或者说对树进行调整的时候都不需要考虑规则5，规则5就是个计数用的

3. 红黑树的节点

                

        红黑树节点的颜色我们默认给红色。

        因为如果默认给黑色的话就会导致每新增一个节点时，该路径的黑色节点就会比别的路径多一个，此时不满足规则4，就要对树进行调整。

        但是如果插入的是一个红色节点，如果它的父节点是黑色的，则不用对树进行任何调整，只有它的父节点是红色的，才会违背规则3，需要对树进行调整。

4. 红黑树的插入

        红黑树的在插入时要一直符合那4个规则，因此在插入之后有两种调整方案。1. 更新节点的颜色，2. 当更新节点颜色的时候也控制不住这个树了的话就对树进行旋转。

        经过总结和推到给出的结果就是：当我们在调整树的时候只需要关注4个节点的状态

                

        分别是当前节点cur，父节点(parent) p，祖父节点(grandparent) g，叔叔节点(uncle) u。

        具体到选择那种调整方案的时候只需要看 uncle节点的状态，如果是红色就选第一种更新方案，如果是黑色或者不存在就选第二种更新方案 

        第一种更新方案是只需要进行颜色的更新就可以维持住红黑树的规则。

        第二种更新方案是需要旋转才可以。第二种更新方案又分为单旋和双旋两种情况

4.1 当uncle节点为红色时

        cur节点是新插入的，或者是调整上来的当前需要调整的节点，它一定是红色的，因为如果是黑色就不必调整了，也不会走到这步。

        parent节点也一定是红色的，因为如果parent节点是黑色的话我们就不用继续调整了，可以跳出调整循环了。

        grandparent节点一定是黑色的，因为如果它是红色的，说明这棵树之前就该调整了，p和g两个红色节点早就连到一块了，或者说这棵树已经坏了。

        那么此时我们假设uncle节点为红色，此时的调整思路如下图

        我们将g节点的黑色状态下发给p和u两个节点，再将g节点颜色改为红色，此时没有在任何路径上新增黑色节点，不会破坏规则4，同时也维护住了规则3。

        然后我们以g节点为cur，继续向上更新，此时更新分3种情况

        如果g节点已经是根了，那我们就不能往上更新了，然后将g节点也就是根节点置黑。

        如果g节点的parent存在且是黑色，那就不用继续更新了。

        如果g节点的parent存在且是红色，就需要向上更新

4.2 当uncle节点为黑或不存在时

        此时的树已经无法通过更新节点颜色控制住的了，因此我们要开始旋转树。

        与AVL树判断单双旋的思路是一样的，如果g、p、cur三个节点在同一边就进行单旋；如果一个在left一个在right，也就是说3个节点不在同一边就进行双旋。

4.1 单旋情况

        当uncle节点不存在时cur一定是新增的节点，因为如果unlce不存在，也就是说以g为根的路径上只能有g节点一个黑色节点，那a、b、c树如果存在的话它们的节点又应该是什么颜色的呢？都是红色吗？因此a、b、c树一定不存在，也就是说cur一定是新增节点。

        那如果uncle不存在的情况能不能通过更新颜色来进行规则控制呢？比如把p节点置黑，g节点置红，然后再向上更新。答案也是不行的。可以想象，如果按照这个方案执行的话，如果插入一个有序的数组，岂不是又变成了一个单支树了。

        我们回到单旋的操作，一共分成两步。1. 以g为根进行单旋。2.处理颜色。但是旋完之后我们不需要进行向上更新了，因为旋完的根p是一个黑色的节点。

4.2 双旋情况

        当g、p、cur三个节点不在同一边就要进行双旋

        先单旋p节点变成上面的单旋情况，然后再单旋，最后更改颜色。

5. 红黑树与AVL树的比较

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

6. 红黑树完整代码

        红黑树的删除代码也先欠着

//节点的颜色
enum color{RED,BLACK};
//红黑树节点的定义
template<class K, class V>
struct RBTNode
{
 
	RBTNode(const pair<K, V>& kv, color color = RED)
		: _kv(kv)
		, _left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
		, _col(color) 
	{}
 
	pair<K, V> _kv;
	RBTNode<K, V>* _left;
	RBTNode<K, V>* _right;
	RBTNode<K, V>* _parent;
	color _col;	//节点颜色
};
 
 
 
template<class K, class V>
class RBTree
{
	typedef RBTNode<K, V> Node;
 
public:
 
	//构造
	RBTree() = default;
	//拷贝构造
	RBTree(const RBTree<K, V>& t)
	{
		_root = Copy(t._root);
	}
 
	//赋值运算符重载
	void operator=(const RBTree<K, V>& t)
	{
		RBTree<K, V> new_t(t);
		std::swap(new_t._root, _root);
	}
 
	//析构
	~RBTree()
	{
		Destroy(_root);
		_root = nullptr;
	}
 
	void Destroy(Node* root)
	{
		if (root == nullptr)
			return;
		Destroy(root->_left);
		Destroy(root->_right);
		delete root;
	}
	Node* Copy(const Node* root)
	{
		if (root == nullptr)
			return nullptr;
		Node* newnode = new Node(root->kv);
		newnode->_left = Copy(root->_left);
		newnode->_right = Copy(root->_right);
 
		return newnode;
	}
 
 
 
	//插入
	bool Insert(const pair<K, V>& kv);
 
	//搜索
	Node* Find(const K& x);
 
	//中序遍历
	void InOrder()
	{
		_InOrder(_root);
		cout << endl;
	}
 
	//树的高度
	int Height()
	{
		return _Height(_root);
	}
 
	//统计节点总个数(插入时可能会有重复数据)
	int Size()
	{
		return _Size(_root);
	}
 
private:
 
	//左单旋
	void RotateL(Node* parent);
	//右单旋
	void RotateR(Node* parent);
 
 
	//中序遍历(子函数)
	void _InOrder(Node* root)
	{
		if (root == nullptr)
			return;
 
		_InOrder(root->_left);
		cout << root->_kv.first << ":" << root->_kv.second << endl;
		_InOrder(root->_right);
	}
 
	//树的高度
	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 _Size(Node* root)
	{
		return root == nullptr ? 0 : _Size(root->_left) + _Size(root->_right) + 1;
	}
 
private:
	Node* _root = nullptr;
};
 
 
 
 
 
//插入
template<class K, class V>
bool RBTree<K, V>::Insert(const pair<K, V>& kv)
{
	//链表为空特殊处理
	if (_root == nullptr)
	{
		_root = new Node(kv, 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 = new Node(kv);
	if (cur->_kv.first < parent->_kv.first)
	{
		parent->_left = cur;
		cur->_parent = parent;
	}
	else
	{
		parent->_right = cur;
		cur->_parent = parent;
	}
	//判断是否需要对树进行调整
	while (parent && parent->_col==RED)//如果父节点颜色为红需要调整
	{
		Node* grandparent = parent->_parent;
		if (parent == grandparent->_left)	//叔叔在右
		{
			Node* uncle = grandparent->_right;
			
			if (uncle && uncle->_col == RED)	//当叔叔存在且为红时
			{
				parent->_col = uncle->_col = BLACK;
				grandparent->_col = RED;
 
				cur = grandparent;
				parent = grandparent->_parent;
			}
			else	//叔叔为黑或不存在
			{
				if (cur == parent->_left)//三节点同在左，右单旋
				{
					RotateR(grandparent);
					parent->_col = BLACK;
					grandparent->_col = RED;
				}
				else	//p节点在g左，cue节点在p右，左右双旋
				{
					RotateL(parent);
					RotateR(grandparent);
					cur->_col = BLACK;
					grandparent->_col = RED;	
				}
				break;
			}
		}
		else	//叔叔在左
		{
			Node* uncle = grandparent->_left;
 
			if (uncle && uncle->_col == RED)	//当叔叔存在且为红时
			{
				parent->_col = uncle->_col = BLACK;
				grandparent->_col = RED;
 
				cur = grandparent;
				parent = grandparent->_parent;
			}
			else	//叔叔为黑或不存在
			{
				if (cur == parent->_right)//三节点同在右，左单旋
				{
					RotateL(grandparent);
					parent->_col = BLACK;
					grandparent->_col = RED;
				}
				else	//p节点在g右，cue节点在p左，右左双旋
				{
					RotateR(parent);
					RotateL(grandparent);
					cur->_col = BLACK;
					grandparent->_col = RED;
				}
				break;
			}
		}
	}
	_root->_col = BLACK;
	return true;
}
 
 
//搜索
template<class K, class V>
RBTNode<K, V>* RBTree<K, V>::Find(const K& x)
{
	Node* cur = _root;
	while (cur)
	{
		if (cur->_kv.first < x)
		{
			cur = cur->_right;
		}
		else if (cur->_kv.first > x)
		{
			cur = cur->_left;
		}
		else
		{
			return cur;
		}
	}
	return nullptr;
}
 
 
//左单旋
template<class K, class V>
void RBTree<K, V>::RotateL(Node* parent)
{
	Node* subR = parent->_right;
	Node* subRL = parent->_right->_left;
 
	//修改向下链接内容
	parent->_right = subRL;
	subR->_left = parent;
	//修改向上链接内容
	subR->_parent = parent->_parent;
	parent->_parent = subR;
	if (subRL)//防止该树点为空
	{
		subRL->_parent = parent;
	}
 
	//parent的parent向下链接
	Node* parentParent = subR->_parent;
	if (parentParent == nullptr)//整棵树的根
	{
		_root = subR;
	}
	else
	{
		if (parent == parentParent->_right)
		{
			parentParent->_right = subR;
		}
		else
		{
			parentParent->_left = subR;
		}
	}
}
 
//右单旋
template<class K, class V>
void RBTree<K, V>::RotateR(Node* parent)
{
	Node* subL = parent->_left;
	Node* subLR = subL->_right;
 
	//修改向下链接内容
	parent->_left = subLR;
	subL->_right = parent;
	//修改向上链接属性
	subL->_parent = parent->_parent;
	parent->_parent = subL;
	if (subLR)
	{
		subLR->_parent = parent;
	}
	//修改parentParent
	Node* parentParent = subL->_parent;
	if (parentParent == nullptr)
	{
		_root = subL;
	}
	else
	{
		if (parent == parentParent->_right)
		{
			parentParent->_right = subL;
		}
		else
		{
			parentParent->_left = subL;
 
		}
	}
}