红黑树插入的实现

前面我们已经实现了搜索二叉树树，知道了其查找规则；实现了AVL树，知道了他的旋转规则；今天这篇红黑树，是解决搜索二叉树退化成单链情况的另一种方法，以插入为重点。

---

目录

红黑树的性质

性质

实现

结点构造

插入实现 

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

情况二: cur，p为红，g为黑，u不存在/u为黑--- g p cur在一条直线上

情况三: cur，p为红，g为黑，u不存在/u为黑--- g p cur不在一条直线上

代码实现

---

红黑树的性质

红黑树顾名思义，他的结点不是红的就是黑的；他通过结点的颜色和性质来保证了他的规则：

红黑树确保没有一条路径会比其他路径长出俩倍

性质

1. 结点颜色不是红色就是黑色，根节点是黑色的

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

3. 从任意一个结点开始的所有路径上，均包含相同数目的黑色结点

4. 每个叶子结点都是黑色的(此处的叶子结点指的是空结点)

实现

结点构造

AVL树中结点包含平衡因子，而红黑树包含的是结点的颜色。

enum Colour
{
	RED,
	BLACK,
};
 
template <class K,class V>
struct RBTreeNode
{
	RBTreeNode* _left;
	RBTreeNode* _right;
	RBTreeNode* _parent;
	pair _kv;
 
	Colour _col;
	RBTreeNode(const pair& kv)
		:_kv(kv)
		, _left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
		, _col(RED)
	{}
};

插入实现 

接着是插入的实现，插入时要保证树的结构尽可能地受到地破坏最小，如果插入黑色结点的话，每条路径上地黑色结点数会不相同，影响整棵树，因此插入时应控制插入的结点为红色结点。

插入主要以父亲和叔叔的颜色做为判断标志

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

遇到上述这种情况时，此树可能是一颗完整的树，也可能只是一颗子树。

a b c d 可能是子树也可能为空。

如果父亲p和叔叔u都为红色，那么将 p u 都变成黑色，此时从g开始，左右两条路径的黑结点各自增加一个，每条路径黑结点相同，只是相对于这是一颗完整的树而言。

如果这个树是子树，只保证了子树中每条路径黑结点相同，要保证整棵树每条路径下的黑色结点相同，我们要将祖父结点g变成红色。

无论是完整的树还是子树，g变红不会影响每条路径的黑色结点相同的情况；

再循环判断g是否为根：为根，将g的颜色变黑色，因为根节点必须是黑色；不为根，那么将g变为cur，继续往上查看是否有红色结点相连的情况

情况二: cur，p为红，g为黑，u不存在/u为黑--- g p cur在一条直线上

当出现左图情况时，cur 一定不是新插入的结点，因为要保证每条路径黑色结点相同，cur 原来一定为黑色，可能是cur的子树 a或者b 有连续的红色结点，颜色依次网上更新，将cur变成了红色节点。

如果 u 不存在，为了保证每条路径黑色结点相同，g 的右子树只要g一个黑色结点，为了保证左子树也有g一个黑色结点，cur 本身只能为新增的红色结点。

如上述情况，是左边连续红色结点，u 是黑色，为维护红黑树结构，这里以g为旋转点，进行右单旋，最后将p变为黑色，g变为红色即可。

上图是左单边为连续红色，遇到右单边为连续红色，对g进行左单旋即可，最后将p变为黑色，g变为红色。

情况三: cur，p为红，g为黑，u不存在/u为黑--- g p cur不在一条直线上

当遇到最左边这样的情况时，需要进行两次旋转，先以p为旋转点，进行左单旋；最后以g为旋转点，进行右单旋，最后将cur变为黑色，g变为红色即可；

如果p在g的右边，cur在p的左边，则先以p为旋转点进行右单旋，再以g为旋转点进行左单旋即可。

代码实现

template <class K,class V>
class RBTree
{
	typedef RBTreeNode Node;
public:
 
