C++之红黑树认识与实现

一.红黑树的概念

红⿊树是⼀棵⼆叉搜索树，他的每个结点增加⼀个存储位来表⽰结点的颜⾊，可以是红⾊或者⿊⾊。通过对任何⼀条从根到叶⼦的路径上各个结点的颜⾊进⾏约束，红⿊树确保没有⼀条路径会⽐其他路径⻓出2倍，因⽽是接近平衡的。

红黑树的结构

// 枚举值表⽰颜⾊ 

enum Colour
{
 RED,
 BLACK
};

template<class K, class V>

struct RBTreeNode

{
 // 这⾥更新控制平衡也要加⼊parent指针 
 pair<K, V> _kv;
 RBTreeNode<K, V>* _left;
 RBTreeNode<K, V>* _right;
 RBTreeNode<K, V>* _parent;
 Colour _col;
 RBTreeNode(const pair<K, V>& kv)
 :_kv(kv)
 , _left(nullptr)
 , _right(nullptr)
 , _parent(nullptr)
 {}
};

template<class K, class V>

class RBTree{
 typedef RBTreeNode<K, V> Node;
public:

private:
 Node* _root = nullptr;
};

二.红黑树的定义与特性

红黑树是一种自平衡的二叉查找树，它满足以下五条基本性质：

节点是红色或黑色：每个节点都有一个颜色属性，红色或黑色。
根节点是黑色：树的根节点必须是黑色。
叶子节点是黑色：叶子节点（即空节点或NULL节点）是黑色。
红色节点的子节点是黑色：如果一个节点是红色，则它的两个子节点都是黑色。
从任意节点到其每个叶子的所有路径都包含相同数量的黑色节点：这确保了树的平衡性。

这些性质保证了红黑树在插入和删除操作后能够保持大致平衡，从而使得查找、插入和删除操作的时间复杂度都能保持在(O(log n))。
在这里插入图片描述

一.红黑树的插入操作

插入操作是红黑树中最复杂的部分之一。插入一个新节点后，可能会破坏红黑树的性质，因此需要通过一系列的调整来恢复这些性质。插入操作可以分为以下几个步骤：

1. 插入节点

首先，将新节点插入到红黑树中，就像在普通二叉查找树中插入一样。新插入的节点会被标记为红色，因为插入红色节点比插入黑色节点更容易保持树的平衡。

2. 修复红黑树

插入红色节点后，可能会违反红黑树的性质4（红色节点的子节点是黑色）。因此，需要通过以下几种情况进行调整：

情况1：新节点的父节点是黑色
这种情况下，插入的红色节点不会破坏红黑树的性质，无需进行任何调整。
情况2：新节点的父节点和叔叔节点都是红色
这种情况下，将父节点和叔叔节点变为黑色，祖父节点变为红色。然后，将祖父节点作为新的当前节点，继续向上调整。
情况3：新节点的父节点是红色，叔叔节点是黑色或为空
这种情况下，不仅仅需要变色，还需要进行旋转来调整。

插入操作的步骤

1. 插入新节点

如果树为空（_root == nullptr），直接创建一个黑色节点作为根节点并返回。
如果树不为空，从根节点开始，通过比较键值来找到插入位置。如果键值已经存在，则返回false，表示插入失败。
找到插入位置后，创建一个红色节点（新节点默认为红色），并将其插入到合适的位置（作为某个节点的左子节点或右子节点）。

2. 修复红黑树的性质

插入红色节点后，可能会违反红黑树的性质（尤其是第4条性质：不能有两个连续的红色节点）。因此需要通过旋转和变色操作来修复。

修复逻辑

循环条件：只要当前节点的父节点是红色，就需要进行修复。
祖父节点和叔叔节点：
- 祖父节点是当前节点的父节点的父节点。
- 叔叔节点是祖父节点的另一个子节点（与父节点不同）。

修复情况

叔叔节点存在且为红色：
- 父节点和叔叔节点都变色为黑色。
- 祖父节点变色为红色。
- 将当前节点更新为祖父节点，继续向上检查。
叔叔节点不存在或者为黑色：
- 如果父节点是祖父节点的左子节点：
  - 如果当前节点是父节点的左子节点：
    - 右旋祖父节点。
    - 父节点变色为黑色，祖父节点变色为红色。
  - 如果当前节点是父节点的右子节点：
    - 左旋父节点。
    - 右旋祖父节点。
    - 当前节点变色为黑色，祖父节点变色为红色。
