C++-第十三章：红黑树

目录

第一节：红黑树的特征

第二节：实现思路

        2-1.插入

                2-1-1.unc为红

                2-1-2.cur为par的左子树，且par为gra的左子树(cur在最左边)

                        2-1-2-1.unc不存在

                        2-1-2-2.unc为黑

                2-1-3.cur为par的右子树，且par为gra的右子树(cur在最右侧)

                        2-1-3-1.unc不存在

                        2-1-3-2.unc为黑

                2-1-4.cur为par的左子树，且par为gra的右子树（cur在左内侧）

                        2-1-4-1.unc无关

                2-1-5.cur为par的右子树，且par为gra的左子树(cur在右内侧)

                        2-1-5-1.unc无关

                2-1-6.par为黑

        总结：

第三节：代码实现

        2-1.Node类

        2-2.RBTree类

 Gitee：红黑树 · 转调/C++ - 码云 - 开源中国

第四节：测试

下期预告：

---

第一节：红黑树的特征

        红黑树并没有AVL树那种严格的平衡因子限制，它只保证最长路径的长度不会超过最短路径的两倍。

        红黑树的特征如下：

        （1）节点分为两种"红"与"黑"

        （2）根节点是"黑"

        （3）"红"节点的孩子都是"黑"节点——不存在连续的"红"节点

        （4）对于每个节点，从该节点开始，到叶子节点结束，的所有简单路径均包含相同数量的"黑"节点

        上述的"红"与"黑"并不是指颜色，只是区分两种节点的方法。

第二节：实现思路

        2-1.插入

        插入时优先将新增节点设置为红色，否则因为规则(4)的制约，黑节点会影响多条路径。

        假如新插入的节点为cur，它的父亲为par，爷爷为gra，父亲的兄弟为unc，那么一共有多种情况。

        当par为红时，因为规则(2)，一定有一个黑色gra，只有一个unc是未知的

        所以先讨论par为红时的情况：

                2-1-1.unc为红

                                

        这种情况就违反了规则(3)，所以要进行改变：

        将par、unc变为黑色，gra变为红色。

                ​​​​​​​        ​​​​​​​        

        此时这个子树已经符合红黑树的规则了，但是对于gra之上的节点来说，变红的gra等价于插入了一个红色的cur，所以又要将gra作为cur，继续向上调整，直到根或者par为"黑"。这是一种递归的思想。

        其次，如果gra就是root，那么根据规则(2)还需要把gra变为黑色。

                2-1-2.cur为par的左子树，且par为gra的左子树(cur在最左边)

                        2-1-2-1.unc不存在

                                        

        此时要在gra和par之间进行右单旋，旋转方式和AVL树的右单旋一致。

        然后将gra变红，par变黑。

        因为par已经变成黑色了，所以不再向上更新。

                        2-1-2-2.unc为黑

                                

        此时也执行与2-1-2-1相同的操作，即在par和gra之间进行右单旋；

        然后将gra变红，par变黑。

        它也不用再向上更新了。

        总结： cur在最左边时，gra和par右单旋+变色。

                2-1-3.cur为par的右子树，且par为gra的右子树(cur在最右侧)

                        2-1-3-1.unc不存在

                        2-1-3-2.unc为黑

        这两种情况和2-1-2的位置情况相反，cur从最左变到了最右，处理方法也类似，只是把右单旋操作变成了左单旋操作。

        总结：cur在最右侧时，gra和par左单旋+变色 

                2-1-4.cur为par的左子树，且par为gra的右子树（cur在左内侧）

                        2-1-4-1.unc无关

        ​​​​​​​        ​​​​​​​        ​​​​​​​        ​​​​​​​        

        此时cur在左内测，先对par和cur使用一次左单旋：

        与2-1-3相比，虽然par和cur的位置不一样，但是par和cur都是红色，将par视作cur，cur视作par之后，它就变成了2-1-3的情况了。

        所以接下来进行右单旋+变色即可。

        之前就行进行了一次左单旋，所以cur在左内侧的情况使用右左双旋+cur和gra互变颜色。

                2-1-5.cur为par的右子树，且par为gra的左子树(cur在右内侧)

                        2-1-5-1.unc无关

        此时cur在右内侧，所以使用右左双旋+cur和gra互变颜色。

        最后是par为黑的情况。

                2-1-6.par为黑

        此时不用做任何改变，因为cur本来就是红色，不违反任何规则。

        总结：

        综上，其实一共就两种情况：

        （1）par为红时：一定有一个黑色的gra，unc为变量

                a.unc为红：

                          Ⅰ.par、unc变黑，gra变红 继续向上调整

                b.unc为黑/不存在：

                          Ⅰ.cur在外侧：单旋+par、gra变色  然后直接结束

                          Ⅱ .cur在内侧：双旋+cur、gra变色  然后直接结束

        （2）par为黑时：直接结束     

        同搜索二叉树，使用替代法：C++-第十章：搜索二叉树-CSDN博客

第三节：代码实现

        将总结整理成代码。

        2-1.Node类

         使用枚举enum对节点进行"红"、"黑"分类，并且节点初始为"红"：

	enum NodeType{RED = 0,BLACK = 1};template<class T>class Node{public:Node<T>* _left = nullptr;Node<T>* _right = nullptr;Node<T>* _parent = nullptr;T val;NodeType _type = RED;};

        2-2.RBTree类

        这里直接给出核心代码：

