devbox
黑客灵魂
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

数据结构 - 红黑树_红黑树路径

作者：黑客灵魂 | 2024-06-27 11:57:48

赞

踩

红黑树路径

目录

红黑树的概念

红黑树的性质：

红黑树性质分析：

红黑树结点定义：

红黑树的插入：

新插入结点应当定为黑色还是红色？

新插入结点可能的情况：

红黑树插入红色新结点后，违背规则三的可能情况及相应措施：

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

抽象图：

​编辑

操作（处理方式）：

分析：

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

情况2.1：p是g的左，cur是p的左。u不存在/u存在且为黑

情况2.2：p是g的右，cur是p的右。u不存在/u存在且为黑

情况2.3：p是g的左，cur是p的右。u不存在/u存在且为黑

情况2.4：p是g的右，cur是p的左。u不存在/u存在且为黑

总结：

红黑树完整实现：

红黑树与AVL树的比较

红黑树的概念

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

（红黑树和AVL树都是二叉搜索树，它们的目的都是为了降低树的高度，使其高度接近logN，提高查找效率。只是AVL树要求更严格（可以理解为过于严格）：每个结点的左右子树高度差不超过1，这也导致AVL树插入或删除时旋转次数过多，效率较低（当树的结构经常改变时）。而红黑树是要求没有一条路径的长度大于其他路径长度的二倍，以此确保这个搜索树接近平衡，没有AVL树严格，因此也减少了旋转次数，提高效率（具体看后面））

红黑树的性质：

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

红黑树性质分析：

回顾红黑树的概念：红黑树通过确保没有一条路径会比其他路径长出两倍，以此达到接近平衡。
那么，红黑树的性质如何确保这个结果呢？第四点等价于：根节点到后代叶子节点的路径中，黑色结点的个数相同（此处的叶子节点，可以理解为第五点的空结点，也可以理解为常规叶子结点，都一样）。黑色结点的个数相同，也就是最短的路径可以理解为x个黑，而最长的就是黑红黑红黑红...共x对（此处也因为第三点的限制：树中不能有连续的红色结点）。因此最短，最长路径的长度正好是二倍关系，其他路径的长度也就能保证在这个范围之内，从而确保红黑树接近平衡。

因此，只要确保第四点：每个结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数目的黑色结点。就可以确保没有一条路径超过其他路径长度的两倍。从而确保红黑树接近平衡，以此提高搜索效率。当然，其他的性质也要遵守，只是第四点相对关键。

红黑树结点定义：

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

还是那一套，没啥意思，加了一个枚举数据成员，用于保存结点颜色。

