封装map和set所需第二步：红黑树

1.红黑树的规则

1.每个结点只有黑或红色

2.根结点只为黑色

3.红节点的两孩子只为黑色

4.所有节点的绝对路径的黑色节点数都相同（绝对路径：从根节点到每一个子节点的过程）

2.红黑树的一些特点

1.设每一条路径有x个黑色结点，有最短路径为x,最长路径为x*2。

下图为最长：

下图为最短：

设N为该树的所有节点数，x为最短路径，有2^x-1 <=N<=2^(x+1)-1.即n=logN.可得一次查找的效率还是为O(logN).

下面开始代码实现：
1.结点和大框

//枚举封装颜色 enum { RED, BLACK }; template<class K, class V> struct RBTreeNode { RBTreeNode* _left; RBTreeNode* _right; RBTreeNode* _parent; pair<K, V> _val; int _col; RBTree(const pair<K, V>& val) :_val(val) ,_left(nullptr) ,_right(nullptr) ,_parent(nullptr) //结点颜色优先为红色 //因为违反条件4的代价很大 ,_col(RED) { } }; template<class K, class V> class RBTree { public: typedef RBTreeNode<K, V> Node; private: Node* _root = nullptr; };

2.出现矛盾时的修改

如上图出现矛盾时，我们将新插的节点为cur,其父亲为parent,父亲的父亲为grandparent,grandparent的另一个孩子为uncle。

当cur与parent的颜色出现矛盾时，grandparent的颜色一定为黑色，此时uncle的颜色就极为重要。

1.uncle为红色

解法：

（cur可能是新节点也可能是从下面更新出来的）

这些情况下只需将parent和uncle更新为black,grandparent更新为red。然后将cur去到grandparent处向上更新即可。（可能grandparent为红后与其的祖父又发生了矛盾）

代码：（说白了，红黑树与AVL树的差别只有insert是不同的）

bool insert(const pair<K, V>& val) { if (_root == nullptr) { _root = new Node(val); _root->_col = BLACK; return true; } Node* cur = _root; Node* parent = nullptr; while (cur) { if (cur->_val.first < val.first) { parent = cur; cur = cur->_right; } else if (cur->_val.first > val.first) { parent = cur; cur = cur->_left; } else { return false; } } //此处走到空结点 cur = new Node(val); //连接parent和cur if (parent->_val.first < val.first) { parent->_right = cur; } else { parent->_left = cur; } cur->_parent = parent; //parent==nulptr代表走到_root了 while (parent && parent->_col == RED) { Node* grandparent = parent->_parent; //这里核心是用于限定uncle在grandparent的左还是右的 if (grandparent->_left == parent) { Node* uncle = grandparent->_right; //uncle==nullptr为其它情况 if (uncle && uncle->_col == RED) { uncle->_col = parent->_col = BLACK; grandparent->_col = RED; cur = grandparent; parent = grandparent->_parent; } else { if (parent->_left == cur) { rotateR(grandparent); parent->_col = BLACK; grandparent->_col = RED; } else { rotateL(parent); rotateR(grandparent); cur->_col = BLACK; grandparent->_col = RED; } //修改完后就要break了，不要再往上走了 break; } } else { Node* uncle = grandparent->_left; //uncle==nullptr为其它情况 if (uncle && uncle->_col == RED) { uncle->_col = parent->_col = BLACK; grandparent->_col = RED; cur = grandparent; parent = grandparent->_parent; } else { if (parent->_left == cur) { rotateR(parent); rotateL(grandparent); cur->_col = BLACK; grandparent->_col = RED; } else { rotateL(grandparent); parent->_col = BLACK; grandparent->_col = RED; } break; } } } _root->_col = BLACK; return true; }

2.uncle为黑或uncle为空

1.uncle为空

此时cur一定为新插入结点，不然左边一定有别的黑节点使黑节点数两边不相等。

2.uncle为黑

此时cur一定不为新插入结点，不然左子树一定比右子树少至少一个黑节点。

二者本质是一样的，只有旋转才能解决，此时又分两种情况。

1.cur在parent的左子树,右单旋

以grandparent为旋转点单右旋，然后将grandparent改为红色，parent改为黑色。

2.cur在parent的右子树,左右双旋

先以parent为旋转点单左旋,再以grandparent为旋转点单右旋，grandparent改为红色,cur改为黑色.

代码：

while (parent && parent->_col == RED) { Node* grandparent = parent->_parent; //这里核心是用于限定uncle在grandparent的左还是右的 //此处uncle为右 if (grandparent->_left == father) { Node* uncle = grandparent->_right; //uncle==nullptr为其它情况 if (uncle&&uncle->_col == RED) { uncle->_col = parent->_col = BLACK; grandparent->_col = RED; cur = grandparent; parent = grandparent->_parent; } else if (parent->_left == cur) { rotateR(grandparent); parent->_col = BLACK; grandparent->_col = RED; } else { rotateL(parent); rotateR(grandparent); cur->_col = BLACK; grandparent->_col = RED; } } //此处uncle为左 else { Node* uncle = grandparent->_laft; //uncle==nullptr为其它情况 if (uncle && uncle->_col == RED) { uncle->_col = parent->_col = BLACK; grandparent->_col = RED; cur = grandparent; parent = grandparent->_parent; } else if (parent->_left == cur) { rotateR(parent); rotateL(grandparent); cur->_col = BLACK; grandparent->_col = RED; } else { rotateL(parent); parent->_col = BLACK; grandparent->_col = RED; } }

3.检查是否为红黑树

1.用孩子找是否与父亲都为红色

2.计算每一条路径的黑色结点是否都相同

bool isRBtree() { if (_root == nullptr) return true; if (_root->_col == RED) return false; Node* cur = _root; int realheight = 0; while (cur) { if (cur->_col == BLACK)realheight++; //随便找一条路径的黑色节点数即可 cur = cur->_left; } return _isRBtree(_root, 0, realheight); } private: //num是形参，找每一条的黑色结点个数，realnum是外部传的一个一条路径的黑色节点数 bool _isRBtree(Node* _root, int num, const int realnum) { //说明遍历到头了 if (_root == nullptr) { if (num != realnum) { cout << "not real number" << endl; return false; } return true; } if (_root->_col == BLACK) num++; if (_root->_col == RED && _root->_parent->_col == RED) { cout << "contrast colour " << endl; return false; } return _isRBtree(_root->_left, num, realnum) && _isRBtree(_root->_right, num, realnum); }

总结两次出的问题都在于在更新完后没有及时的break，因此要注意在调整更新后要及时地break,部分情况除外。