红黑树

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

红黑树的性质

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

红黑树结点的定义

// 节点的颜色
enum Color{RED, BLACK};
// 红黑树节点的定义
template<class ValueType>
struct RBTreeNode
 {
 RBTreeNode(const ValueType& data = ValueType()，Color color = RED)
 : _pLeft(nullptr)
 , _pRight(nullptr)
 , _pParent(nullptr)
 , _data(data)
 , _color(color)
 {}
 RBTreeNode<ValueType>* _pLeft; // 节点的左孩子
 RBTreeNode<ValueType>* _pRight; // 节点的右孩子
 RBTreeNode<ValueType>* _pParent; // 节点的双亲(红黑树需要旋转，为了实现简单给出该字段)
 ValueType _data; // 节点的值域
 Color _color; // 节点的颜色
 };

在定义节点时将节点的默认颜色给成红色的，是因为插入之前所有根至外部节点的路径上黑色节点数目都相同，所以如果插入的节点是黑色肯定错误（黑色节点数目不相同），而相对的插入红节点可能会也可能不会违反“没有连续两个节点是红色”这一条件，所以插入的节点为红色，如果违反条件再调整

红黑树结构

为了能够简单的实现后续的关联式容器，所以我们在红黑树中增加一个头节点，因为根节点必须是黑色的，为了与根节点进行区分，将头结点给成红色，并且让头结点的 pParent 域指向红黑树的根节点，pLeft域指向红黑树中最小的节点，_pRight域指向红黑树中最大的节点

template<class ValueType>
class RBTree
{
 typedef RBTreeNode<ValueType> Node;
 typedef Node* PNode;
public:
 RBTree()
 : _pHead(new Node)
 {
 _pHead->_pParent = nullptr;
 _pHead->_pLeft = _pHead;
 _pHead->_pRight = _pHead;
 }
 
 PNode& GetRoot()
 {
 return _pHead->_pParent;
 }
private:
 PNode _pHead;
};

红黑树的插入

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

   template<class ValueType>
   class RBTree
   {
    //……
    
    bool Insert(const ValueType& data)
    {
    PNode& pRoot = GetRoot();
    // 1. 按照二叉搜索的树方式插入新节点
    if (nullptr == pRoot)
    {
    pRoot = new Node(data, BLACK);
    // 根的双亲为头节点
    pRoot->_pParent = _pHead;
    }
    else
    {
    // 按照二叉搜索树的特性，找节点在红黑树中的插入位置
    PNode pCur = pRoot;
    PNode pParent = nullptr;
    while (pCur)
    {
    pParent = pCur;
    if (data < pCur->_data)
    pCur = pCur->_pLeft;
    else if (data > pCur->_data)
    pCur = pCur->_pRight;
    else
    return false;
    }
    // 插入新节点
    pCur = new Node(data);
    if (data < pParent->_data)
    pParent->_pLeft = pCur;
    else
    pParent->_pRight = pCur;
    // 更新新节点的双亲
    pCur->_pParent = pParent;
    // 2. 检测新节点插入后，红黑树的性质是否造到破坏，
    // 若满足直接退出，否则对红黑树进行旋转着色处理
    //...
    }
    // 根节点的颜色可能被修改，将其改回黑色
    pRoot->_color = BLACK;
    _pHead->_pLeft = LeftMost();
    _pHead->_pRight = RightMost();
    return true;
    }
   private:
    PNode& GetRoot()
    {
    return _pHead->_pParent;
    }
    // 获取红黑树中最小节点，即最左侧节点
    PNode LeftMost()
    {
    PNode pCur = GetRoot();
    if (nullptr == pCur)
    return _pHead;
    // 获取红黑树中最左侧节点
    while (pCur->_pLeft)
    {
    pCur = pCur->_pLeft;
    }
    return pCur;
    }
    // 获取红黑树中最大节点，即最右侧节点
    PNode RightMost()
    {
    PNode pCur = GetRoot();
    if (nullptr == pCur)
    return _pHead;
    // 获取红黑树中最右侧节点
    while (pCur->_pRight)
    {
    pCur = pCur->_pRight;
    }
    return pCur;
    }
   private:
    PNode _pHead;
   };

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

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

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

  

  cur和p均为红，违反了性质三，此处能否将p直接改为黑？
  解决方式：将p,u改为黑，g改为红，然后把g当成cur，继续向上调整