- 如果父节点是祖父节点的右子节点：
  - 如果当前节点是父节点的右子节点：
    - 左旋祖父节点。
    - 父节点变色为黑色，祖父节点变色为红色。
  - 如果当前节点是父节点的左子节点：
    - 右旋父节点。
    - 左旋祖父节点。
    - 当前节点变色为黑色，祖父节点变色为红色。
单旋：
双旋：

3. 根节点的颜色

最后，确保根节点是黑色。

代码逻辑解析

插入新节点：

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;
    }
}

从根节点开始，通过比较键值找到插入位置。如果键值已存在，返回`false`。

cur = new Node(kv);
cur->_col = RED;
if (parent->_kv.first < kv.first)
{
    parent->_right = cur;
}
else
{
    parent->_left = cur;
}
cur->_parent = parent;

创建一个红色的新节点，并将其插入到合适的位置。

修复红黑树性质：

while (parent && parent->_col == RED)
{
    Node* grandfather = parent->_parent;
    if (parent == grandfather->_left)
    {
        Node* uncle = grandfather->_right;
        if (uncle && uncle->_col == RED)
        {
            parent->_col = uncle->_col = BLACK;
            grandfather->_col = RED;
            cur = grandfather;
            parent = cur->_parent;
        }
        else
        {
            if (cur == parent->_left)
            {
                RotateR(grandfather);
                parent->_col = BLACK;
                grandfather->_col = RED;
            }
            else
            {
                RotateL(parent);
                RotateR(grandfather);
                cur->_col = BLACK;
                grandfather->_col = RED;
            }
            break;
        }
    }
    else
    {
        Node* uncle = grandfather->_left;
        if (uncle && uncle->_col == RED)
        {
            parent->_col = uncle->_col = BLACK;
            grandfather->_col = RED;
            cur = grandfather;
            parent = cur->_parent;
        }
        else
        {
            if (cur == parent->_right)
            {
                RotateL(grandfather);
                parent->_col = BLACK;
                grandfather->_col = RED;
            }
            else
            {
                RotateR(parent);
                RotateL(grandfather);
                cur->_col = BLACK;
                grandfather->_col = RED;
            }
            break;
        }
    }
}

根据父节点和叔叔节点的颜色，以及当前节点的位置，选择合适的旋转和变色操作来修复红黑树的性质。

确保根节点为黑色：

        _root->_col = BLACK;
```    
    

### 二.红黑树的删除操作（作为了解即可）

删除操作比插入操作更为复杂，因为它可能会破坏红黑树的平衡。删除操作可以分为以下几个步骤：

#### 1\. 删除节点

首先，找到需要删除的节点。如果该节点有两个子节点，则需要找到它的后继节点（右子树中的最小节点）来替换它。然后，将该节点的值替换为后继节点的值，并将后继节点删除。

#### 2\. 修复红黑树

删除节点后，可能会违反红黑树的性质。需要通过以下几种情况进行调整：

-   **情况1：被删除的节点是红色**  
    这种情况下，直接删除该节点不会破坏红黑树的性质。
    
-   **情况2：被删除的节点是黑色，且其子节点是红色**  
    这种情况下，将子节点变为黑色，然后删除该节点。
    
-   **情况3：被删除的节点是黑色，且其子节点是黑色**  
    这种情况下，需要通过一系列复杂的调整来恢复红黑树的性质，包括颜色调整和旋转操作。
    

### 三.红黑树的查找操作

按⼆叉搜索树逻辑实现即可，搜索效率为O(logN)

```C
    Node* Find(const K& key)
    {
     Node* cur = _root;
     while (cur)
     {
     if (cur->_kv.first < key)
     {
     cur = cur->_right;
     }
     else if (cur->_kv.first > key)
     {
     cur = cur->_left;
     }
     else
     {
     return cur;
     }
     }
     return nullptr;
    }

四.红黑树的验证

每个节点是红色或黑色。
根节点是黑色。
所有叶子节点（空节点）是黑色。
如果一个节点是红色，则它的两个子节点都是黑色（不能有两个连续的红色节点）。
从任何节点到其每个叶子的所有路径都包含相同数量的黑色节点。

