map和set(三)——红黑树

1、红黑树的概念及性质

1.1概念

概念：

红黑树是一种二叉搜索树，以颜色(Red or Black)互斥来限制每条路径不会比另外的路径长出两倍，来达到近似平衡

1.2性质

红黑树的性质：

1. 每个节点不是黑色就是红色
2. 根节点是黑色的
3. 如果一个节点是红色的，则它的两个孩子节点必须是黑色的(无连续的红节点)
4. 对于每个节点，从该节点到其所有的后代叶节点的简单路径上，均包含相同数目的黑节点(每条路径都包含相同数量的黑色节点)
5. 每个叶子节点都是黑色的(此叶子节点指的是NULL)

得知上面的有关红黑树的情况后，思考一个一个问题

它的性质如何保证最长路径不会超过最短路径的两倍？

考虑极端场景：

最短路径： 全黑                                最长路径：一直一黑一红

对比AVL树，高度是很接近logN

红黑树高度是很接近2*logN(红黑树搜索效率相对差一些，但几乎可以忽略不计)

但插入同样的数据，AVL树的高度更低，是通过多次旋转而得来的

2、红黑树的简单实现

2.1红黑树节点的定义

enum(枚举)里存的是节点的颜色

节点要有指向左节点、右节点、父节点的指针；节点存的值(数据)及节点的颜色

enum Colour
{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;Colour _col;RBTreeNode(const pair<K, V>& kv):_left(nullptr), _right(nullptr), _parent(nullptr), _kv(kv), _col(RED){}
};

初始化(构造)节点，三指针指向空；_kv(值or数据)取决于传的值，_col默认为红色

为什么(插入)节点的颜色默认为红色呢？

如果插入黑色节点就会破坏规则：每条路径上黑色节点的数量相同

所以(插入)节点的默认颜色为红色

2.2插入

以下为简写：

u uncle 叔叔

p parent 父亲

g grandfather 爷爷

c cur遍历节点(可能是新插入节点)

情况一：

u(叔叔)存在且为红

g必为黑，若为红早就违反没有连续两个红色节点的规则

此时c节点一定是新插入的节点，且c节点的插入破坏了没有连续的红色节点的规则，所以我们需要对这颗红黑树进行调整

把g的颜色改为红色，将p/u的颜色改为黑色

注意：

g节点可能为根节点

若g节点为根节点，那么再将g节点变黑(根节点的颜色必须为黑色)，所有路径的黑色节点+1，所有路径的黑色节点数依然相等

若g节点非根节点，那么只需要将g作为cur继续向上调整颜色

情况二 

叔叔不存在或叔叔存在且为黑

 若叔叔不存在

那么c节点一定是新插入节点，因为叔叔不存在，那么p父亲下面就不能再挂黑色节点了(往p下面挂p路径有黑色节点，而u却没有)，不然就会违反"所有路径的黑色节点数量都相等"这条规则

若叔叔存在且为黑

那么c节点一定不是新插入的节点，若c节点为新插入节点，则在插入c之前就会违反"所有路径黑色节点数量相同"这一规则(g和u都为黑而p却非黑，c为插入默认为红，不平衡了)；c不是新插入节点那么c节点下面一定有黑色节点对应黑色的u节点以达到平衡

 这时候我们就要用到之前AVL数所用的旋转了

叔叔不存在

叔叔存在且为黑

对g进行右旋(p为g的左、c为p的左)，然后将p改为黑色，g改为红色

 上面的情况都是基于c节点在p节点左子树(左孩子节点)的条件下

当cur在p节点的右边，情况又是怎样的呢？

叔叔不存在

叔叔存在且为黑

当p为g的左而c为p的右边，单纯的单选已经解决不了了

要先对p进行左单旋，在对g进行右单旋(对比上下两个图就知道，其实只多了一步)

 

以上的所有情况都是基于父亲在爷爷左边的基础上的，还有父亲在爷爷右边的几种情况，不过和上面的大差不差，我就不细讲了 

