【C++】红黑树（上）

⚪前言

• AVL树：严格平衡（左右子树高度差不超过 1），所以 AVL 树的查找、插入、删除效率高：O(logN)，但在插入和删除节点后，要维持树的平衡状态，做的旋转处理还是很多的。
• 红黑树：近似平衡（控制最长路径不超过最短路径的2倍），变了一种方式来控制树的平衡，相较于 AVL 树而言，没有那么严格。

红黑树更多是一种折中的选择，它舍弃平衡二叉树的严格平衡，换取节点插入时尽可能少的调整。

因为红黑树的旋转情况少于 AVL 树，使得红黑树整体性能略优于 AVL 树，不然 map 和 set 底层怎么会使用红黑树呢，包括很多语言的库里面都用了红黑树。

一、红黑树

1、红黑树的概念

红黑树，是一种二叉搜索树，但在每个结点上增加一个存储位表示结点的颜色，可以是 Red 或 Black。

通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路径会比其他路径长出 2 倍，因而是接近平衡的。

2、红黑树的性质

1. 每个结点不是红色就是黑色。
2. 根节点是黑色的 。
3. 如果一个节点是红色的，则它的两个孩子结点是黑色的。（红黑树里面没有连续的红色节点）
4. 对于每个结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数目的黑色结点 。（即每条路径都有相同数量的黑色节点，注意：路径是走到 NIL 空节点）
5. 每个 NIL 叶子结点都是黑色的。（此处的叶子结点指的是空结点）

上图这颗红黑树一共有 11 条路径，每条路径都有两个黑节点（不包括 NIL）。

为什么满足上面的性质，红黑树就能保证其最长路径中节点个数不会超过最短路径节点个数的 2 倍呢？（不包括NIL）

当某条路径最短时，这条路径必然都是由黑色节点构成。

当某条路径长度最长时，这条路径必然是由红色和黑色节点交替构成的（上面第 3 点限定了不能出现两个连续的红色节点）。而第 4 点又限定了从任一节点到其每个叶子节点的所有路径必须包含相同数量的黑色节点，那么说明最长路径上黑节点的数目和最短路径上黑节点的数目是相等的。

• 最短路径：全是黑节点。
• 最长路径：一黑一红，交替出现，所以最长路径刚好是最短路径的 2 倍。

3、红黑树节点的定义

// 定义节点的颜色
enum Color // 枚举类型，枚举值默认从0开始，往后逐个加1（递增）
{
    RED,
    BLACK
};
 
// 红黑树节点的定义（KV模型）
template<class K, class V>
struct RBTreeNode
{
    RBTreeNode<K, V>* _left;   // 三叉链结构
  RBTreeNode<K, V>* _right;
  RBTreeNode<K, V>* _parent;
 
  pair<K, V> _kv;            // 键值对
  Colour _col;               // 用来标记节点颜色
 
    // 构造函数
  RBTreeNode(const pair<K, V>& kv)
    :_left(nullptr)
    , _right(nullptr)
    , _parent(nullptr)
    , _kv(kv)
  {}
};

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

• 如果插入黑色节点，一定会破坏第 4 点性质（每条路径的黑色节点数量相等）。
• 如果插入红色节点，可能会破坏第 3 点性质（树中不能出现两个连续的红色节点）。

所以默认给红色。（破坏第 3 点性质的可行性高一些）

4、红黑树结构

为了后续实现关联式容器简单，红黑树的实现中增加一个头结点，因为跟节点必须为黑色，为了与根节点进行区分，将头结点给成黑色，并且让头结点的 parent 域指向红黑树的根节点，_left 域指向红黑树中最小的节点，_right 域指向红黑树中最大的节点，如下：

// 红黑树的定义（KV模型）
template<class K, class V>
class RBTree
{
  typedef RBTreeNode<K, V> Node;
public:
    RBTree() :_root(nullptr) {}        // 构造函数
    bool Insert(const pair<K, V>& kv); // 插入节点
    void InOrder();                    // 中序遍历
    bool IsBalance();                  // 检测红黑树是否平衡           
  // ......
 
private:
    void _InOrder(Node* root);         // 中序遍历子函数
    void RotateL(Node* parent)         // 左单旋
    void RotateR(Node* parent)         // 右单旋
    // ......
private:
  Node* _root;
};