• 情况二: cur为红，p为红，g为黑，u不存在/u为黑

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

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

p为g的左孩子，cur为p的右孩子，则针对p做左单旋转；相反，
p为g的右孩子，cur为p的左孩子，则针对p做右单旋转
则转换成了情况2

bool Insert(const ValueType& data)
{
 // 1. 按照二叉搜索树的性质将新节点插入
 // ......
 
 // 2. 检测新节点插入后，红黑树的性质是否造到破坏
 // 更新结点颜色--
 // 违反性质3：不能有连在一起的红色结点
 while(pParent && RED == pParent->_color)
 {
 // 注意：grandFather一定存在
 // 因为pParent存在，且不是黑色节点，则pParent一定不是根，则其一定有双亲
 PNode grandFather = pParent->_pParent;
 // 先讨论左侧情况
 if(pParent == grandFather->_pLeft)
 {
 PNode unclue = grandFather->_pRight;
 // 情况三：叔叔节点存在，且为红
 if(unclue && RED == unclue->_color)
 {
 pParent->_color = BLACK;
 unclue->_color = BLACK;
 grandFather->_color = RED;
 pCur = grandFather;
 pParent = pCur->_pParent;
 }
 else
 {
 // 情况五：叔叔节点不存在，或者叔叔节点存在且为黑
 if(pCur == pParent->_pRight)
 {
 _RotateLeft(pParent);
 swap(pParent, pCur);
 }
 // 情况五最后转化成情况四
     grandFather->_color = RED;
 pParent->_color = BLACK;
 _RotateRight(grandFather);
 }
 }
 else
 {
 // 右侧请学生们自己动手完成
 }
 }
 // 旋转完成后，将根节点的颜色改成黑叔
 _pRoot->_color = BLACK;
 return true;
}

红黑树的验证

红黑树的检测分为两步：

1. 检测其是否满足二叉搜索树(中序遍历是否为有序序列)
2. 检测其是否满足红黑树的性质

bool IsValidRBTree()
{
 PNode pRoot = GetRoot();
 
 // 空树也是红黑树
 if (nullptr == pRoot)
 return true;
    // 检测根节点是否满足情况
 if (BLACK != pRoot->_color)
 {
 cout << "违反红黑树性质二：根节点必须为黑色" << endl;
 return false;
 }
 // 获取任意一条路径中黑色节点的个数
 size_t blackCount = 0;
 PNode pCur = pRoot;
 while (pCur)
 {
 if (BLACK == pCur->_color)
 blackCount++;
 pCur = pCur->_pLeft;
 }
 // 检测是否满足红黑树的性质，k用来记录路径中黑色节点的个数
 size_t k = 0;
 return _IsValidRBTree(pRoot, k, blackCount);
 }
bool _IsValidRBTree(PNode pRoot, size_t k, const size_t blackCount)
{
 if (nullptr == pRoot)
 return true;
 // 统计黑色节点的个数
 if (BLACK == pRoot->_color)
 k++;
 // 检测当前节点与其双亲是否都为红色
 PNode pParent = pRoot->_pParent;
 if (pParent && RED == pParent->_color && RED == pRoot->_color)
 {
 cout << "违反性质三：没有连在一起的红色节点" << endl;
 return false;
 }
 // 如果pRoot是因子节点，检测当前路径中黑色节点的个数是否有问题
 if (nullptr == pRoot->_pLeft && nullptr == pRoot->_pRight)
 {
 if (k != blackCount)
 {
 cout << "违反性质四：每条路径中黑色节点的个数必须相同" << endl;
 return false;
 }
 }
 return _IsValidRBTree(pRoot->_pLeft, k, blackCount) &&
 _IsValidRBTree(pRoot->_pRight, k, blackCount);
}

红黑树与AVL树的比较

红黑树和AVL树都是高效的平衡二叉树，增删改查的时间复杂度都是O( )，红黑树不追求绝对平衡，其只需保证最长路径不超过最短路径的2倍，相对而言，降低了插入和旋转的次数，所以在经常进行增删的结构中性能比AVL树更优，而且红黑树实现比较简单，所以实际运用中红黑树更多。