namespace zd
{template<class T>class RBTree{public:// 插入函数void Insert(const T& val){// 没有节点就初始化根节点if (_root == nullptr){_root = new Node<T>;_root->_val = val;// 记得根的颜色一定是黑_root->_type = BLACK;}Node<T>* cur = _root;Node<T>* parent = nullptr;while (cur){if (cur->_val < val){parent = cur;cur = cur->_right;}else if (cur->_val > val){parent = cur;cur = cur->_left;}else{// 不允许存储重复的valreturn;}}cur = new Node<T>;cur->_val = val;if (parent->_val > cur->_val){parent->_left = cur;	}else{parent->_right = cur;}cur->_parent = parent;// 使红黑树符合规则Balance(cur);}void _Print(Node<T>* root){if (root == nullptr) return;_Print(root->_left);std::cout << root->_val << " ";_Print(root->_right);}// 中序遍历打印void Print(){_Print(_root);}private:// 平衡红黑树void Balance(Node<T>* cur){// 只有上一个gra才可以递归到根，将根变为黑色并退出if (cur == _root){_root->_type = BLACK;return;}Node<T>* par = cur->_parent;if (par->_type == BLACK) // 黑色直接结束{return;}else // 红色{Node<T>* gra = par->_parent;Node<T>* unc;if (par == gra->_left)unc = gra->_right;elseunc = gra->_left;// unc存在且为红if (unc && unc->_type == RED){// par、unc变黑par->_type = unc->_type = BLACK;// gra变红gra->_type = RED;// 递归调用自己,继续向上调整Balance(gra);}// unc为黑/不存在 && cur在左外侧else if (cur == par->_left && par == gra->_left){RotateR(gra); // 右单旋// 变色par->_type = BLACK;gra->_type = RED;return;}// unc为黑/不存在 && cur在右外侧else if (cur == par->_right && par == gra->_right){RotateL(gra); // 左单旋// 变色par->_type = BLACK;gra->_type = RED;return;}// unc为黑/不存在 && cur在左内侧else if (cur == par->_right && par == gra->_left){RotateLR(gra); // 左右双旋// 变色cur->_type = BLACK;gra->_type = RED;return;}// unc为黑/不存在 && cur在右内侧else if (cur == par->_left && par == gra->_right){RotateRL(gra); // 右左双旋// 变色cur->_type = BLACK;gra->_type = RED;return;}}}// 右单旋void RotateR(Node<T>* gra){Node<T>* par = gra->_left;gra->_left = par->_right;if (gra->_left)gra->_left->_parent = gra;par->_right = gra;// 正确连接par和gra的父亲if (gra == _root){_root = par;}else{if (gra->_parent->_left == gra)gra->_parent->_left = par;elsegra->_parent->_right = par;}par->_parent = gra->_parent;gra->_parent = par;}// 左单旋void RotateL(Node<T>* gra){Node<T>* par = gra->_right;gra->_right = par->_left;if (gra->_right)gra->_right->_parent = gra;par->_left = gra;// 正确连接par和gra的父亲if (gra == _root){_root = par;}else{if (gra->_parent->_left == gra)gra->_parent->_left = par;elsegra->_parent->_right = par;}par->_parent = gra->_parent;gra->_parent = par;}// 左右双旋void RotateLR(Node<T>* gra){Node<T>* par = gra->_left;RotateL(par);RotateR(gra);}// 右左双旋void RotateRL(Node<T>* gra){Node<T>* par = gra->_right;RotateR(par);RotateL(gra);}private:Node<T>* _root = nullptr;};
};

        我们还需要一个函数来验证红黑树，验证规则如下：

        （1）根为黑

        （2）任意红色节点的父亲为黑

        （3）以任意节点为起点，到叶子节点的路径上的黑色节点数量相等

                方法：每个节点记录最左路径上的黑色节点数量为标准，其他路径和它不一样，那就说明不是红黑树。

        

        将上述规则实现成代码：

		// 验证红黑树bool IsRBTree(){// 验证根的颜色if (_root->_type == RED)return false;// 检查红节点的父亲都是黑节点bool ret1 = RedOfBlack(_root);// 遍历树,每个节点检查自己的路径上的黑色节点是否相同bool ret2 = BlackIsEq(_root);if (ret1 == false)printf("出现连续红\n");if (ret2 == false)printf("黑色数量不一致\n");return ret1 && ret2;}// 检查连续红节点bool RedOfBlack(Node<T>* root){if (root == nullptr) return true;// 验证红色节点的父亲为黑色if (root->_type == RED){if (root->_parent->_type == RED)return false;}return RedOfBlack(root->_left) && RedOfBlack(root->_right);}// 检查路径黑节点数量bool BlackIsEq(Node<T>* root){if (root == nullptr) return true;// 获得最左路径黑节点数量int Bc = 0;Node<T>* cur = root;while (cur){if (cur->_type == BLACK)Bc++;cur = cur->_left;}int otherPath = root->_type == BLACK ? 1 : 0; // 其他路径的节点数量return _BlackIsEq(root->_left,Bc,otherPath) && _BlackIsEq(root->_right, Bc, otherPath);}bool _BlackIsEq(Node<T>* root, int Bc, int oP){if (root == nullptr){if (Bc == oP) return true;return false;}if (root->_type == BLACK){oP++;}return _BlackIsEq(root->_left, Bc, oP) && _BlackIsEq(root->_right,Bc,oP);}

 Gitee：红黑树 · 转调/C++ - 码云 - 开源中国

第四节：测试

        生成多个随机数进行测试即可：

#include "RBTree.hpp"
#include <time.h>
int main()
{zd::RBTree<int> tree;srand(time(nullptr));int i = 100;while (i--){int x = rand();tree.Insert(x);}tree.Print();std::cout << tree.IsRBTree() << std::endl;return 0;
}

下期预告：

        第十四章将学习哈希表的原理，并自己实现一个简单的哈希表。