C++红黑树的原理和实现

文章目录

一、引言

二、红黑树的概念与性质

2、1 红黑树的概念

2、2 红黑树的性质

三、红黑树的定义与实现

3、1 红黑树的定义

3、2 插入新节点

3、2、1 默认插入红色节点

3、3 插入情况分类

3、3、1 情况一（根据颜色向上调整）

3、3、2 情况二（单次旋转 变色）

3、3、3 情况三（两次旋转 变色）

3、4 插入的完整代码实现

四、红黑树的检验

五、性能分析

六、总结

---

👀 专栏：C 、数据结构 👀

💥 标题：红黑树💥

 ❣️ 寄语：与其忙着诉苦，不如低头赶路，奋路前行，终将遇到一番好风景 ❣️ 

一、引言

  红黑树是一种自平衡的二叉搜索树，它在计算机科学中扮演着重要的角色。由于其高效的插入、删除和查找操作，红黑树被广泛应用于各种数据结构和算法的实现中。红黑树的设计旨在保持树的平衡，从而确保各种操作的时间复杂度能够保持在较低的范围内。 

 当我们学完 AVL树 后，我们再学红黑树相对来说就会简单一点。红黑树可以看成是AVL树的升级版。

二、红黑树的概念与性质

2、1 红黑树的概念

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

2、2 红黑树的性质

 红黑树也是一颗很特殊的树，它具有如下的性质：

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

  这里就有一个疑问了：为什么满足上面的性质，红黑树就能保证：其最长路径中节点个数不会超过最短路径节点个数的两倍？

  根据上述的性质三我们知道，一个路径最短的情况下就是所有节点的颜色为黑色。同时最长的情况是一红一黑交叉出现。但是我们不要忘记了性质四每条路径的黑色节点数量相同，那么最长的路径就是最短的路径两倍了，并没有超过两倍。

  通过以上的红黑树特性，我们可以保证红黑树在进行插入、删除等操作时，始终能够保持树的平衡性，从而保证了各种操作的时间复杂度始终在对数级别内。在接下来的章节中，我们将深入探讨红黑树的插入操作的实现细节，以及时间复杂度的分析，进一步理解红黑树的原理和实现。 

三、红黑树的定义与实现

3、1 红黑树的定义

  红黑树也是一种二叉搜索树，它的每个节点包含一个关键字（键值对）、左右孩子指针和父结点指针。每个节点还包含一个记录颜色的变量，该变量用来表示该节点是红色节点还是黑色节点。 实现代码如下：

1.  
   enum Colour
2.  
   {
3.  
   RED,
4.  
   BLACK
5.  
   };
6.  
    
7.  
   template<class K, class V>
8.  
   struct RBTreeNode
9.  
   {
10.  
    RBTreeNode<K, V>* _left;
11.  
    RBTreeNode<K, V>* _right;
12.  
    RBTreeNode<K, V>* _parent;
13.  
     
14.  
    pair<K, V> _kv;
15.  
    Colour _col;
16.  
     
17.  
    RBTreeNode(const pair<K, V>& kv)
18.  
    :_left(nullptr)
19.  
    , _right(nullptr)
20.  
    , _parent(nullptr)
21.  
    , _kv(kv)
22.  
    {}
23.  
    };

  表示颜色我们采用枚举的方式，以便整篇的代码比较整洁且易于理解。

3、2 插入新节点

  红黑树的插入操作是通过对二叉搜索树的基本插入操作结合颜色调整和旋转操作来实现的。插入算法的概述如下：

1. 首先，将插入的节点按照普通的二叉搜索树插入操作，将其放置在合适的位置上。
2. 将插入节点标记为红色，这样不会违反红黑树的特性。
3. 检查插入节点的父节点及其祖父节点、叔叔节点等情况，根据不同的情况进行颜色调整和旋转操作，以保持红黑树的平衡性和特性。
4. 最后，确保根节点是黑色的，以满足红黑树的根节点特性。

  插入操作的核心是对树进行颜色调整和旋转，以确保插入后仍然满足红黑树的特性。具体的左旋和右旋操作将在后续小节中详细解释，而插入修正过程则会对颜色调整的各种情况进行逐步解析。通过这些操作，红黑树能够在插入新节点时保持平衡，从而保证了各种操作的高效性能。

  接下来，我们将逐步深入探讨插入操作的具体细节，以便更好地理解红黑树的实现原理。

