C++笔记19•数据结构:红黑树(RBTree)•

红黑树

1.简介：

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

• 当搜索二叉树退化为单支树时，搜索效率极低，为了使搜索效率高，建立平衡搜索二叉树就需要"平衡树"来解决。上一篇博客介绍了AVL树，这篇博客介绍的红黑树和AVLTree作用是一样的。
• 如果在一棵原本是平衡的树中插入一个新节点，可能造成不平衡，此时必须调整树的结构，使之平衡化，用AVLTree或RBTree。
• RBTree相对AVLTree效果略微差一些，但是相比AVLTree实现更简单一些，不需要平衡因子的不断更新，而是用红&黑颜色替代，只用到了左单旋和右单旋（RBTree的双旋是调用左单旋和右单旋），现在的硬件设备运转非常快，CUP的高速运转下RBTree与AVLTree的差别已经显得微不足道。关联式容器map/set的底层就是用RBTree实现的。
• 性质： 1. 每个结点不是红色就是黑色 2. 根节点是黑色的  3. 如果一个节点是红色的，则它的两个孩子结点是黑色的 ( 没有连续的红节点) 4. 对于每个结点，从该结点到其所有后代叶结点的简单路径上，均 包含相同数目的黑色结点  5. 每个叶子结点都是黑色的 ( 此处的叶子结点指的是空结点)

满足以上性质就可以保证：最长路径中节点的个数不会超过最短路径节点个数的两倍。

总结一下：RBTree(①根是黑的②没有连续的红节点③每条路径有相同数量的黑节点)

举例：

做个比方，假设上面的图，最短路径是：全黑 时间复杂度（log（N））     

                                           最长路径是：一黑一红，时间复杂度（2*log（N）） 

                                           所以最多是2倍。

现在的硬件设备运转非常快，log（N）和2*log（N）对CPU来处理真的很快。比如N=10亿，log（10亿）大概等于30；2*log（10亿）大概等于60；最短路径需要搜索30次，最短路径需要搜索60次，这对CPU来处理真的是不值一提的，所以说不管在最短或者最长路径上搜索数据，都是非常快的。

•  红黑树是近似平衡,高度控制没有AVL树那么严格，增删查改的性能基本差不多。
• 红黑树高度可能会高一些，但是它旋转得少一些。实际中红黑树综合而言更优一点，实际中红黑树用得更多。

 2.代码实现

#define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
#include <string>
#include <assert.h>
using namespace std;

//平衡搜索树 RBTree
//1. 每个结点不是红色就是黑色
//2. 根节点是黑色的 
//3. 如果一个节点是红色的，则它的两个孩子结点是黑色的(意思就是红色节点不能连续)
//4. 对于每个结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数目的黑色结点 
//5. 每个叶子结点都是黑色的(此处的叶子结点指的是空结点)

enum Colour
{
	RED,
	BLACK,
};

template<class K, class V>
struct RBTreeNode
{
	RBTreeNode<K, V>* _left;//一定不要写成RBTreeNode*<K>  _left;  这样编译器无法识别
	RBTreeNode<K, V>* _right;
	RBTreeNode<K, V>* _parent;
	pair<K, V> _kv;
	Colour _col;

	RBTreeNode(const pair<K, V>& kv)
		:_left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
		, _kv(kv)
		, _col(RED)//新插入的节点颜色默认设置为红色，原因是针对红黑树的组建规则，红色限制少,但是根节点必须是黑色。
	{}
};

template<class K, class V>
class RBTree
{
	typedef struct RBTreeNode<K, V> Node;
public:
	bool insert(const pair<K, V>& kv)
	{
		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;

		//对RBTree进行颜色节点排查  检查是否存在连续的红色节点
		while (parent && parent->_col == RED)
		{
			Node* grandfater = parent->_parent;
			assert(grandfater);
			
			if (parent == grandfater->_left)
			{
				Node* uncle = grandfater->_right;

				//情况一：叔叔节点存在且颜色为红
				if (uncle && uncle->_col == RED)//叔叔节点存在且颜色为红
				{
					//变色：父亲和叔叔变黑，爷爷变红；
					parent->_col = BLACK;
					uncle->_col = BLACK;
					grandfater->_col = RED;

					//继续向上搜索
					cur = grandfater;
					parent = cur->_parent;
				}

				//情况二：叔叔节点不存在 或 叔叔节点存在且颜色为黑
				//(1)如果叔叔不存在，那么cur就是新增节点
				//(2)如果叔叔存在且颜色为黑，那么cur一定不是新增节点。

				else
				{
					if (cur == parent->_left)
					{
						//     右单旋
						//     grandfater
						//      /
						//   parent        ->    parent 
						//   /                    /  \
						// cur                  cur   grandfater
						RotateR(grandfater);
						parent->_col = BLACK;
						grandfater->_col = RED;
						//不用再向上搜索
					}
					else  //cur == parent->_right
					{
						//双旋
						//     g                  g              
						//   p        ->        c      ->       c
						//     c              p              p    g
						RotateL(parent);
						RotateR(grandfater);
						cur->_col = BLACK;
						grandfater->_col = RED;
					}
					break;
				}
			}
		

			else //parent == grandfater->_right
			{
				Node* uncle = grandfater->_left;

				//情况一：叔叔节点存在且颜色为红
				if (uncle&& uncle->_col == RED)//叔叔节点存在且颜色为红
				{
					//变色：父亲和叔叔变黑，爷爷变红；
					parent->_col = BLACK;
					uncle->_col = BLACK;
					grandfater->_col = RED;

					//继续向上搜索
					cur = grandfater;
					parent = cur->_parent;
				}

				//情况二：叔叔节点不存在 或 叔叔节点存在且颜色为黑
				//(1)如果叔叔不存在，那么cur就是新增节点
				//(2)如果叔叔存在且颜色为黑，那么cur一定不是新增节点。

				else
				{
					if (cur == parent->_right)
					{
						//     左单旋
						//     grandfater
						//         \
						//        parent        ->     parent 
						//            \                /     \
						//             cur        grandfater  cur 
						RotateL(grandfater);
						parent->_col = BLACK;
						grandfater->_col = RED;
						//不用再向上搜索
					}
					else  //cur == parent->_left
					{
						//双旋
						//     g                  g              
						//       p        ->        c      ->       c
						//     c                     p            g   p
						RotateR(parent);
						RotateL(grandfater);
						cur->_col = BLACK;
						grandfater->_col = RED;
					}
					break;
				}
			}
		}
		_root->_col = BLACK;

		return true;
	}
	void InOrder()
	{
		_InOrder(_root);
		cout << endl;
	}