5、红黑树的插入操作

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

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

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

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

因为新节点的默认颜色是红色，因此：

如果其双亲节点的颜色是黑色，没有违反红黑树任何性质，则不需要调整；

如果其双亲节点的颜色为红色，就违反了第 3 点性质（不能有连在一起的红色节点），此时需要对红黑树分情况来讨论：

约定：cur 为当前节点，p（parent）为父节点，g（grandfather）为祖父节点，u（uncle）为叔叔节点。

调整的关键：主要是看 cur 的叔叔节点 u 是否存在，以及叔叔节点 u 的颜色。

cur 为红，p 为红，违反了规则，我们将 p 变黑，则导致 p 所在的所有路径上，黑节点数增加了一个，但因为叔叔节点 u 和父节点 p 在同一层上，所以叔叔节点 u 的状态会影响到以祖父 g 为根的子树中路径的黑节点数，可能导致违反规则（每条路径都有相同数量的黑色节点）。

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

注意：此处所看到的树，可能是一颗完整的树，也可能是一颗子树。所以可能会一直调整到根节点才停止。

对情况一进行平衡化操作：先调整颜色，再往上调整。

无论父亲 p 是祖父 g 的左孩子还是右孩子，无论 cur 是父亲 p 的左孩子还是右孩子，处理方式都是一样的：

• 调整颜色：将 cur 的父亲 p 和叔叔 u 变黑，祖父 g 变红。
• 把祖父 g 当成新的 cur，往上调整（即往上检测新的子树破坏了性质），分为以下情况：

1、如果 cur 父亲 p 不存在，说明 cur 就是根节点，调整到头了，此时将根节点改为黑色。

2、如果 cur 父亲 p 存在且为黑色，则无需调整（没有违反任何性质)。

3、如果 cur 父亲 p 存在且为红色，继续调整，判断是否产生了情况 2/3：

注意：情况 1 在向上调整的过程中，可能会产生情况 2/3。处理方式：旋转（先要判断是哪种旋转） + 变色处理。

问：cur 和 p 均为红，违反了性质三，此处能否将 p 直接改为黑？

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

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

如图所示，情况一向上调整过程中，产生了情况二 - ①：

对情况二进行平衡化操作：先单旋，再调整颜色（不管是哪种单旋，颜色调整都一样：p 变黑，g 变红）

注意：对局部的一颗子树平衡化操作，整个过程中，我们要保持当前子树的每条路径中黑色节点数量不变。

① 如果父亲 p 是祖父 g 的左孩子， cur 是父亲 p 的左孩子，先对祖父 g 进行右单旋；然后将父亲 p 变黑，祖父 g 变红：

1. u不存在
   

1. u存在且为黑

② 如果父亲 p 是祖父 g 的右孩子， cur 是父亲 p 的右孩子，先对祖父 g 进行进行左单旋；然后将父亲 p 变黑，祖父 g 变红：

1. u不存在

1. u存在且为黑

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

如图所示，情况一向上调整过程中，产生了情况三 - ①：

对情况三进行平衡化操作：先双旋，再调整颜色（不管是哪种双旋，颜色调整都一样：cur 变黑，g 变红）

注意：对局部的一颗子树平衡化操作，整个过程中，我们要保持当前子树的每条路径中黑色节点数量不变。

① 如果父亲 p 是祖父 g 的左孩子， cur 是父亲 p 的右孩子，先对父亲 p 进行左单旋，再对祖父 g 进行右单旋；然后将 cur 变黑，祖父 g 变红：

1. u不存在

1. u存在且为黑

② 如果父亲 p 是祖父 g 的右孩子，cur 是父亲 p 的左孩子，先对父亲 p 进行右单旋，再对祖父 g 进行左单旋；然后将 cur 变黑，祖父 g 变红：

1. u不存在

1. u存在且为黑

【总结】

当插入红色新节点 cur 后，如果父亲 p 存在且为红，说明破坏红黑树性质了，需要平衡化操作。

【C++】红黑树（下）https://developer.aliyun.com/article/1515246?spm=a2c6h.13148508.setting.26.11104f0e63xoTy