什么是红黑树
红黑树，是一种二叉搜索树，但在每个结点上增加一个存储位表示结点的颜色，可以是Red（红）或Black（黑），它是一种比AVL树在使用上更优秀的树，通过对任何一条从根到叶子的路径上各个结点着色方式的限制，保没有一条路径会比其他路径长出俩倍，因而是接近平衡的。
一棵红黑树有以下特性：
- 1. 每个结点不是红色就是黑色
- 2. 根节点是黑色的
- 3. 如果一个节点是红色的，则它的两个孩子结点是黑色的
- 4. 对于每个结点，从该结点到其所有后代叶结点的简单路径上，均 包含相同数目的黑色结点
- 5. 每个叶子结点都是黑色的(此处的叶子结点指的是空结点)
因为每条路径中黑色结点的个数都是一定的，且红色结点是不能连续的，所以红黑树的一条路径上的结点数最少就是：n（全黑），最多就是 2n个（黑红相间隔），因为保证了这棵树的相对均衡，所以最差的查找是复杂度也是 O(log2*N)
那为什么不用 AVL树来存储呢，查找效率不是更高一些？
AVL树是依据高度差（平衡因子）来旋转调整树的形状的，一旦左右子树平衡因子之差超过1，就要进行旋转；而红黑树是正常插入数据，通过变色来调整维持红黑树的特性，直到通过变色无法维持红黑树的特性时才进行旋转调整，因此相对于AVL树旋转次数更少一些，效率较高。
红黑树结点
相对于普通搜索二叉树多了个_parent的指针，方便建立树，一个枚举类型的变量表示树的颜色。
红黑树的插入及验证
红黑树的插入内核就是依照二叉搜索树的基本方法进行插入，但如果违反了红黑树的特性，就要进行调整。
- 插入红色结点：因为红黑树中的每条路径上的黑色结点的个数都是一定的，因此插入的时候只有插入红色结点，才能保证不影响每条路径黑色结点个数相等这一特性。
- 看插入结点的父亲结点的颜色：确定插入的是红色结点，那么就要看父亲结点的颜色，父亲结点如果是黑色，那么插入就直接结束了，如果父亲结点是红色，那么就违反了红黑树的第三个特性，要进行调整，去看叔叔结点的颜色。
- 看叔叔结点：叔叔结点（父亲的父亲结点的另一个孩子结点），父亲为红色。如果叔叔也为红色，那么隐藏条件就是爷爷结点为黑色，这种情况只需要将爷爷结点的颜色变为红色，父亲和叔叔结点的颜色变为黑色，这样就保证了红黑树的特性；如果叔叔不存在或者叔叔为黑色，那就需要旋转和变色一起调整了，因为此时仅仅靠变色已经难以解决问题了，至于如果旋转，只需要遵循红黑树的他特性。
验证建立的红黑树是否正确，就要从红黑树的几个特性依次卡，只要不符合就返回 false，只有全部成立才返回 true
代码实现
#pragma once #include<iostream> using namespace std; typedef enum Color { RED, // 红色 BLACK // 黑色 }Color; template<class K, class V> struct RBTreeNode { RBTreeNode(const pair<K, V>& kv) :_right(nullptr) , _left(nullptr) , _parent(nullptr) ,_col(RED) , _kv(kv) {} RBTreeNode<K, V>* _right; RBTreeNode<K, V>* _left; RBTreeNode<K, V>* _parent; // 颜色：枚举类型 Color _col; pair<K, V> _kv; }; 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); // 初始化的时候就是红色结点 cur->_parent = parent; // 调整父子之间的关系 if (parent->_kv.first < kv.first) parent->_right = cur; else if (parent->_kv.first > kv.first) parent->_left = cur; Node* grandparent = parent->_parent; while (parent && parent->_col == RED) { grandparent = parent->_parent; Node* uncle = nullptr; // 调整父亲和叔叔与爷爷的关系 if (parent->_kv.first > grandparent->_kv.first) { grandparent->_right = parent; uncle = grandparent->_left; } else if (parent->_kv.first < grandparent->_kv.first) { grandparent->_left = parent; uncle = grandparent->_right; } // 新插入结点的父亲是红色结点，需要调整 // 调整父亲和叔叔的左右 if (uncle && uncle->_col == RED) // 叔叔存在并且为红色 { grandparent->_col = RED; uncle->_col = parent->_col = BLACK; cur = grandparent; parent = cur->_parent; } else if(uncle == nullptr || uncle->_col == BLACK) { if (parent == grandparent->_left) { if (cur == parent->_left) { RotateR(grandparent); parent->_col = BLACK; grandparent->_col = RED; } else if (cur == parent->_right) { RotateL(parent); RotateR(grandparent); cur->_col = BLACK; grandparent->_col = RED; } } else { if (cur == parent->_left) { RotateR(parent); RotateL(grandparent); grandparent->_col = RED; cur->_col = BLACK; } else if (cur == parent->_right) { RotateL(grandparent); grandparent->_col = RED; parent->_col = BLACK; } } break; } } _root->_col = BLACK; return true; } bool IsValidRBTree() { 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); } 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++; // 检测当前节点与其双亲是否都为红色 Node* pParent = pRoot->_parent; if (pParent && RED == pParent->_colo && RED == pRoot->_col) { cout << "违反性质三：没有连在一起的红色节点" << endl; return false; } return _IsValidRBTree(pRoot->_left, k, blackCount) && _IsValidRBTree(pRoot->_right, k, blackCount); } void Order() { _Order(_root); cout << endl; } void _Order(Node* root) { if (root == nullptr) return; _Order(root->_left); cout << root->_kv.first << " "; _Order(root->_right); } void RotateR(Node* parent) { Node* subL = parent->_left; Node* subLR = subL->_right; Node* parentParent = parent->_parent; subL->_right = parent; parent->_parent = subL; parent->_left = subLR; if (subLR) subLR->_parent = parent; if (parent == _root) { _root = subL; subL->_parent = nullptr; } else { if (parentParent->_left == parent) { parentParent->_left = subL; } else if (parentParent->_right == parent) { parentParent->_right = subL; } subL->_parent = parentParent; } } void RotateL(Node* parent) { Node* subR = parent->_right; Node* subRL = subR->_left; Node* parentParent = parent->_parent; subR->_left = parent; parent->_parent = subR; if (subRL) subRL->_parent = parent; parent->_right = subRL; if (parent == _root) { _root = subR; subR->_parent = nullptr; } else { // 先找到 parent 是父亲的左子树还是右子树 if (parentParent->_left == parent) // 左子树 { parentParent->_left = subR; } else if (parentParent->_right == parent) // 右子树 { parentParent->_right = subR; } subR->_parent = parentParent; } } private: Node* _root = nullptr; };
