C++数据结构红黑树全面分析

enum Color
{
	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;
	Color _color;

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

template<class K, class V>
class RBTree
{
	typedef RBTreeNode<K, V> Node;
public:
private:
	Node* _root = nullptr;
};

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

	// parent的右指向subR的左
	parent->_right = subRL;

	if (subRL) subRL->_parent = parent;

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

	if (ppNode == nullptr)
	{
		_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* subL = parent->_left;
	Node* subLR = subL->_right;

	// parent的左指向subL的右
	parent->_left = subLR;

	if (subLR) subLR->_parent = parent;

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

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

		subL->_parent = ppNode;
	}
}

pair<Node*, bool> Insert(const pair<K, V>& kv)
{
	if (_root == nullptr)
	{
		_root = new Node(kv, BLACK);// 根节点默认给黑
		return make_pair(_root, true);
	}

	Node* cur = _root;
	Node* parent = nullptr;

	while (cur)
	{
		parent = cur;
		if (kv.first < cur->_kv.first)
			cur = cur->_left;
		else if (kv.first > cur->_kv.first)
			cur = cur->_right;
		else
			return make_pair(nullptr, 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;
	}

	
	// 调整颜色
	// 情况一：p是红，g是黑，u存在且为红
	// 调整后的几种情况：
	// 1.如果g为根节点，把g的颜色改成黑，结束；
    	// 2.如果g不为根节点，
	//	a.g的父节点为黑，结束；
	//	b.g的父节点为红，迭代向上调整,继续判断是哪种情况（一和三）
	//	cur = grandfather;
	//  father = cur->father;
	//  这里不管cur是在p的左边还是右边，都是一样的，关心的是颜色而不是位置
	// 情况二：p是红，g是黑，u不存在/u为黑 cur p g 三个是一条直线
	// 调整方法（左边为例）：1.右单旋 2.把p改成黑，g改成红
	// a. u不存在时，cur必定是新增节点   
	// b. u存在时，cur必定是更新上来的节点
	// 情况三：p是红，g是黑，u不存在/u为黑 cur p g 三个是一条折线
	// 调整方法（左边为例）：1.p左单旋 2.g右单旋 3.把cur改成黑，g改成红
	// a. u不存在时，cur必定是新增节点   
	// b. u存在时，cur必定是更新上来的节点
	
	while (parent && parent->_color == RED)
	{
		Node* grandfather = parent->_parent;
		// 左边
		if (grandfather->_left == parent)
		{
			// 红黑色的条件关键看叔叔
			Node* uncle = grandfather->_right;
			// u存在且为红
			if (uncle && uncle->_color == RED)
			{
				// 调整 p和u改成黑，g改成红
				parent->_color = uncle->_color = BLACK;
				grandfather->_color = RED;

				// 迭代  向上调整
				cur = grandfather;
				parent = cur->_parent;
			}
			else// u存在为黑/u不存在
			{
				// 折线用一个左单旋处理 1.p左单旋 2.g右单旋 3.把cur改成黑，g改成红   cur p g 三个是一条折线
				if (cur == parent->_right)
				{
					RotateL(parent);
					swap(parent, cur);
				}
				// 直线 cur p g 把p改成黑，g改成红
				// 右单旋  有可能是第三种情况
				RotateR(grandfather);

				parent->_color = BLACK;
				grandfather->_color = RED;
			}
		}
		// uncle在左边
		else
		{
			Node* uncle = grandfather->_left;
			if (uncle && uncle->_color == RED)
			{
				parent->_color = uncle->_color = BLACK;
				grandfather->_color = RED;

				// 迭代  向上调整
				cur = grandfather;
				parent = cur->_parent;
			}
			else
			{
				// 折线用一个右单旋处理  g p cur  g变红p边黑
				if (cur == parent->_left)
				{
					RotateR(parent);
					swap(parent, cur);
				}

				// 直线 g p cur 把p改成黑，g改成红
				// 左单旋  有可能是第三种情况
				RotateL(grandfather);

				parent->_color = BLACK;
				grandfather->_color = RED;
			}
		}
	}

	_root->_color = BLACK;
	return Find(kv.first);
}

bool Erase(const K& key)
{
	// 如果树为空，删除失败
	if (_root == nullptr)
		return false;

	Node* parent = nullptr;
	Node* cur = _root;
	Node* delNode = nullptr;
	Node* delNodeParent = nullptr;
	while (cur)
	{
		// 小于往左边走
		if (key < cur->_kv.first)
		{
			parent = cur;
			cur = cur->_left;
		}
		else if (key > cur->_kv.first)
		{
			parent = cur;
			cur = cur->_right;
		}
		else
		{
			// 找到了，开始删除
			// 1.左右子树都为空 直接删除  可以归类为左为空
			// 2.左右子树只有一边为空  左为空，父亲指向我的右，右为空，父亲指向我的左  
			// 3.左右子树都不为空  取左子树最大的节点或右子树最小的节点和要删除的节点交换，然后再删除
			
			if (cur->_left == nullptr)
			{
				// 要删除节点为根节点时，直接把右子树的根节点赋值给——root
				// 根节点的话会导致parent为nullptr
				if (_root == cur)
				{
					_root = _root->_right;
					if (_root)
					{
						_root->_parent = nullptr;
						_root->_color = BLACK;
					}
					return true;
				}
				else
				{
					delNode = cur;
					delNodeParent = parent;
				}
			}
			else if (cur->_right == nullptr)
			{
				if (_root == cur)
				{
					_root = _root->_left;
					if (_root)
					{
						_root->_parent = nullptr;
						_root->_color = BLACK;
					}
					return true;
				}
				else
				{
					delNode = cur;
					delNodeParent = parent;
				}
			}
			else
			{
				// 找右子树中最小的节点
				Node* rightMinParent = cur;
				Node* rightMin = cur->_right;// 去右子树找
				while (rightMin->_left)
				{
					rightMinParent = rightMin;
					rightMin = rightMin->_left;
				}
				//swap(cur->_key, rightMin->_key);
				// 替代删除
				cur->_kv = rightMin->_kv;

				delNode = rightMin;
				delNodeParent = rightMinParent;
			}
			break;
		}
	}
	// 没找到
	if (cur == nullptr)
		return false;
	// 1.替代节点为红，直接删除（看上面）
	// 2.替代节点为黑（只能有一个孩子或两个孩子）
	// i)替代节点有一个孩子不为空（该孩子一定为红）,把孩子的颜色改成黑
	// ii)替代节点的两个孩子都为空
	cur = delNode;
	parent = delNodeParent;
	if (cur->_color == BLACK)
	{
		if (cur->_left)// 左孩子不为空
		{
			cur->_left->_color = BLACK;
		}
		else if (cur->_right)
		{
			cur->_right->_color = BLACK;
		}
		else// 替代节点的两个孩子都为空
		{
			while (parent)
			{
				// cur是parent的左
				if (cur == parent->_left)
				{
					Node* brother = parent->_right;
					// p为黑
					if (parent->_color == BLACK)
					{
						Node* bL = brother->_left;
						Node* bR = brother->_right;
						// SL和SR一定存在且为黑
						if (brother->_color == RED)// b为红，SL和SR都为黑  b的颜色改黑，p的颜色改红  情况a
						{
							RotateL(parent);
							brother->_color = BLACK;
							parent->_color = RED;

							// 没有结束，还要对cur进行检索
						}
						else if(bL && bR && bL->_color == BLACK && bR->_color == BLACK)// b为黑，孩子存在
						{
							// 且孩子也为黑  把brother改成红色，迭代 GP比GU小1  情况b
							brother->_color = RED;
							cur = parent;
							parent = parent->_parent;
						}
						// bL存在为红，bR不存在或bR为黑 情况e  右旋后变色转为情况d
						else if (bL && bL->_color == RED && (!bR || (bR && bR->_color == BLACK)))
						{
							RotateR(brother);
							bL->_color = BLACK;
							brother->_color = RED;
						}
						else if (bR && bR->_color == RED) // 右孩子为红，进行一个左旋，然后把右孩子的颜色改成黑色 情况d
						{
							RotateL(parent);
							swap(brother->_color, parent->_color);
							bR->_color = BLACK;
							break;
						}
						else
						{
							// cur p b 都是黑，且b无孩子，迭代更新
							// parent是红就结束
							brother->_color = RED;
							cur = parent;
							parent = parent->_parent;								
						}
					}
					// p为红  b一定为黑
					else
					{
						Node* bL = brother->_left;
						Node* bR = brother->_right;
						if (bL && bR && bL->_color == BLACK && bR->_color == BLACK)// b的孩子全为黑 情况c p变黑，b变红 结束
						{
							brother->_color = RED;
							parent->_color = BLACK;
							break;
						}
						// bL存在为红，bR不存在或bR为黑 情况e  右旋后变色转为情况d
						else if (bL && bL->_color == RED && (!bR || (bR && bR->_color == BLACK)))
						{
							RotateR(brother);
							bL->_color = BLACK;
							brother->_color = RED;
						}
						else if (bR && bR->_color == RED) // 右孩子为红，进行一个左旋，然后把右孩子的颜色改成黑色 情况d
						{
							RotateL(parent);
							//swap(brother->_color, parent->_color);
							brother->_color = parent->_color;
							parent->_color = BLACK;
							bR->_color = BLACK;
							break;
						}
						else// cur 为黑，p为红，b为黑  调整颜色，结束
						{
							parent->_color = BLACK;
							brother->_color = RED;
							break;
						}
					}
				}
				else
				{
					Node* brother = parent->_left;
					// p为黑
					if (parent->_color == BLACK)
					{
						Node* bL = brother->_left;
						Node* bR = brother->_right;
						// SL和SR一定存在且为黑
						if (brother->_color == RED)// b为红，SL和SR都为黑  b的颜色改黑，p的颜色改红  情况a
						{
							RotateR(parent);
							brother->_color = BLACK;
							parent->_color = RED;

							// 没有结束，还要对cur进行检索
						}
						else if (bL && bR && bL->_color == BLACK && bR->_color == BLACK)// b为黑，孩子存在
						{
							// 且孩子也为黑  把brother改成红色，迭代 GP比GU小1  情况b
							brother->_color = RED;
							cur = parent;
							parent = parent->_parent;
						}
						// 右孩子存在且为红，但左孩子不存在或为黑  情况e  右旋后变色转为情况d
						else if (bR && bR->_color == RED && (!bL || (bL && bL->_color == BLACK)))
						{
							RotateL(brother);
							brother->_color = RED;
							bR->_color = BLACK;
						}
						else if (bL && bL->_color == RED) // 左孩子为红，进行一个右旋，然后把左孩子的颜色改成黑色 情况d
						{
							RotateR(parent);
							swap(brother->_color, parent->_color);
							bL->_color = BLACK;
							break;
						}
						else
						{
							// cur p b 都是黑，且b无孩子，迭代更新
							// if (parent == _root) // p是根节点，把b变红 否则迭代
							brother->_color = RED;
							cur = parent;
							parent = parent->_parent;
						}
					}
					// p为红  b一定为黑
					else
					{
						Node* bL = brother->_left;
						Node* bR = brother->_right;
						if (bL && bR && bL->_color == BLACK && bR->_color == BLACK)// b的孩子全为黑 情况c p变黑，b变红 结束
						{
							brother->_color = RED;
							parent->_color = BLACK;
							break;
						}
						// 右孩子存在且为红，但左孩子不存在或为黑  情况e  右旋后变色转为情况d
						else if (bR && bR->_color == RED && (!bL || (bL && bL->_color == BLACK)))
						{
							RotateL(brother);
							brother->_color = RED;
							bR->_color = BLACK;
						}
						else if (bL && bL->_color == RED) // 左孩子为红，进行一个右旋，然后把左孩子的颜色改成黑色 情况d
						{
							RotateR(parent);
							// swap(brother->_color, parent->_color);
							brother->_color = parent->_color;
							parent->_color = BLACK;
							bL->_color = BLACK;
							break;
						}
						else// cur 为黑，p为红，b为黑  调整颜色，结束
						{
							parent->_color = BLACK;
							brother->_color = RED;
							break;
						}
					}
				}
			}

		}
	}
	delNodeParent = delNode->_parent;
	// 删除
	if (delNode->_left == nullptr)
	{
		if (delNodeParent->_left == delNode)
			delNodeParent->_left = delNode->_right;
		else
			delNodeParent->_right = delNode->_right;
		if (delNode->_right)// 右不为空，就让右节点的父指针指向delNodeParent
			delNode->_right->_parent = delNodeParent;
	}
	else
	{
		if (delNodeParent->_left == delNode)
			delNodeParent->_left = delNode->_left;
		else
			delNodeParent->_right = delNode->_left;
		if (delNode->_left)// 右不为空，就让右节点的父指针指向delNodeParent
			delNode->_left->_parent = delNodeParent;
	}

	delete delNode;
	delNode = nullptr;
	return true;
}

bool Find(const K& key)
{
	if (_root == nullptr)
		return false;

	Node* cur = _root;
	while (cur)
	{
		// 小于往左走
		if (key < cur->_kv.first)
		{
			cur = cur->_left;
		}
		// 大于往右走
		else if (key > cur->_kv.first)
		{
			cur = cur->_right;
		}
		else
		{
			// 找到了
			return true;
		}
	}

	return false;
}

bool IsValidRBTree()
{
	// 空树也是红黑树
	if (_root == nullptr)
		return true;
	// 判断根节点的颜色是否为黑色
	if (_root->_color != BLACK)
	{
		cout << "违反红黑树的根节点为黑色的规则" << endl;
		return false;
	}

	// 计算出任意一条路径的黑色节点个数
	size_t blackCount = 0;
	Node* cur = _root;
	while (cur)
	{
		if (cur->_color == BLACK)
			++blackCount;
		cur = cur->_left;
	}

	// 检测每条路径黑节点个数是否相同 第二个参数记录路径中黑节点的个数
	return _IsValidRBTree(_root, 0, blackCount);
}
bool _IsValidRBTree(Node* root, size_t k, size_t blackCount)
{
	// 走到空就判断该条路径的黑节点是否等于blackCount
	if (root == nullptr)
	{
		if (k != blackCount)
		{
			cout << "违反每条路径黑节点个数相同的规则" << endl;
			return false;
		}
		return true;
	}

	if (root->_color == BLACK)
		++k;
		
	// 判断是否出现了连续两个红色节点
	Node* parent = root->_parent;
	if (parent && root->_color == RED && parent->_color == RED)
	{
		cout << "违反了不能出现连续两个红色节点的规则" << endl;
		return false;
	}

	return _IsValidRBTree(root->_left, k, blackCount)
		&& _IsValidRBTree(root->_right, k, blackCount);
}

void TestRBTree()
{
	//srand((size_t)time(nullptr));
	RBTree<int, int> rbt;
	// int a[] = { 1,2,3,4,5,6,7,8,9,10,5,7,8,11,12,13 };
	// int a[] = { 16,3,7,11,9,26,18,14,15 };
	// int a[] = { 4,2,6,1,3,5,15,7,16,14 };
	// int a[] = { 10,9,8,7,6,5,4,3,2,1 };
	vector<int> a;
	for (size_t i = 0; i < 13; ++i)
	{
		// a.push_back(rand());
		a.push_back(i);
	}
	//int a[] = { 4,2,6,7,3,5 };
	
	for (auto e : a)
	{	
		int begin = clock();
		rbt.Insert(make_pair(e, e));
		int end = clock();
		cout << "插入数据 " << e << " 后：" << "树的高度：" << rbt.Height() << " 是否为红黑树：" << rbt.IsValidRBTree();
		cout << " 用时：" << end - begin << "ms" << endl;
	}
	cout << "-------------------------------------------------------" << endl;
	for (auto e : a)
	{
		int begin = clock();
		rbt.Erase(e);
		int end = clock();
		cout << "删除数据 " << e << " 后：" << "树的高度：" << rbt.Height() << " 是否为红黑树：" << rbt.IsValidRBTree();
		cout << " 用时：" << end - begin << "ms" << endl;
	}
	// cout << rbt.IsValidRBTree() << endl;
	// rbt.InOrder();
}