3、2、1 默认插入红色节点

  在具体的学习插入操作之前，我们应该想一下新插入的节点是插入红色节点呢还是插入黑色节点呢？我们不妨自己先结合着红黑树的性质思考一下。

  试想，我们新插入的节点是黑色节点，那么就违背了上述的性质四。那么影响的就是整棵树。大概率需要很复杂的旋转和调整才能恢复。假如新插入的节点是红色节点，新插入的节点的父节点可能为黑色，也可能为红色。当父节点为黑色时，并无影响。当父节点为红色时，违背了上述的性质三，影响的只是改父节点所在的子树。

  将新插入的节点设置为红色有两个主要原因：

1. 保持黑色高度平衡：红黑树要求在任意路径上的黑色节点数量是相同的，这被称为黑色高度平衡。通过将新插入的节点设置为红色，可以确保其不会破坏现有的黑色高度平衡。

2. 简化平衡调整：当插入新节点后，可能会导致红黑树的性质被破坏，需要进行平衡调整来恢复性质。将新节点设置为红色可以简化平衡调整的过程，因为红色节点的插入更容易适应红黑树的性质。如果将新节点设置为黑色，则可能需要对树进行更多的旋转和重新着色操作。

  总之，将新插入的节点设置为红色有助于保持红黑树的平衡性和减少平衡调整的复杂性。

3、3 插入情况分类

  我们先看如下情况，在值为1的黑色节点左侧插入一个新节点： 

  插入完之后，并不影响改红黑树的平衡，且满足红黑树的性质。

  我们再看另一种情况，在值为22的红色节点左侧插入一个新节点：

  我们发现，此时新插入的节点影响到了红黑树的平衡。那要是插入到值为22的红色节点右侧呢？或者插入到值为6的节点，又或者插入到值为27的节点，都需要我们进行调整。由于情况太多，所以对需要进行调整的情况进行了分类。

  接下来对需要调整的各种情况分类进行详解。

3、3、1 情况一（根据颜色向上调整）

  具体需要调整的状态如下图（抽象图）：

  注：cur为当前所在位置的节点；p（parent）为cur的父节点；u（uncle）为cur的叔叔节点；g（grandfather）为cur的祖宗节点。

  我们发现上述的情况cur为红，p为红，g为黑，u存在且为红，违背了性质三。那怎么进行调整呢？调整的方法很简单：将p,u改为黑，g改为红，然后把g当成cur，继续向上调整。具体如下图：

  如果g是根节点，调整完之后，需要将g改变为黑色。如果g是子树，g一定有双节点，且如果g的双亲是红色，需要继续重复此过程向上调整。 具体如下图:

  上图中的cur可能是新增节点，也可能是更新后的节点，具体如下图：

  当然，新增的红色节点可以是任意孩子位置， 只要是满足cur为红，p为红，g为黑，u存在且为红，就划分到这一类。 

3、3、2 情况二（单次旋转 变色）

  我们知道，只有p（父节点）是红色时，才需要进行调整。但是u（叔叔节点）不一定为红色，也有可能为黑色，甚至u（叔叔节点）可能就不存在。具体如下图：

  u的情况有两种，不同情况对应的情况说明：

1. 如果u节点不存在，则cur一定是新插入节点，因为如果cur不是新插入节点，则cur和p一定有一个节点的颜色是黑色，就不满足性质4：每条路径黑色节点个数相同.
2. 如果u节点存在，则其一定是黑色的，那么cur节点原来的颜色一定是黑色的，现在看到其是红色的原因是因为cur的子树在调整的过程中将cur节点的颜色由黑色改成红色。

  虽然u的情况有两种，但是处理方法是一样的。这时，只通过颜色调整是不行了。具体的调整方法是： p为g的左孩子，cur为p的左孩子，则进行对g进行右单旋转；相反， p为g的右孩子，cur为p的右孩子，则对g进行进行左单旋转。p、g变色--p变黑，g变红。具体如下图：

3、3、3 情况三（两次旋转 变色）

  当u（叔叔节点）为黑色或者不存在时，cur的位置也是影响旋转的关键。我们看如下情况：

  我们发现直接对g（祖宗节点）进行旋转并不能很好的解决问题。那能不能先对p（父亲节点）进行旋转呢？具体调整方法：p为g的左孩子，cur为p的右孩子，则针对p做左单旋转；相反，p为g的右孩子，cur为p的左孩子，则针对p做右单旋转。则转换成了情况2。对p旋转完后，具体情况如下图：

  那我们再进行针对情况二的旋转和变色不就完成了吗！！！ 

3、4 插入的完整代码实现

  当我们理解了上述的插入和调整思路后，我们来看一下代码的实现：