红黑树其本质还是二叉搜索树，红黑树的插入还是以二叉搜索树的插入为基础所更改的

大概可以分为两步：

1. 以二叉搜索树的方式插入新节点

2. 检测新节点插入后，红黑树的性质是否造到破坏(对其进行旋转或变色)

 代码

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); // 红色的//判断插入的节点该连接到父节点的左还是右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 (parent == grandfather->_left)//父亲在爷爷左{Node* uncle = grandfather->_right;// 情况一：叔叔存在且为红if (uncle && uncle->_col == RED){// 变色parent->_col = uncle->_col = BLACK;grandfather->_col = RED;// 继续往上处理cur = grandfather;parent = cur->_parent;}else{// 情况二：叔叔不存在或者存在且为黑// 旋转+变色if (cur == parent->_left){RotateR(grandfather);						//       gparent->_col = BLACK;						//    p    ugrandfather->_col = RED;					// c}else{RotateL(parent);RotateR(grandfather);						//        gcur->_col = BLACK;							//    p       ugrandfather->_col = RED;					//      c}break;}}else//父亲在爷爷右边{Node* uncle = grandfather->_left;// 情况一：叔叔存在且为红if (uncle && uncle->_col == RED){parent->_col = uncle->_col = BLACK;grandfather->_col = RED;cur = grandfather;parent = cur->_parent;}else{// 情况二：叔叔不存在或者存在且为黑if (cur == parent->_right){RotateL(grandfather);		//      gparent->_col = BLACK;		//   u     pgrandfather->_col = RED;	//            c}else{RotateR(parent);RotateL(grandfather);						//		 gcur->_col = BLACK;							//  u        pgrandfather->_col = RED;					//          c}break;}}}_root->_col = BLACK;return true;
}

左旋右旋的代码

void RotateL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;parent->_right = subRL;if (subRL)subRL->_parent = parent;subR->_left = parent;Node* ppnode = parent->_parent;parent->_parent = subR;if (parent == _root){_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->_left = subLR;if (subLR)subLR->_parent = parent;subL->_right = parent;Node* ppnode = parent->_parent;parent->_parent = subL;if (parent == _root){_root = subL;subL->_parent = nullptr;}else{if (ppnode->_left == parent){ppnode->_left = subL;}else{ppnode->_right = subL;}subL->_parent = ppnode;}}

 

2.3红黑树的验证

红黑树的检测分为两步：

1. 检测其是否满足二叉搜索树(中序遍历是否为有序序列)

2. 检测其是否满足红黑树的性质

一般写验证的话要跟他的性质反着来，比如根节点的颜色是黑色的，那么如果根节点的颜色为红色就返回false

具体性质可以列为以下三条

根节点颜色为黑色

没有连续的红色节点

所有路径的黑色节点数量相同

根节点颜色为黑色已经讲过了

没有连续的红色节点可以在走中序的同时判断，(cur为遍历节点)若cur的颜色为红色且cur的parent的颜色也为红色那么返回false

至于所有路径的黑色节点数量相同

可以先统计一下最左路径黑色节点的数量作为参考值，然后如果有哪条路径的黑色节点数量不等于这个参考值的话就返回false

bool IsValidRBTRee()
{if (_root && _root->_col == RED){return false;}int refBlackNum = 0;//黑节点参考值Node* cur = _root;while (cur){if (cur->_col == BLACK){refBlackNum++;}cur = cur->_left;}return _IsValidRBTRee(_root, 0, refBlackNum);
}bool _IsValidRBTRee(Node* cur, size_t blackCount, size_t refBlack)
{if (cur == nullptr){if (refBlack != blackCount){cout << "黑色节点不相等" << endl;return false;}return true;}if (cur->_col == RED && cur->_parent->_col == RED){cout << "存在连续红色节点" << endl;return false;}if (cur->_col == BLACK)blackCount++;return _IsValidRBTRee(cur->_left, blackCount, refBlack)&& _IsValidRBTRee(cur->_right, blackCount, refBlack);
}

