【高阶数据结构】红黑树

1.红黑树的概念

2.红黑树的性质

3.红黑树的定义

4.红黑树的插入操作

1. 按照二叉搜索的树规则插入新节点

2. 检测新节点插入后，红黑树的性质是否造到破坏

5.红黑树的验证

6 红黑树与AVL树的比较

1.红黑树的概念

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

2.红黑树的性质

每个结点不是红色就是黑色
根节点是黑色的
如果一个节点是红色的，则它的两个孩子结点是黑色的
对于每个结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数目的黑色结点
每个叶子结点都是黑色的(此处的叶子结点指的是空结点)

思考：为什么满足上面的性质，红黑树就能保证：其最长路径中节点个数不会超过最短路径节点个数的两倍？

3.红黑树的定义

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

思考：在节点的定义中，为什么要将节点的默认颜色给成红色的？

4.红黑树的插入操作

红黑树是在二叉搜索树的基础上加上其平衡限制条件，因此红黑树的插入可分为两步：

1. 按照二叉搜索的树规则插入新节点

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;cur->_parent = parent;//优先插入红色节点，因为黑色节点要求每条路径上都相同，插入黑色会影响全局if (parent->_kv.first < kv.first){parent->_right = cur;}else{parent->_left = cur;}//判断是否插入成功//不符合红黑树性质需要调整}

2. 检测新节点插入后，红黑树的性质是否造到破坏

因为新节点的默认颜色是红色，因此：如果其双亲节点的颜色是黑色，没有违反红黑树任何性质，则不需要调整；但当新插入节点的双亲节点颜色为红色时，就违反了性质三不能有连在一起的红色节点，此时需要对红黑树分情况来讨论：

约定:cur为当前节点，p为父节点，g为祖父节点，u为叔叔节点

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

注意：此处所看到的树，可能是一棵完整的树，也可能是一棵子树

如果g是根节点，调整完成功后，需要将g改为黑色

如果g是子树，g一定有双亲，且g的双亲如果是红色，需要继续向上调整

解决方式：将p,u改为黑，g改为红，然后把g当成cur，继续向上调整。

情况二：cur为红，p为红，g为黑，u不存在/u存在且为黑

说明: u的情况有两种

如果u节点不存在，则cur一定是新插入节点，因为如果cur不是新插入节点，则cur和p一定有一个节点的颜色是黑色，就不满足性质4:每条路径黑色节点个数相同。
如果u节点存在，则其一定是黑色的，那么cur节点原来的颜色一定是黑色的，现在看到其是红色的原因是因为cur的子树在调整的过程中将cur节点的颜色由黑色改成红色。

旋转

p为g的左孩子，cur为p的左孩子，则进行右单旋转;
相反，p为g的右孩子，cur为p的右孩子，则进行左单旋转p、g变色--p变黑，g变红

情况三: cur为红，p为红，g为黑，u不存在/u存在且为黑

p为g的左孩子，cur为p的右孩子，则针对p做左单旋，再对g做右单旋。
相反，p为g的右孩子，cur为p的左孩子，则针对p做右单旋，再对g做左单旋。

针对每种代码处理的代码：

        //插入红色，如果父亲是黑色，插入成功//父亲是红色，那么存在连续的红色，违反规则，需要处理while (parent && parent->_col == RED){//关键看叔叔 uncle //cur红 parent红 grandfather黑 三个颜色是固定的//    g//  f   u// c//parent红色，一定不是根，有父亲Node* grandfather = parent->_parent;if (parent == grandfather->_left){//    g//  f   u// cNode* uncle = grandfather->_right;if (uncle && uncle->_col == RED)//变色{uncle->_col = parent->_col = BLACK;grandfather->_col = RED;//继续往上处理cur = grandfather;parent = cur->_parent;//if (parent == nullptr)//{//	grandfather->_col = BLACK;//是根节点，这里放在了最后处理//	break;//}}else //uncle不存在（新插入的是cur），或为黑（cur是调整上来的）{if (cur == parent->_left)//右单旋{RotateR(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else //左右双旋{//   g// p     c//   cRotateL(parent);RotateR(grandfather);grandfather->_col = RED;cur->_col = BLACK;}break;}}else{Node* uncle = grandfather->_left;//   g// u   f//       cif (uncle && uncle->_col == RED)//变色{uncle->_col = parent->_col = BLACK;grandfather->_col = RED;//继续往上处理cur = grandfather;parent = cur->_parent;}else //uncle不存在（新插入的是cur），或为黑（cur是调整上来的）{if (cur == parent->_right)//左单旋{RotateL(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else //右左双旋{//   g// u   p//    cRotateR(parent);RotateL(grandfather);cur->_col = BLACK; grandfather->_col = RED;}break;}}}_root->_col = BLACK;return true;

5.红黑树的验证

红黑树的检测分为两部分，检测其是否满足红黑树的性质：

判断每条路径黑色节点是狗相同
判断是否存在连续的红色节点

bool Check(Node* root, int blacknum, const int refVal){if (root == nullptr){if (refVal != blacknum){cout << "黑色节点不相同的路径" << endl;return false;}return true;}//检查红色节点的父亲if (root->_parent && (root->_col == RED && root->_parent->_col == RED)){cout << "有连续红色节点" << endl;return false;}if (root->_col == BLACK){blacknum++;}return Check(root->_left, blacknum, refVal) && Check(root->_right, blacknum, refVal);}bool IsBalance(){if (_root == nullptr){return true;}if (_root->_col == RED){return false;}int refVal = 0;Node* cur = _root;while (cur){if (cur->_col == BLACK){refVal++;}cur = cur->_left;}int blacknum = 0;return Check(_root, blacknum, refVal);}