1.  
   bool Insert(const pair<K, V>& kv)
2.  
   {
3.  
   if (_root == nullptr)
4.  
   {
5.  
   _root = new Node(kv);
6.  
   _root->_col = BLACK;
7.  
   return true;
8.  
   }
9.  
    
10.  
    Node* parent = nullptr;
11.  
    Node* cur = _root;
12.  
    while (cur)
13.  
    {
14.  
    if (cur->_kv.first < kv.first)
15.  
    {
16.  
    parent = cur;
17.  
    cur = cur->_right;
18.  
    }
19.  
    else if (cur->_kv.first > kv.first)
20.  
    {
21.  
    parent = cur;
22.  
    cur = cur->_left;
23.  
    }
24.  
    else
25.  
    {
26.  
    return false;
27.  
    }
28.  
    }
29.  
     
30.  
    cur = new Node(kv);
31.  
    cur->_col = RED;
32.  
     
33.  
    if (parent->_kv.first < kv.first)
34.  
    {
35.  
    parent->_right = cur;
36.  
    }
37.  
    else
38.  
    {
39.  
    parent->_left = cur;
40.  
    }
41.  
     
42.  
    cur->_parent = parent;
43.  
     
44.  
    while (parent && parent->_col == RED)
45.  
    {
46.  
    Node* grandfater = parent->_parent;
47.  
    assert(grandfater);
48.  
    assert(grandfater->_col == BLACK);
49.  
    // 关键看叔叔
50.  
    if (parent == grandfater->_left)
51.  
    {
52.  
    Node* uncle = grandfater->_right;
53.  
    // 情况一 : uncle存在且为红，变色 继续往上处理
54.  
    if (uncle && uncle->_col == RED)
55.  
    {
56.  
    parent->_col = uncle->_col = BLACK;
57.  
    grandfater->_col = RED;
58.  
    // 继续往上处理
59.  
    cur = grandfater;
60.  
    parent = cur->_parent;
61.  
    }// 情况二 三：uncle不存在 存在且为黑
62.  
    else
63.  
    {
64.  
    // 情况二：右单旋 变色
65.  
    // g
66.  
    // p u
67.  
    // c
68.  
    if (cur == parent->_left)
69.  
    {
70.  
    RotateR(grandfater);
71.  
    parent->_col = BLACK;
72.  
    grandfater->_col = RED;
73.  
    }
74.  
    else
75.  
    {
76.  
    // 情况三：左右单旋 变色
77.  
    // g
78.  
    // p u
79.  
    // c
80.  
    RotateL(parent);
81.  
    RotateR(grandfater);
82.  
    cur->_col = BLACK;
83.  
    grandfater->_col = RED;
84.  
    }
85.  
     
86.  
    break;
87.  
    }
88.  
    }
89.  
    else // (parent == grandfater->_right)
90.  
    {
91.  
    Node* uncle = grandfater->_left;
92.  
    // 情况一
93.  
    if (uncle && uncle->_col == RED)
94.  
    {
95.  
    parent->_col = uncle->_col = BLACK;
96.  
    grandfater->_col = RED;
97.  
    // 继续往上处理
98.  
    cur = grandfater;
99.  
    parent = cur->_parent;
100.  
     }
101.  
     else
102.  
     {
103.  
     // 情况二：左单旋 变色
104.  
     // g
105.  
     // u p
106.  
     // c
107.  
     if (cur == parent->_right)
108.  
     {
109.  
     RotateL(grandfater);
110.  
     parent->_col = BLACK;
111.  
     grandfater->_col = RED;
112.  
     }
113.  
     else
114.  
     {
115.  
     // 情况三：右左单旋 变色
116.  
     // g
117.  
     // u p
118.  
     // c
119.  
     RotateR(parent);
120.  
     RotateL(grandfater);
121.  
     cur->_col = BLACK;
122.  
     grandfater->_col = RED;
123.  
     }
124.  
      
125.  
     break;
126.  
     }
127.  
     }
128.  
      
129.  
     }
130.  
      
131.  
     _root->_col = BLACK;
132.  
     return true;
133.  
     }

四、红黑树的检验

  当我们写完插入时，怎么判断该树是否符合红黑树呢？只是中序打印肯定是不够的，因为中序打印只能说明该树是二叉搜索树。那怎么办呢？

  判断最长路径是否不大于最短路径长度的二倍行不行呢？好像也并不行。为什么呢？那要是还有连续的红节点呢？又或者每条路径的黑色节点的数量不同呢？

  我们发现，当满足性质三和性质四时，就会满足最长路径是否不大于最短路径长度的二倍。同时再判断一下根节点的颜色就行，具体代码如下：