红黑树的插入：

  1. bool Insert(const pair<K, V>& kv)
  2.     {
  3.         if(_root == nullptr) {
  4.             _root = new Node(kv);
  5.             _root->_col = BLACK;
  6.             return true;
  7.         }
  8.         Node* parent = nullptr;
  9.         Node* cur = _root;
  10.         while(cur != nullptr) {
  11.             if(kv.first > cur->_kv.first) {
  12.                 parent = cur;
  13.                 cur = cur->_right;
  14.             }
  15.             else if(kv.first < cur->_kv.first) {
  16.                 parent = cur;
  17.                 cur = cur->_left;
  18.             }
  19.             else {
  20.                 return false;
  21.             }
  22.         }
  23.         cur = new Node(kv);
  24.         cur->_col = RED;
  25.         if(kv.first > parent->_kv.first) {
  26.             parent->_right = cur;
  27.         }
  28.         else {
  29.             parent->_left = cur;
  30.         }
  31.         cur->_parent = parent;
  32.  
  33.         // 插入新结点成功，且为红色。进行判断
  34.         // 进入下方循环后，parent一定为红，则parent一定不是根节点，则parent一定有父亲，有没有兄弟不一定。
  35.         while(parent && parent->_col == RED) {
  36.             Node* grandfather = parent->_parent;
  37.             Node* uncle = nullptr;
  38.             if(parent == grandfather->_left)
  39.                 uncle = grandfather->_right;
  40.             else
  41.                 uncle = grandfather->_left;
  42.  
  43.             // 判断叔叔的情况，决定处理方式
  44.             if(uncle && uncle->_col == RED) {
  45.                 // 叔叔存在且为红
  46.                 parent->_col = BLACK;
  47.                 uncle->_col = BLACK;
  48.  
  49.                 grandfather->_col = RED;
  50.                 cur = grandfather;
  51.                 parent = cur->_parent;
  52.             }
  53.             else {
  54.                 // 叔叔不存在或者叔叔存在且为黑
  55.                 if(parent == grandfather->_left && cur == parent->_left) {
  56.                     // 此时，左左，右单旋+变色
  57.                     // 先变色也可以
  58.                     parent->_col = BLACK;
  59.                     grandfather->_col = RED;
  60.                     RotateR(grandfather);
  61.                 }
  62.                 else if(parent == grandfather->_right && cur == parent->_right) {
  63.                     // 右右，左单旋
  64.                     parent->_col = BLACK;
  65.                     grandfather->_col = RED;
  66.                     RotateL(grandfather);
  67.                 }
  68.                 else if(parent == grandfather->_right && cur == parent->_left) {
  69.                     // cur为红，parent为红，grandfather为黑。
  70.                     // 右左双旋。
  71. //                    RotateR(parent);
  72. //                    RotateL(grandfather);
  73. //                    // 记住这里是上黑，下面俩红即可。
  74. //                    cur->_col = BLACK;
  75. //                    grandfather->_col = RED;
  76.  
  77.                     // 第二种实现方法，即单旋后变为双旋。
  78.                     RotateR(parent);
  79.                     std::swap(cur, parent);
  80.                     parent->_col = BLACK;
  81.                     grandfather->_col = RED;
  82.                     RotateL(grandfather);
  83.                 }
  84.                 else if(parent == grandfather->_left && cur == parent->_right) {
  85. //                    RotateL(parent);
  86. //                    RotateR(grandfather);
  87. //                    // 记住这里是上黑，下面俩红即可。
  88. //                    cur->_col = BLACK;
  89. //                    grandfather->_col = RED;
  90.                     RotateL(parent);
  91.                     std::swap(cur, parent);
  92.                     parent->_col = BLACK;
  93.                     grandfather->_col = RED;
  94.                     RotateR(grandfather);
  95.                 }
  96.  
  97.                 break;
  98.             }
  99.             if(cur == _root) {
  100.                 cur->_col = BLACK;
  101.             }
  102.         }
  103.         return true;
  104.     }

红黑树是一种二叉搜索树，因此，和AVL树一样，开始的插入逻辑都是二叉搜索树的插入方式，找到位置之后插入新建结点。

在讲红黑树的插入之前，有一个点很重要。即我们必须意识到：红黑树通过满足性质和规定，从而保证没有一条路径超过其他路径长度的二倍，从而保证树的高度接近logN，从而确保树的查找效率。因此，我们在考虑红黑树的插入时，只需要确保怎么才能不破坏红黑树的性质，破坏之后怎么处理即可。

新插入结点应当定为黑色还是红色？

若新插入结点定为黑色，则违背红黑树规定4。若新插入结点定为红色，则可能违背规定3。

违背规定四：导致从根节点到该新插入结点的路径中黑色结点个数比其他路径都多1，这时候是很难处理的。而违背规定三也只是概率性问题，只有当新插入结点的父节点为红色时，才需要处理，且这里的处理方式也一定比处理规定四简单很多。（事实上，插入黑色结点违背规定四如何处理我并不知道，但是新插入红色结点总是合适的）

故，我们将每个除了根节点之外的新结点都定为红色。

新插入结点可能的情况：

1. 整棵树为空树，直接插入黑色根节点即可。

2. 新插入红色结点的父节点为黑色，插入成功。

3. 新插入红色结点的父节点为红色，违背性质3，此时需要采取措施。

下面我们讨论当新插入结点的父节点为红色时，可能的情况及相应的操作：

红黑树插入红色新结点后，违背规则三的可能情况及相应措施：

首先，新插入结点一定为红色，且此时父节点为红色，祖父结点为黑色。这是一定的。（逻辑很简单）

我们考虑的是此时新插入结点的叔叔结点的情况，从而对应不同操作：

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

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

抽象图：

操作（处理方式）：

1. p变为黑，u变为黑，g变为红。

2. 若g为整颗红黑树的根节点，则再将其变为黑。
（因为红黑树规定根节点必须为黑，此时变为黑色之后，也就相当于每条路径多一个黑色结点，并不影响红黑树的性质）