3.全部代码

#pragma once
enum Colour
{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;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 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); // 红色的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 (parent == grandfather->_left){Node* uncle = grandfather->_right;// 情况一：叔叔存在且为红if (uncle && uncle->_col == RED){// 变色parent->_col = uncle->_col = BLACK;grandfather->_col = RED;// 继续往上处理cur = grandfather;parent = cur->_parent;}else{// 情况二：叔叔不存在或者存在且为黑// 旋转+变色if (cur == parent->_left){RotateR(grandfather);						//       gparent->_col = BLACK;						//    p    ugrandfather->_col = RED;					// c}else{RotateL(parent);RotateR(grandfather);						//        gcur->_col = BLACK;							//    p       ugrandfather->_col = RED;					//      c}break;}}else{Node* uncle = grandfather->_left;// 情况一：叔叔存在且为红if (uncle && uncle->_col == RED){parent->_col = uncle->_col = BLACK;grandfather->_col = RED;cur = grandfather;parent = cur->_parent;}else{// 情况二：叔叔不存在或者存在且为黑if (cur == parent->_right){RotateL(grandfather);		//      gparent->_col = BLACK;		//   u     pgrandfather->_col = RED;	//            c}else{RotateR(parent);RotateL(grandfather);						//		 gcur->_col = BLACK;							//  u        pgrandfather->_col = RED;					//          c}break;}}}_root->_col = BLACK;return true;}/*获取红黑树最左侧节点*/Node* LeftMost(){Node* cur = _root;if (cur == nullptr ){return _root;}while (cur->_left){cur = cur->_left;}return cur;}// 获取红黑树最右侧节点Node* RightMost(){Node* cur = _root;if (nullptr == cur){return _root;}while (cur->_right){cur = cur->_right;}return cur;}// 检测红黑树是否为有效的红黑树，注意：其内部主要依靠_IsValidRBTRee函数检测bool IsValidRBTRee(){if (_root && _root->_col == RED){return false;}int refBlackNum = 0;//黑节点参考值Node* cur = _root;while (cur){if (cur->_col == BLACK){refBlackNum++;}cur = cur->_left;}return _IsValidRBTRee(_root, 0, refBlackNum);}void InOrder(){_InOrder(_root);cout << endl;}void _InOrder(Node* root){if (root == nullptr)return;_InOrder(root->_left);cout << root->_kv.first<<" ";_InOrder(root->_right);}void RotateL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;parent->_right = subRL;if (subRL)subRL->_parent = parent;subR->_left = parent;Node* ppnode = parent->_parent;parent->_parent = subR;if (parent == _root){_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->_left = subLR;if (subLR)subLR->_parent = parent;subL->_right = parent;Node* ppnode = parent->_parent;parent->_parent = subL;if (parent == _root){_root = subL;subL->_parent = nullptr;}else{if (ppnode->_left == parent){ppnode->_left = subL;}else{ppnode->_right = subL;}subL->_parent = ppnode;}}bool _IsValidRBTRee(Node* cur, size_t blackCount, size_t refBlack){if (cur == nullptr){if (refBlack != blackCount){cout << "黑色节点不相等" << endl;return false;}return true;}if (cur->_col == RED && cur->_parent->_col == RED){cout << "存在连续红色节点" << endl;return false;}if (cur->_col == BLACK)blackCount++;return _IsValidRBTRee(cur->_left, blackCount, refBlack)&& _IsValidRBTRee(cur->_right, blackCount, refBlack);}
private:Node* _root = nullptr;
};void TestRBTree1()
{int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16,10,12};RBTree<int,int> t;for (auto e : a){t.Insert(make_pair(e, e));}t.InOrder();cout << t.IsValidRBTRee() << endl;
}