• 【C++ 学习 ㉓】- 详解红黑树

    目录

    一、红黑树的概念和性质

    二、红黑树的两个结论

    三、红黑树节点的定义

    四、红黑树的插入

    五、红黑树的实现

    5.1 - RBT.h

    5.2 - test.cpp

    六、红黑树和 AVL 树的比较

     

    一、红黑树的概念和性质

    红黑树（red-black tree）是这样的一棵二叉搜索树：树中的每个节点的颜色不是红色就是黑色。可以把一棵红黑树视为一棵扩充二叉树，用外部节点表示空指针。其特性描述如下：

    1. 根节点和所有外部节点的颜色是黑色。

    2. 从根节点到外部节点的途中没有连续两个节点的颜色是红色。

      特性 2 意味着如果一个节点的颜色是红色，则它的左、右孩子的颜色必然是黑色。

    3. 对任一节点，所有从该节点到外部节点的路径上都有相同数目的黑色节点。

    二、红黑树的两个结论

    从红黑树中任一节点 x 出发（不包括节点 x），到达任一个外部节点的路径上的黑节点个数叫做节点 x 的黑高度，亦称为节点的阶，记作 bh(x)。红黑树的黑高度定义为其根节点的黑高度。

    下图所示的二叉搜索树就是一棵红黑树，节点上边的数字为该节点的黑高度。

    1. 结论一：对任一节点 x，假设它的黑高度为 r，那么从节点 x 到任一外部节点的路径长度为 r ~ 2r。

      注意：从节点 x 到任一外部节点的路径长度为该路径上的指针的个数。

    2. 结论二：假设 h 是一棵红黑树的高度（不包括外部节点），n 是红黑树中内部节点的个数， r 是红黑树的黑高度，则以下关系式成立：

      (1) ​h \le 2r；

      (2) n \ge 2^r - 1；

      (3) h \le 2log_2^{(n+1)}。

      证明：

      (1) 由结论一即可证明。上图所示的红黑树的高度（不计外部节点）为 2r = 4。

      (2) 因为红黑树的黑高度为 r，即从红黑树的第 1 层到第 r 层没有外部节点，所以内部节点的总数至少为 2^r - 1。在上图所示的红黑树中，红黑树的黑高度为 r = 2，第 1 层和第 2 层总共有 2^r - 1 = 3 个内部节点，而在第 3 层和第 4 层还有 7 个节点，则有 ​n \ge 2^r - 1。

      (3) 由 (2) 可得 r \le log_2^{(n+1)}，结合 (1)，有 ​h \le 2log_2^{(n+1)}。

      由此也可以知道红黑树的搜索、插入、删除操作的时间复杂度为 O(log_2^n​)。

    三、红黑树节点的定义

    1. enum Color
    2. {
    3.     RED,
    4.     BLACK
    5. };
    6. ​
    7. template<class K, class V>
    8. struct RBTNode
    9. {
    10.     RBTNode* _left;
    11.     RBTNode* _right;
    12.     RBTNode* _parent;
    13.     std::pair _kv;
    14.     Color _clr;
    15. ​
    16.     RBTNode(const std::pair& kv = std::pair(), Color clr = RED)
    17.         : _left(nullptr), _right(nullptr), _parent(nullptr), _kv(kv), _clr(clr)
    18.     { }
    19. };

    四、红黑树的插入

    如果插入前树非空，若新节点被染成黑色，将违反红黑树的特性 3，即所有从根节点到外部节点的路径上的黑色节点个数变得不相等了，因此如果插入前树非空，新插入的节点应该被然成红色。

    如果新插入的节点的父节点是黑色节点，则没有违反红黑树的任何特性，不需要做调整，即插入结束；如果新插入的节点的父节点是红色节点，则违反了红黑树的特性 2，即出现了连续两个红色节点，需要做平衡调整。

    设 *cur 为当前节点，它和它的父结点 *parent 都是红色节点，它的祖父节点 *grandparent 是黑色节点，即出现了连续两个红色节点的情形，此时通过考查其叔叔节点 *uncle 做相应的平衡调整。

    1. 如果 *uncle 是红色节点，则将 *parent 和 *uncle 改为黑色节点，将 *grandparent 改为红色节点。例如：

      如果 *grandparent 是根节点，则将其再改为黑色节点，调整完成。

      如果 *grandparent 是子树的根，则其父节点也可能是红色节点，所以还需要继续往上调整。

    2. 如果 *uncle 不存在或者是黑色节点，此时又有以下 4 种情况：

      (1) *parent 是 *grandparent 的左孩子，*cur 是 *parent 的左孩子。在这种情况下，只要做一次右单旋，再将 *parent 改为黑色节点，*grandparent 改为红色节点，就可恢复红黑树的特性，并结束平衡调整。

      (2) *parent 是 *grandparent 的左孩子，*cur 是 *parent 的右孩子。在这种情况下，只要做一次先左后右的双旋转，再将 *cur 改为黑色节点，*grandparent 改为红色节点，就可恢复红黑树的特性，并结束平衡调整。

      (3) *parent 是 *grandparent 的右孩子，*cur 是 *parent 的右孩子。

      (4) *parent 是 *grandparent 的右孩子，*cur 是 *parent 的左孩子。

      情况 (2)、(3) 和情况 (1)、(2) 是镜像的。

     

    五、红黑树的实现

    5.1 - RBT.h

    1. #pragma once
    2. ​
    3. #include 
    4. ​
    5. enum Color
    6. {
    7.     RED,
    8.     BLACK
    9. };
    10. ​
    11. template<class K, class V>
    12. struct RBTNode
    13. {
    14.     RBTNode* _left;
    15.     RBTNode* _right;
    16.     RBTNode* _parent;
    17.     std::pair _kv;
    18.     Color _clr;
    19. ​
    20.     RBTNode(const std::pair& kv = std::pair(), Color clr = RED)
    21.         : _left(nullptr), _right(nullptr), _parent(nullptr), _kv(kv), _clr(clr)
    22.     { }
    23. };
    24. ​
    25. template<class K, class V>
    26. class RBT
    27. {
    28.     typedef RBTNode Node;
    29. public:
    30.     RBT() : _root(nullptr) { }
    31. ​
    32.     ~RBT()
    33.     {
    34.         Destroy(_root);
    35.     }
    36. ​
    37.     bool isValidRBT()
    38.     {
    39.         if (_root == nullptr)
    40.             return true;
    41. ​
    42.         if (_root->_clr == RED)
    43.             return false;
    44. ​
    45.         // 获取从根节点到任一外部节点的路径上的黑色节点的个数
    46.         size_t blackCount = 0;
    47.         Node* cur = _root;
    48.         while (cur)
    49.         {
    50.             if (cur->_clr == BLACK)
    51.                 ++blackCount;
    52.             cur = cur->_left;
    53.         }
    54. ​
    55.         size_t k = 0;  // k 用来路径种的黑色节点个数
    56.         return _isValidRBT(_root, blackCount, k);
    57.     }
    58. ​
    59.     bool insert(const std::pair& kv)
    60.     {
    61.         if (_root == nullptr)
    62.         {
    63.             _root = new Node(kv, BLACK);
    64.             return true;
    65.         }
    66. ​
    67.         Node* parent = nullptr;
    68.         Node* cur = _root;
    69.         while (cur)
    70.         {
    71.             parent = cur;
    72.             if (kv.first < cur->_kv.first)
    73.                 cur = cur->_left;
    74.             else if (kv.first > cur->_kv.first)
    75.                 cur = cur->_right;
    76.             else
    77.                 return false;
    78.         }
    79. ​
    80.         // 如果插入前树非空，新插入的节点应该是红色节点
    81.         cur = new Node(kv, RED); 
    82.         cur->_parent = parent;
    83. ​
    84.         // 出现连续两个红色节点的情形
    85.         while (parent && parent->_clr == RED)
    86.         {
    87.             Node* grandparent = parent->_parent;
    88.             Node* uncle;
    89.             if (grandparent->_left == parent)
    90.                 uncle = grandparent->_right;
    91.             else
    92.                 uncle = grandparent->_left;
    93. ​
    94.             // 如果 *uncle 是红色节点
    95.             if (uncle && uncle->_clr == RED)
    96.             {
    97.                 parent->_clr = uncle->_clr = BLACK;
    98.                 grandparent->_clr = RED;
    99. ​
    100.                 cur = grandparent;
    101.                 parent = cur->_parent;
    102.             }
    103.             else  // 如果 *uncle 不存在或者是黑色节点
    104.             {
    105.                 if (grandparent->_left == parent && parent->_left == cur)
    106.                 {
    107.                     LL(grandparent);
    108.                     parent->_clr = BLACK;
    109.                     grandparent->_clr = RED;
    110.                 }
    111.                 else if (grandparent->_right == parent && parent->_right == cur)
    112.                 {
    113.                     RR(grandparent);
    114.                     parent->_clr = BLACK;
    115.                     grandparent->_clr = RED;
    116.                 }
    117.                 else if (grandparent->_left == parent && parent->_right == cur)
    118.                 {
    119.                     LR(grandparent);
    120.                     cur->_clr = BLACK;
    121.                     grandparent->_clr = RED;
    122.                 }
    123.                 else if (grandparent->_right == parent && parent->_left == cur)
    124.                 {
    125.                     RL(grandparent);
    126.                     cur->_clr = BLACK;
    127.                     grandparent->_clr = RED;
    128.                 }
    129.                 break;
    130.             }
    131.         }
    132.         _root->_clr = BLACK;
    133.         return true;
    134.     }
    135. private:
    136.     void Destroy(Node*& root)
    137.     {
    138.         // 【注意:root 为 _root 或者某个节点的左或右指针的引用】
    139.         if (root == nullptr)
    140.             return;
    141. ​
    142.         Destroy(root->_left);
    143.         Destroy(root->_right);
    144.         delete root;
    145.         root = nullptr;
    146.     }
    147.     
    148.     bool _isValidRBT(Node* root, size_t blackCount, size_t k)
    149.     {
    150.         if (root == nullptr)
    151.         {
    152.             if (blackCount == k)
    153.                 return true;
    154.             else
    155.                 return false;  // 违反了特性 3
    156.         }
    157. ​
    158.         if (root->_clr == BLACK)
    159.         {
    160.             ++k;
    161.         }
    162.         else
    163.         {
    164.             if (root->_parent && root->_parent->_clr == RED)
    165.                 return false;  // 违反了特性 2
    166.         }
    167. ​
    168.         return _isValidRBT(root->_left, blackCount, k)
    169.             && _isValidRBT(root->_right, blackCount, k);
    170.     }
    171. ​
    172.     void LL(Node* parent)
    173.     {
    174.         Node* cur = parent->_left;
    175.         Node* curRight = cur->_right;
    176. ​
    177.         parent->_left = curRight;
    178.         if (curRight)
    179.             curRight->_parent = parent;
    180. ​
    181.         cur->_right = parent;
    182.         Node* tmp = parent->_parent;
    183.         parent->_parent = cur;
    184.         cur->_parent = tmp;
    185. ​
    186.         if (tmp == nullptr)
    187.         {
    188.             _root = cur;
    189.         }
    190.         else
    191.         {
    192.             if (tmp->_left == parent)
    193.                 tmp->_left = cur;
    194.             else
    195.                 tmp->_right = cur;
    196.         }
    197.     }
    198. ​
    199.     void RR(Node* parent)
    200.     {
    201.         Node* cur = parent->_right;
    202.         Node* curLeft = cur->_left;
    203. ​
    204.         parent->_right = curLeft;
    205.         if (curLeft)
    206.             curLeft->_parent = parent;
    207. ​
    208.         cur->_left = parent;
    209.         Node* tmp = parent->_parent;
    210.         parent->_parent = cur;
    211.         cur->_parent = tmp;
    212. ​
    213.         if (tmp == nullptr)
    214.         {
    215.             _root = cur;
    216.         }
    217.         else
    218.         {
    219.             if (tmp->_left == parent)
    220.                 tmp->_left = cur;
    221.             else
    222.                 tmp->_right = cur;
    223.         }
    224.     }
    225. ​
    226.     void LR(Node* parent)
    227.     {
    228.         Node* cur = parent->_left;
    229.         RR(cur);
    230.         LL(parent);
    231.     }
    232. ​
    233.     void RL(Node* parent)
    234.     {
    235.         Node* cur = parent->_right;
    236.         LL(cur);
    237.         RR(parent);
    238.     }
    239. private:
    240.     Node* _root;
    241. };

    5.2 - test.cpp

    1. #include "RBT.h"
    2. #include 
    3. #include 
    4. #include 
    5. using namespace std;
    6. ​
    7. void TestRBT()
    8. {
    9.     srand((unsigned int)time(0));
    10.     size_t N = 10000;
    11.     vector<int> v;
    12.     for (size_t i = 0; i < N; ++i)
    13.     {
    14.         v.push_back(rand());
    15.     }
    16. ​
    17.     RBT<int, int> t;
    18.     for (const auto& e : v)
    19.     {
    20.         t.insert(make_pair(e, e));
    21.         if (!t.isValidRBT())
    22.             cout << "插入操作有误！" << endl;
    23.     }
    24.     cout << "插入完成~" << endl;
    25. }
    26. ​
    27. int main()
    28. {
    29.     TestRBT();
    30.     return 0;
    31. }

    六、红黑树和 AVL 树的比较

    红黑树和 AVL 树的增删查改的效率都很高，时间复杂度为 O(​)，但红黑树不追求极致的平衡，其只需保证最长路径不超过最短路径的 2 倍，相对而言，降低了平衡旋转的次数，所以在经常进行增删的结构中，红黑树的性能比 AVL 树更好，并且红黑树的实现更简单，所以在实际应用中，使用红黑树的也更多。

  • 相关阅读:
    Zookeeper系列——3Zookeeper源码分析之Session管理及请求处理
    《原CSharp》第二回 巧习得元素分类 子不知怀璧其罪
    SD卡使用记录
    Docker部署单节点Kafka
    Entity FrameWork Core教程，从基础应用到原理实战
    如何改变胆小怕事的性格？
    大规模爬虫系统面临的主要挑战及解决思路
    java编程之多线程实战指南（设计模式篇），从基础到避坑
    SpringBoot SpringBoot 开发实用篇 3 测试 3.3 测试类中启动web 环境
    Java 栈和队列的基本使用
  • 原文地址：https://blog.csdn.net/melonyzzZ/article/details/133213928