3. 若g为子树的根节点，则将其当作cur，继续向上循环检查。
（因为此时处理完之后，对于这颗子树来说，每条路径的黑色结点的个数没有变，仍然是1，但是此时祖父节点变为红，可能祖父的父节点此时也为红，违背性质三，故需要循环向上检查）

分析：

0. 这样处理其实也能理解啊... 此时违背规则三，把p变为黑，可是这样g的左子树凭空多了一个黑色，故把根结点变为红，叔叔变为黑。这样子树的每条路径的黑色结点个数就不变了。

1. 情况一的结果是：将祖父结点当作cur继续向上检查，因此，上方抽象图中，cur也不一定是新增结点，只有当abcde子树为空时，cur为新增结点，否则，cur只是之前情况一处理完之后的祖父结点，由黑变为了红。（这里抽象图的实例情况有很多，可以无限延展下去。有兴趣就画一些。）但是总之，情况一概括了当叔叔结点存在且为红的处理方式。

2. 红黑树和AVL树不同，情况一这里，并不关心p和u是g的左还是右，cur是p的左还是右，只关心叔叔的情况。

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

说明：此时把p（父亲结点）直接变为红，左子树的路径中多了一个黑色，此时叔叔结点不存在/存在且为黑，就无法像情况一一样处理了。

以上为情况二的一种... 叔叔存在和叔叔不存在。它们的处理方式是一样的。
实际上我想说的是：

若叔叔不存在，则cur一定为新增结点。（因为g的右子树无黑结点）
若叔叔存在且为黑，则cur一定不是新增结点，一定是某情况一处理完之后的祖父结点。（因为g的右子树有黑结点）那么，这里为什么不可能是情况二处理完之后呢？没错，情况二处理完之后就不需要循环向上了（具体见情况二的结果与作用）

但是，不管叔叔结点存在且为黑还是不存在，处理方式都是一样的！（见下文），下面举例时，我只举出叔叔存在且为黑的抽象图，叔叔不存在的情况就是对应的简化情况，cur为新增的情况，很好理解。

情况2.1：p是g的左，cur是p的左。u不存在/u存在且为黑

单旋+变色：g进行右单旋，p变为黑，g变为红。（此时p是整颗子树的根节点）

情况2.2：p是g的右，cur是p的右。u不存在/u存在且为黑

单旋+变色：g进行左单旋， p变为黑，g变为红。（此时p是整颗子树的根节点）（旋转后的结果图略了，类比情况2.1）

情况2.3：p是g的左，cur是p的右。u不存在/u存在且为黑

此处p是g的左，cur是p的右，应当双旋+变色。此时第一次单旋后，就变为了情况2.1，按照情况2.1处理即可。

左单旋之后，和2.1不同的是p和cur的位置，故你可以先swap(cur, p)。然后按照情况2.1一样处理。也可以不swap，直接右旋+变色，但是此时变色是变cur和g，不同于情况2.1的g和u

双旋+变色：p进行左单旋，g进行右单旋。swap之后变色：p变为黑，g变为红。（不swap直接变色：cur变黑，g变红）

情况2.4：p是g的右，cur是p的左。u不存在/u存在且为黑

双旋+变色：p进行右单旋，g进行左单旋。swap(cur, p)之后，p变黑，g变红。（不swap，cur变黑，g变红）

此处和2.3原理相同，在第一次p进行右单旋之后，就变为了2.2的情况，只是cur和p的位置不同。

总结：

综上，情况二的宗旨为：u不存在/u存在且为黑，此时仅仅像情况一一样变色是做不到的，需要旋转+变色。并且情况二和情况一不同的是：情况一不在乎左右之分。而情况二的p与g关系，cur与p的关系将直接决定如何旋转，这里类似AVL树的旋转，只是没有了平衡因子。

情况二不管2.1 2.2 2.3 2.4 进行旋转+变色后，不需要再将根节点当作cur向上处理，因为情况二在旋转变色后，子树根节点一定为黑，并且也同时消除了连续红色结点。故不需要向上处理。

在红黑树的Insert函数中，最后一个while循环就是处理父节点为红的情况的。