代码中的检查逻辑

1. `IsBalance`函数

这个函数是入口函数，用于初始化检查过程。

bool IsBalance()
{
    if (_root == nullptr)
        return true; // 如果树为空，直接返回true，空树满足红黑树的性质
    if (_root->_col == RED)
        return false; // 根节点必须是黑色，否则直接返回false

    // 计算从根节点到最左边叶子节点的黑色节点数量作为参考值
    int refNum = 0;
    Node* cur = _root;
    while (cur)
    {
        if (cur->_col == BLACK)
            ++refNum; // 如果当前节点是黑色，增加黑色节点计数
        cur = cur->_left; // 沿着左子树向下遍历
    }

    // 使用参考值调用Check函数检查整棵树
    return Check(_root, 0, refNum);
}

检查根节点颜色：如果根节点是红色，直接返回false，因为红黑树的根节点必须是黑色。
计算参考值refNum：从根节点开始，沿着左子树一直向下，统计路径上的黑色节点数量。这个值将作为后续路径检查的参考值。
调用Check函数：使用计算出的refNum，从根节点开始递归检查整棵树。

2. `Check`函数

这个函数是递归函数，用于检查树的每个路径是否满足红黑树的性质。

bool Check(Node* root, int blackNum, const int refNum)
{
    if (root == nullptr)
    {
        // 前序遍历走到空节点，意味着一条路径走完了
        if (refNum != blackNum)
        {
            cout << "存在黑色节点的数量不相等的路径" << endl;
            return false; // 如果当前路径的黑色节点数量与参考值不同，返回false
        }
        return true;
    }

    // 检查是否存在连续的红色节点
    if (root->_col == RED && root->_parent->_col == RED)
    {
        cout << root->_kv.first << "存在连续的红色节点" << endl;
        return false; // 如果当前节点和父节点都是红色，返回false
    }

    if (root->_col == BLACK)
    {
        blackNum++; // 如果当前节点是黑色，增加黑色节点计数
    }

    // 递归检查左右子树
    return Check(root->_left, blackNum, refNum) && Check(root->_right, blackNum, refNum);
}

检查路径结束：如果当前节点是空节点（root == nullptr），说明已经到达路径的末端。此时检查当前路径的黑色节点数量blackNum是否与参考值refNum相等。如果不相等，说明违反了红黑树的第5条性质。
检查连续红色节点：如果当前节点是红色，并且它的父节点也是红色，直接返回false，因为这违反了红黑树的第4条性质。
统计黑色节点：如果当前节点是黑色，将blackNum加1。
递归检查子树：递归调用Check函数，分别检查当前节点的左子树和右子树。只有当左右子树都满足红黑树的性质时，当前节点才满足性质。

bool Check(Node* root, int blackNum, const int refNum)
{
 if (root == nullptr)
 {
 // 前序遍历⾛到空时，意味着⼀条路径⾛完了 
 //cout << blackNum << endl;

 if (refNum != blackNum)
 {
 cout << "存在⿊⾊结点的数量不相等的路径" << endl;
 return false;
 }
 return true;
 }
 
 // 检查孩⼦不太⽅便，因为孩⼦有两个，且不⼀定存在，反过来检查⽗亲就⽅便多了 
 if (root->_col == RED && root->_parent->_col == RED)
 {
 cout << root->_kv.first << "存在连续的红⾊结点" << endl;
 return false;
 }
 if (root->_col == BLACK)
 {
 blackNum++;
 }
 return Check(root->_left, blackNum, refNum)
 && Check(root->_right, blackNum, refNum);
}
 

bool IsBalance()
{
 if (_root == nullptr)
 return true;
 if (_root->_col == RED)
 return false;
 
 // 参考值 
 int refNum = 0;
 Node* cur = _root;
 while (cur)
 {
 if (cur->_col == BLACK)
  {
 ++refNum;
 }
 cur = cur->_left;
 }
 return Check(_root, 0, refNum);
}

红黑树 vs AVL树

特性	红黑树	AVL树
平衡严格度	宽松（最长路径≤2×最短）	严格（高度差≤1）
插入/删除	更快（平均更少旋转）	较慢（旋转次数多）
查找效率	稍慢（高度略高）	更快（高度最小化）
适用场景	频繁修改的关联容器（如map）	查询密集型场景