红黑树
1. 红黑树的概念
红黑树，是一种二叉搜索树，但在每个节点上增加一个存储位表示节点的颜色，可以是Red或者是Black。通过任何一条根到叶子的路径各个节点着色方式的限制。红黑树确保任何一条路径不会比其他路径长度多出两倍，所以是平衡的
2. 红黑树的性质
- 每个节点不是红色就是黑色
- 根节点是黑色的
- 如果一个节点是红色的，它的两个孩子节点是黑色的
- 对于每个节点，从该节点到其所有后代叶节点的简单路径上，包含相同数目的黑色节点
- 每个叶子节点都是黑色的（此处的叶子节点表示空节点）
3. 红黑树节点的定义
enum Color { RED, BLACK }; template<class ValueType> class RBTreeNode { public: explicit RBTreeNode(const ValueType& data = ValueType(), Color color = RED):_left(nullptr), _right(nullptr), _parent(nullptr), _data(data), _color(color) {} RBTreeNode<ValueType>* _left; RBTreeNode<ValueType>* _right; RBTreeNode<ValueType>* _parent; ValueType _data; Color _color; };
在节点的定义当中，为什么将节点的默认颜色给为红色？
通过把新插入的节点默认为红色，可以较快地满足红黑树的性质，并且减少了插入操作时需要进行的旋转操作次数，提高了插入操作的效率。同时，红色节点相对于黑色节点来说，占用的存储空间更小，节省了内存空间。因此，在红黑树中，默认将节点的颜色给为红色。
4. 红黑树的结构
红黑树当中增加了一个头结点，如下图所示
5. 红黑树的插入操作
红黑树是在二叉搜索树的基础上加平衡限制条件，因此红黑树插入可以分为两步：
- 按照二叉搜索树的规则插入新节点
- 检测新节点插入之后红黑树的性质是否改变
约定：cur表示当前节点、p父节点、g为祖父节点，u为叔叔节点
- 情况一：cur为红色，p为红，g为红, u存在且为红
注意：上图的数可以是一棵完整的树，也可能是一棵子树
黑色是可以连着出现，但是红色节点不行。
如果g是根节点，调整完成之后，需要将g改为黑色。如果g是子树，g一定有双亲，且g的双亲如果是红色，需要继续向上调整
cur 和 p均为红，违反了性质三。将p和u改为黑，然后把g当做cur继续向上调整
- 情况二：cur为红，p为红，g为黑色。u不存在/u存在且为黑
u的情况有两种
- 如果u不存在，则cur一定是新插入的节点。如果cur不是新插入的节点，则cur和p则一定有一个节点颜色是黑色，就不满足性质四
- 如果u存在，一定是黑色，那么cur原来的颜色一定是黑色，现在看到红色的原因是在调整的过程中将cur节点的颜色改为红色
p为g的左孩子，cur为p的左孩子，进行右旋
p为g的右孩子，cur为p的右孩子，进行左旋
p、g变色–p变黑，g变红
- 情况三：cur为红，p为红，g为黑u不存在/u存在且为黑
while (parent && parent->_col == RED) { Node* grandfather = parent->_parent; if (grandfather->_left == parent) { Node* uncle = grandfather->_right; // 情况1：u存在且为红，变色处理，并继续往上处理 if (uncle && uncle->_col == RED) { parent->_col = BLACK; uncle->_col = BLACK; grandfather->_col = RED; // 继续往上调整 cur = grandfather; parent = cur->_parent; } else // 情况2+3：u不存在/u存在且为黑，旋转+变色 { // g // p u // c if (cur == parent->_left) { RotateR(grandfather); parent->_col = BLACK; grandfather->_col = RED; } else { // g // p u // c RotateL(parent); RotateR(grandfather); cur->_col = BLACK; //parent->_col = RED; grandfather->_col = RED; } break; } } else // (grandfather->_right == parent) { // g // u p // c Node* uncle = grandfather->_left; // 情况1：u存在且为红，变色处理，并继续往上处理 if (uncle && uncle->_col == RED) { parent->_col = BLACK; uncle->_col = BLACK; grandfather->_col = RED; // 继续往上调整 cur = grandfather; parent = cur->_parent; } else // 情况2+3：u不存在/u存在且为黑，旋转+变色 { // g // u p // c if (cur == parent->_right) { RotateL(grandfather); grandfather->_col = RED; parent->_col = BLACK; } else { // g // u p // c RotateR(parent); RotateL(grandfather); cur->_col = BLACK; grandfather->_col = RED; } break; } } } _root->_col = BLACK; return true; }
因为红黑树只要求最长路径不超过最短路径的两倍。相对而言降低了插入和旋转的次数。