	void Height()
	{
		cout << "最长路径:" << _maxHeight(_root) << endl;
		cout << "最短路径:" << _minHeight(_root) << endl;
	}


	bool IsBalanceTree()
	{
		// 检查红黑树几条规则

		Node* pRoot = _root;
		// 空树也是红黑树
		if (nullptr == pRoot)
			return true;

		// 检测根节点是否满足情况
		if (BLACK != pRoot->_col)
		{
			cout << "违反红黑树性质二：根节点必须为黑色" << endl;
			return false;
		}

		// 获取任意一条路径中黑色节点的个数 -- 比较基准值
		size_t blackCount = 0;
		Node* pCur = pRoot;
		while (pCur)
		{
			if (BLACK == pCur->_col)
				blackCount++;

			pCur = pCur->_left;
		}

		// 检测是否满足红黑树的性质，k用来记录路径中黑色节点的个数
		size_t k = 0;
		return _IsValidRBTree(pRoot, k, blackCount);
	}

private:
	Node* _root=nullptr;
	void _InOrder(Node* root)
	{
		if (root == nullptr)
		{
			return;
		}
		_InOrder(root->_left);
		cout << root->_kv.first << ":" << root->_kv.second<<endl;
		_InOrder(root->_right);
	}

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

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

		subR->_left = parent;
		parent->_parent = subR;

		if (parent == _root)
		{
			_root = subR;
			_root->_parent = nullptr;//subR->_parent = nullptr; //不可以只写这一句  如果parent是根 必须要更新_root; 加上 _root = subR;
		}
		else
		{
			if (parent == ppNode->_left)
			{
				ppNode->_left = subR;
			}
			else  //parent == ppNode->_right
			{
				ppNode->_right = subR;
			}
			subR->_parent = ppNode;
		}

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

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

		subL->_right = parent;
		parent->_parent = subL;

		if (parent == _root)
		{
			_root = subL;
			_root->_parent = nullptr;//subR->_parent = nullptr; //不可以只写这一句  如果parent是根 必须要更新_root; 加上 _root = subR;
		}
		else
		{
			if (parent == ppNode->_left)
			{
				ppNode->_left = subL;
			}
			else  //parent == ppNode->_right
			{
				ppNode->_right = subL;
			}
			subL->_parent = ppNode;
		}

	}

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

		int lh = _maxHeight(root->_left);
		int rh = _maxHeight(root->_right);

		return lh > rh ? lh + 1 : rh + 1;
	}

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

		int lh = _minHeight(root->_left);
		int rh = _minHeight(root->_right);

		return lh < rh ? lh + 1 : rh + 1;
	}


	bool _IsValidRBTree(Node* pRoot, size_t k, const size_t blackCount)
	{
		//走到null之后，判断k和black是否相等
		if (nullptr == pRoot)
		{
			if (k != blackCount)
			{
				cout << "违反性质四：每条路径中黑色节点的个数必须相同" << endl;
				return false;
			}
			return true;
		}

		// 统计黑色节点的个数
		if (BLACK == pRoot->_col)
			k++;

		// 检测当前节点与其双亲是否都为红色
		if (RED == pRoot->_col && pRoot->_parent && pRoot->_parent->_col == RED)
		{
			cout << "违反性质三：存在连在一起的红色节点" << endl;
			return false;
		}

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

void TestAVLTree1()
{
	//int a[] = {10, 1, 2, 3, 4, 5, 6, 7, 8,9 };
	int a[] = { 40,50,30,29,28,27,0,26,25,24,11,8,7,6,5,4,3,2,1 };
	RBTree<int, int> t;
	for (auto e : a)
	{
		t.insert(make_pair(e, e));
	}
	t.InOrder();
	cout << t.IsBalanceTree() << endl;
}
void TestAVLTree2()
{
	int a[] = { 30,29,28,27,26,25,24,11,8,7,6,5,4,3,2,1 };
	RBTree<int, int> t;
	for (auto e : a)
	{
		bool res = t.insert(make_pair(e, e));
		if (res)
		{
			cout << "Inserted: " << e << endl;
		}
		else
		{
			cout << "Failed to insert: " << e << endl;
		}
	}
	t.InOrder();
	cout << t.IsBalanceTree() << endl;

}


int main()
{
	TestAVLTree1();
	//TestAVLTree2();
	return 0;
}