	bool Insert(const pair& kv)
	{
		//1. 按照搜索树的规则插入
		//2. 看是否违反平衡规则，违反则旋转
		//3. 红黑树根节点是黑色
 
		//空树时
		if (_root == nullptr)
		{
			_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 = new Node(kv);
		cur->_col = RED;
		if (parent->_kv.first < kv.first)
		{
			parent->_right = cur;
		}
		else
		{
			parent->_left = cur;
		}
 
		cur->_parent = parent;  //注意结点的更新
 
		//存在连续红色结点
		while (parent &&parent->_col == RED)
		{
			Node* grandfather = parent->_parent;
			if (grandfather->_left == parent)         //找叔叔
			{
				Node* uncle = grandfather->_right;    //叔叔在右边的前提下
 
				//情况1---叔叔颜色为红色
				if (uncle && uncle->_col == RED)
				{
					parent->_col = uncle->_col = BLACK;
					grandfather->_col = RED;
					
					//可能是子树--继续向上处理
					cur = grandfather;
					parent = cur->_parent;
				}
				else   //叔叔存在且为黑或者叔叔不存在
				{
 
                    //情况二，g p cur在一条直线上
					if (cur == parent->_left)
					{
						RotateR(grandfather);
						parent->_col = BLACK;
						grandfather->_col = RED;
					}
                       
                    //情况三: g p cur不在一条直线上，双旋--先左单旋，再右单旋
					else   
					{
						RotateL(parent);
						RotateR(grandfather);
						cur->_col = BLACK;
						grandfather->_col = RED;
					}
					break;
				}
			}
			else                                        //叔叔在左边的前提下
			{
				Node* uncle = grandfather->_left;
 
				//情况1---叔叔颜色为红色
				if (uncle && uncle->_col == RED)
				{
					parent->_col = uncle->_col = BLACK;
					grandfather->_col = RED;
 
					//可能是子树--继续向上处理
					cur = grandfather;
					parent = cur->_parent;
				}
              
                //情况二，g p cur都在右侧
				else
				{
					// g
					//   p
					//    c
					if (cur == parent->_right)
					{
						RotateL(grandfather);
						parent->_col = BLACK;
						grandfather->_col = RED;
					}
  
                    //情况三--不在一条线上，需要双旋
					else
					{
						//   g
						//     p
						//   c
						RotateR(parent);
						RotateL(grandfather);
						cur->_col = BLACK;
						grandfather->_col = RED;
					}
					break;
				}
			}
 
		}
		
 
		_root->_col = BLACK;     //最后的时候根变为黑色即可·、
		return true;
	}
 
 
 
 
private:
	//右单旋
	void RotateR(Node* parent)
	{
		Node* subL = parent->_left;
		Node* subLR = subL->_right;
 
		parent->_left = subLR;
		if (subLR)
			subLR->_parent = parent;
 
		Node* ppNode = parent->_parent;
 
		subL->_right = parent;
		parent->_parent = subL;
 
		if (parent == _root)
		{
			_root = subL;
			_root->_parent = nullptr;
		}
		else
		{
			if (parent == ppNode->_left)
			{
				ppNode->_left = subL;
			}
			else
			{
				ppNode->_right = subL;
			}
 
			subL->_parent = ppNode;
		}
 
	}
 
	//左单旋
	void RotateL(Node* parent)
	{
		Node* subR = parent->_right;
		Node* subRL = subR->_left;
 
		parent->_right = subRL;
		if (subRL)
			subRL->_parent = parent;
 
		Node* ppNode = parent->_parent;
 
		subR->_left = parent;
		parent->_parent = subR;
 
		if (parent == _root)
		{
			_root = subR;
			_root->_parent = nullptr;
		}
		else
		{
			if (parent == ppNode->_left)
			{
				ppNode->_left = subR;
			}
			else
			{
				ppNode->_right = subR;
			}
 
			subR->_parent = ppNode;
		}
 
	}
 
	Node* _root = nullptr; 
};