红黑树完整实现：

  1. //
  2. // Created by yangzilong on 2022/11/11.
  3. //
  4.  
  5. #ifndef STL_RBTREE_H
  6. #define STL_RBTREE_H
  7. #include <utility>
  8. #include <iostream>
  9. #include <vector>
  10. using namespace std;
  11. enum Color
  12. {
  13.     RED,
  14.     BLACK
  15. };
  16.  
  17. template< class K, class V >
  18. struct RBTreeNode
  19. {
  20.     RBTreeNode(const pair<K, V>& kv)
  21.     :_left(nullptr), _right(nullptr), _parent(nullptr), _kv(kv)
  22.     {   }
  23.  
  24.     RBTreeNode<K, V>* _left;
  25.     RBTreeNode* _right;
  26.     RBTreeNode* _parent;
  27.     pair<K, V> _kv;
  28.     Color _col;
  29. };
  30.  
  31. template <class K, class V>
  32. class RBTree
  33. {
  34.     typedef RBTreeNode<K, V> Node;
  35. public:
  36.     bool Insert(const pair<K, V>& kv)
  37.     {
  38.         if(_root == nullptr) {
  39.             _root = new Node(kv);
  40.             _root->_col = BLACK;
  41.             return true;
  42.         }
  43.         Node* parent = nullptr;
  44.         Node* cur = _root;
  45.         while(cur != nullptr) {
  46.             if(kv.first > cur->_kv.first) {
  47.                 parent = cur;
  48.                 cur = cur->_right;
  49.             }
  50.             else if(kv.first < cur->_kv.first) {
  51.                 parent = cur;
  52.                 cur = cur->_left;
  53.             }
  54.             else {
  55.                 return false;
  56.             }
  57.         }
  58.         cur = new Node(kv);
  59.         cur->_col = RED;
  60.         if(kv.first > parent->_kv.first) {
  61.             parent->_right = cur;
  62.         }
  63.         else {
  64.             parent->_left = cur;
  65.         }
  66.         cur->_parent = parent;
  67.  
  68.         // 插入新结点成功，且为红色。进行判断
  69.         // 进入下方循环后，parent一定为红，则parent一定不是根节点，则parent一定有父亲，有没有兄弟不一定。
  70.         while(parent && parent->_col == RED) {
  71.             Node* grandfather = parent->_parent;
  72.             Node* uncle = nullptr;
  73.             if(parent == grandfather->_left)
  74.                 uncle = grandfather->_right;
  75.             else
  76.                 uncle = grandfather->_left;
  77.  
  78.             // 判断叔叔的情况，决定处理方式
  79.             if(uncle && uncle->_col == RED) {
  80.                 // 叔叔存在且为红
  81.                 parent->_col = BLACK;
  82.                 uncle->_col = BLACK;
  83.  
  84.                 grandfather->_col = RED;
  85.                 cur = grandfather;
  86.                 parent = cur->_parent;
  87.             }
  88.             else {
  89.                 // 叔叔不存在或者叔叔存在且为黑
  90.                 if(parent == grandfather->_left && cur == parent->_left) {
  91.                     // 此时，左左，右单旋+变色
  92.                     // 先变色也可以
  93.                     parent->_col = BLACK;
  94.                     grandfather->_col = RED;
  95.                     RotateR(grandfather);
  96.                 }
  97.                 else if(parent == grandfather->_right && cur == parent->_right) {
  98.                     // 右右，左单旋
  99.                     parent->_col = BLACK;
  100.                     grandfather->_col = RED;
  101.                     RotateL(grandfather);
  102.                 }
  103.                 else if(parent == grandfather->_right && cur == parent->_left) {
  104.                     // cur为红，parent为红，grandfather为黑。
  105.                     // 右左双旋。
  106. //                    RotateR(parent);
  107. //                    RotateL(grandfather);
  108. //                    // 记住这里是上黑，下面俩红即可。
  109. //                    cur->_col = BLACK;
  110. //                    grandfather->_col = RED;
  111.  
  112.                     // 第二种实现方法，即单旋后变为双旋。
  113.                     RotateR(parent);
  114.                     std::swap(cur, parent);
  115.                     parent->_col = BLACK;
  116.                     grandfather->_col = RED;
  117.                     RotateL(grandfather);
  118.                 }
  119.                 else if(parent == grandfather->_left && cur == parent->_right) {
  120. //                    RotateL(parent);
  121. //                    RotateR(grandfather);
  122. //                    // 记住这里是上黑，下面俩红即可。
  123. //                    cur->_col = BLACK;
  124. //                    grandfather->_col = RED;
  125.                     RotateL(parent);
  126.                     std::swap(cur, parent);
  127.                     parent->_col = BLACK;
  128.                     grandfather->_col = RED;
  129.                     RotateR(grandfather);
  130.                 }
  131.  
  132.                 break;
  133.             }
  134.             if(cur == _root) {
  135.                 cur->_col = BLACK;
  136.             }
  137.         }
  138.         return true;
  139.     }
  140.  
  141.  
  142.     void InOrder()
  143.     {
  144.         _InOrder(_root);
  145.         cout << endl;
  146.     }
  147.  
  148.     // 看颜色还是看高度？
  149.     // 看颜色，因为高度正确不一定是红黑树
  150.     bool IsBalance()
  151.     {
  152.         if(_root == nullptr)
  153.             return true;
  154.         if(_root->_col == RED) {
  155.             cout << "根节点为红色，错误" << endl;
  156.             return false;
  157.         }
  158.         int baseNum = 0;
  159.         return PrevCheck(_root, 0, 0);
  160.     }
  161.  
  162. private:
  163.     bool PrevCheck(Node* root, int baseNum, int blackNum)
  164.     {
  165.         if(root == nullptr)
  166.         {
  167.             if(baseNum == 0) {
  168.                 baseNum = blackNum;
  169.                 return true;
  170.             }
  171.             else if(blackNum != baseNum){
  172.                 cout << "某条路径黑色结点数量不同，错误" << endl;
  173.                 return false;
  174.             }
  175.             else
  176.                 return true;
  177.         }
  178.         if(root->_col == BLACK)
  179.             blackNum++;
  180.         else {
  181.             if((nullptr != root->_left && root->_left->_col == RED) || (nullptr != root->_right && root->_right->_col == RED)) {
  182.                 cout << "出现连续红色结点，错误" << endl;
  183.                 return false;
  184.             }
  185.         }
  186.         return PrevCheck(root->_left, baseNum, blackNum)
  187.             && PrevCheck(root->_right, baseNum, blackNum);
  188.     }
  189.  
  190.     void _InOrder(Node* root)
  191.     {
  192.         if (root == nullptr)
  193.         {
  194.             return;
  195.         }
  196.         _InOrder(root->_left);
  197.         cout << root->_kv.first << ":" << root->_kv.second << endl;
  198.         _InOrder(root->_right);
  199.     }
  200. private:
  201.     void RotateL(Node* parent)
  202.     {
  203.         Node* subR = parent->_right;
  204.         Node* subRL = subR->_left;  // 可能为空
  205.  
  206.         parent->_right = subRL;
  207.         if(subRL)
  208.             subRL->_parent = parent;
  209.  
  210.         subR->_left = parent;
  211.         Node* ppNode = parent->_parent;  // 修改parent->parent之前，保存原先parent->parent
  212.         parent->_parent = subR;
  213.  
  214.         if(parent == _root)
  215.         {
  216.             _root = subR;
  217.             subR->_parent = nullptr;
  218.         }
  219.         else
  220.         {
  221.             if(parent == ppNode->_right) {
  222.                 ppNode->_right = subR;
  223.                 subR->_parent = ppNode;
  224.             }
  225.             else {
  226.                 ppNode->_left = subR;
  227.                 subR->_parent = ppNode;
  228.             }
  229.         }
  230.     }
  231.  
  232.     void RotateR(Node* parent)
  233.     {
  234.         Node* subL = parent->_left;
  235.         Node* subLR = subL->_right;
  236.  
  237.         parent->_left = subLR;
  238.         if(subLR)
  239.             subLR->_parent = parent;
  240.  
  241.         Node* ppNode = parent->_parent;
  242.         parent->_parent = subL;
  243.         subL->_right = parent;
  244.  
  245.         if(parent == _root) {
  246.             _root = subL;
  247.             subL->_parent = nullptr;
  248.         }
  249.         else {
  250.             if(parent == ppNode->_right) {
  251.                 ppNode->_right = subL;
  252.                 subL->_parent = ppNode;
  253.             }
  254.             else {
  255.                 ppNode->_left = subL;
  256.                 subL->_parent = ppNode;
  257.             }
  258.         }
  259.     }
  260. private:
  261.     RBTreeNode<K, V>* _root = nullptr;
  262. };

依旧没有红黑树的删除。包含红黑树自检代码，就是一个递归判断。红黑树的左旋右旋与AVL树的相同，只是没有了平衡因子。

红黑树与AVL树的比较

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

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/黑客灵魂/article/detail/762447
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号