1.  
   public:
2.  
   void InOrder()
3.  
   {
4.  
   _InOrder(_root);
5.  
   cout << endl;
6.  
   }
7.  
    
8.  
   bool IsBalance()
9.  
   {
10.  
    if (_root == nullptr)
11.  
    {
12.  
    return true;
13.  
    }
14.  
     
15.  
    if (_root->_col == RED)
16.  
    {
17.  
    cout << "根节点不是黑色" << endl;
18.  
    return false;
19.  
    }
20.  
     
21.  
    // 黑色节点数量基准值
22.  
    int benchmark = 0;
23.  
    /*Node* cur = _root;
24.  
    while (cur)
25.  
    {
26.  
    if (cur->_col == BLACK)
27.  
    benchmark;
28.  
     
29.  
    cur = cur->_left;
30.  
    }*/
31.  
     
32.  
    return PrevCheck(_root, 0, benchmark);
33.  
    }
34.  
     
35.  
    private:
36.  
    bool PrevCheck(Node* root, int blackNum, int& benchmark)
37.  
    {
38.  
    if (root == nullptr)
39.  
    {
40.  
    //cout << blackNum << endl;
41.  
    //return;
42.  
    if (benchmark == 0)
43.  
    {
44.  
    benchmark = blackNum;
45.  
    return true;
46.  
    }
47.  
     
48.  
    if (blackNum != benchmark)
49.  
    {
50.  
    cout << "某条黑色节点的数量不相等" << endl;
51.  
    return false;
52.  
    }
53.  
    else
54.  
    {
55.  
    return true;
56.  
    }
57.  
    }
58.  
     
59.  
    if (root->_col == BLACK)
60.  
    {
61.  
    blackNum;
62.  
    }
63.  
     
64.  
    if (root->_col == RED && root->_parent->_col == RED)
65.  
    {
66.  
    cout << "存在连续的红色节点" << endl;
67.  
    return false;
68.  
    }
69.  
     
70.  
    return PrevCheck(root->_left, blackNum, benchmark)
71.  
    && PrevCheck(root->_right, blackNum, benchmark);
72.  
    }
73.  
     
74.  
    void _InOrder(Node* root)
75.  
    {
76.  
    if (root == nullptr)
77.  
    {
78.  
    return;
79.  
    }
80.  
     
81.  
    _InOrder(root->_left);
82.  
    cout << root->_kv.first << ":" << root->_kv.second << endl;
83.  
    _InOrder(root->_right);
84.  
    }

五、性能分析

  红黑树的插入操作的平均时间复杂度是O(log n)，其中n是树中节点的数量。这是因为红黑树的插入操作涉及到一系列的旋转和修正操作，但这些操作都是局部的，不会导致整个树的高度增加太多。

  需要注意的是，虽然单次插入操作的时间复杂度是O(log n)，但在一系列插入操作后，为了保持红黑树的平衡性，可能需要进行多次的旋转和修正操作。但由于这些操作的时间复杂度都是常数级别的，不会随着插入操作的增加而显著增加，所以整体插入操作的平均时间复杂度仍然是O(log n)。

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

  AVL树是另一种自平衡二叉搜索树，与红黑树相比，AVL树要求更为严格的平衡性，每个节点的左子树和右子树的高度差（平衡因子）不超过1。这使得AVL树在查找操作上更快，但插入和删除操作可能需要更多的旋转。

六、总结

  红黑树作为一种自平衡二叉搜索树，具有良好的平衡性质和高效的插入、删除、查找等操作，被广泛应用于各种数据结构和算法领域。通过合理的旋转操作和修正过程，红黑树能够保持树的平衡，从而保证了操作的时间复杂度在可接受的范围内。

  在本文中，我们深入探讨了红黑树的原理和实现细节。从基本概念开始，我们介绍了红黑树的定义、特性，然后详细讲解了插入操作的算法和旋转操作。接着，我们讨论了删除操作的实现和修正过程。通过分析插入和删除操作的时间复杂度，我们得出了红黑树在各种操作下的高效性能。

  总的来说，红黑树作为一种经典的数据结构，在算法和计算机科学领域中具有重要地位。通过深入学习和理解红黑树的原理和实现，读者不仅可以拓展自己的数据结构知识，还能够为解决实际问题提供有力的工具和思路。随着计算机科学的不断发展，红黑树及其相关的优化和扩展将继续在各个领域发挥重要作用。

这篇好文章是转载于：学新通技术网