网站导航
> 文章列表 > C++之红黑树

C++之红黑树

网友: 文章列表 2024-03-21 18:32:56

C++之红黑树

文章目录

  • 前言
  • 一、概念
  • 二、性质
  • 三、结点的定义
  • 四、红黑树的结构
  • 五、插入操作
    • 1.插入代码
    • 2.左单旋
    • 3.右单旋
    • 4.插入新结点的情况分析与总结
      • 第一步、按照搜索二叉树的规则插入新结点
      • 第二步、分析插入结点后红黑树的性质是否被破坏
      • 动态演示：
  • 六、验证红黑树
    • 1.检测是否满足二叉搜索树
    • 2.检测是否满足红黑树性质
  • 七、红黑树与AVL树的比较
  • 总结

前言

前面一节我们介绍了平衡搜索二叉树AVL树，我们知道，AVL树虽然查找效率很高，但是不能过多的修改，因为它为了保持平衡要不断的进行旋转。我们今天介绍的红黑树也是一种平衡搜索树，不过它所要求的平衡没有AVL树那么严格，因此对它进行修改操作时所要进行的旋转比AVL树要进行的旋转少。

一、概念

红黑树，一种二叉搜索树，它额外在每一个结点上增加一个表示结点颜色的存储位，有Red和Black两种可能。
通过对任意一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路径会比其他路径长处二倍，因此它是接近平衡的。
C++之红黑树

二、性质

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

三、结点的定义

//结点的颜色enum color{RED,BLACK};

//结点的定义template<typename T>struct RBnode//红黑树的结点(三叉链){RBnode(T data):_data(data), _parent(nullptr), _left(nullptr), _right(nullptr), col(RED){}T _data;//数据RBnode* _parent;//父节点(为了方便实现旋转)RBnode* _left;//左孩子RBnode* _right;//右孩子color _col;//颜色};

看到这里，相信大家会有一个疑问:为什么默认新插入的结点颜色是红色？
答：如果我们将新结点的颜色设置为黑色，那么它一定会违背性质4（即，对于每一个结点，从该节点到其所有后代叶子结点的简单路径上，均包含相同数目的黑色结点），这样我们就需要大幅度的在这棵树上进行调整（几乎需要所有路径进行调整），才能使它再次符合性质4；
如果我们将新结点颜色设置为红色，它有可能违背性质3（即，如果一个结点是红色，那么它的两个孩子结点是黑色），也有一定的可能不违背，即使违背性质3它所带来的后果比违背性质4严重性小很多，我们可以通过几次旋转（只对它所在的路径进行调整）使它重新符合性质3。
因为我们新插入一个结点，它不是黑色就是红色，因此一定会违反一条性质，我们选择违反后果较小的性质3。

四、红黑树的结构

五、插入操作

1.插入代码

		bool insert(const pair<K, V>& kv){Node* newnode = new RBnode<K,V>(kv);if (!_root)//如果根节点为空，则新插入的结直接就是根节点{_root = newnode;}else{Node* cur = _root;Node* parent = cur;while (cur){parent = cur;if (cur->_kv.first > kv.first){cur = cur->_left;}else if (cur->_kv.first < kv.first){cur = cur->_right;}else//树中已经有这个结点，插入失败{return false;}}cur = newnode;if (parent->_kv.first > cur->_kv.first){parent->_left = cur;}else{parent->_right = cur;}cur->_parent = parent;Node* Grandpa = parent->_parent;Node* uncle = nullptr;while(Grandpa && parent->_col == RED)//如果父节点不是黑色,且父节点不是根结点{if (parent == Grandpa->_left)//定义叔叔结点{uncle = Grandpa->_right;}else{uncle = Grandpa->_left;}if (uncle->_col == RED)//如果叔叔存在且为红{Grandpa->_col = RED;parent->_col = uncle->_col = BLACK;}else//如果叔叔不存在，或者存在且为黑{//p是g的右孩子，c是p的右孩子（左单旋）if (parent == Grandpa->_right && cur == parent->_right){Rotetal(Grandpa);Grandpa->_col = RED;parent->_col = BLACK;}//p是g的左孩子，c是p的左孩子（右单旋）else if (parent == Grandpa->_left && cur == parent->_left){Rotetal(Grandpa);Grandpa->_col = RED;parent->_col = BLACK;}//p是g的左孩子，c是p的右孩子（左右双旋）else if (parent == Grandpa->_left && cur == parent->_right){//先以parent为轴进行左单旋Rotetal(parent);//再以Grandpa为轴进行右单旋Rotetar(Grandpa);//更新颜色cur->_col = BLACK;Grandpa->_col = parent->_col = RED;}//p是g的右孩子，c是p的左孩子（右左双旋）else if (parent == Grandpa->_right && cur == parent->_left){//先以parent为轴进行右单旋Rotetar(parent);//再以Grandpa为轴进行左单旋Rotetal(Grandpa);//更新颜色cur->_col = BLACK;Grandpa->_col = parent->_col = RED;}//旋转之后就符合性质4了，因此不用再继续更新break;}cur = parent;parent = Grandpa;Grandpa = Grandpa->_parent;}if (_root->_col == RED)//如果到最后更新到根节点，导致根节点为红色，为了满足性质2（根节点是黑色），就要将根结点置为黑色{_root->_col = BLACK;}}return true;}

2.左单旋

		//左单旋void Rotetal(Node* parent){Node* SubR = parent->_right;Node* SubRL = SubR->_left;Node* Grandpa = parent->_parent;parent->_parent = SubR;parent->_right = SubRL;if (SubRL){SubRL->_parent = parent;}SubR->_parent = Grandpa;if (!Grandpa){_root = SubR;_root->_parent = nullptr;}else{if (parent == Grandpa->_left){Grandpa->_left = SubR;}else{Grandpa->_right = SubR;}}SubR->_left = parent;}

3.右单旋

		//右单旋void Rotetar(Node* parent){Node* SubL = parent->_left;Node* SubLR = SubL->_right;Node* Grandpa = parent->_parent;parent->_parent = SubL;parent->_left = SubLR;if (SubLR){SubLR->_parent = parent;}SubL->_parent = Grandpa;if (!Grandpa){_root = SubL;_root->_parent = nullptr;}else{if (parent == Grandpa->_left){Grandpa->_left = SubL;}else{Grandpa->_right = SubL;}}SubL->_right = parent;}

4.插入新结点的情况分析与总结

第一步、按照搜索二叉树的规则插入新结点

如果该树是空树，就让新结点作为它的根节点。
先找到要插入的位置，比当前结点小就向左子树寻找，比当前结点大就向右子树寻找。

第二步、分析插入结点后红黑树的性质是否被破坏

新结点默认为红色，
1.如果双亲节点的颜色是黑色，则没有违反红黑树性质，不需要调整；
2.如果双亲节点的颜色是红色，则违反性质4需要进行调整。
为了方便分析，我们约定当前结点为cur©，当前节点的父节点为parent§，当前节点的祖父结点为Grandpa(g),当前结点的叔叔结点为uncle（c）.。

  • 情况一：c为红色，p为红，g为黑，u存在且为红
    C++之红黑树
    只需要将p和u的颜色置为黑色，g的颜色置为红色。
    如果g是根节点，调整之后只需要将g改为黑色即可；
    如果g是子树，那么g一定有双亲结点，如果g的双亲结点为红色，就需要继续向上调整。
  • 情况二：cur为红，p为红，g为黑，u不存在/存在且为黑
    1. 如果u不存在，则说明cur是新增节点。因为如果cur不是新增节点，那么cur和p一定有一个是黑色，那么就不满足性质4（每条路径上的黑色结点的个数相同）；
    1. 如果u存在且为黑，则说明cur原本就存在且为黑。现在是红色是因为cur所在子树新增节点导致向上调整颜色的过程中将cur置为红色。
      这种情况有四种可能：
  • p是g的左孩子，c是p的左孩子；（要进行右单旋）
    以g为轴进行右单旋：
    C++之红黑树
    更新结点p为黑色，cur和g为红色。
  • p是g的右孩子，c是p的右孩子；（要进行左单旋）
    以g为轴进行左单旋：
    C++之红黑树
    更新结点p为黑色，cur和g为红色。
  • p是g的左孩子，c是p的右孩子；（要进行左右双旋）
    先以p为轴进行左单旋，再以g为轴进行右单旋：
    C++之红黑树
    更新结点cur为黑色，p和g为红色。
  • p是g的右孩子，c是p的左孩子。（要进行右左双旋）
    先以p为轴进行左单旋，再以g为轴进行右单旋：
    C++之红黑树
    更新结点cur为黑色，p和g为红色。

动态演示：

升序：
在这里插入图片描述
降序：
在这里插入图片描述
随机插入构建红黑树：
在这里插入图片描述

右旋转：
在这里插入图片描述
左旋转：
在这里插入图片描述

六、验证红黑树

验证红黑树分为两步：

1.检测是否满足二叉搜索树

中序遍历是否为有序序列

2.检测是否满足红黑树性质

代码如下：

		bool IsValidRBTree()//验证是否为红黑树{Node* pRoot = GetRoot();// 空树也是红黑树if (nullptr == pRoot)return true;// 检测根节点是否满足情况if (BLACK != pRoot->_col){cout << "违反红黑树性质二：根节点必须为黑色" << endl;return false;}// 获取任意一条路径中黑色节点的个数size_t blackCount = 0;Node* pCur = pRoot;while (pCur){if (BLACK == pCur->_col)blackCount++;pCur = pCur->_left;}// 检测是否满足红黑树的性质，k用来记录路径中黑色节点的个数size_t k = 0;return _IsValidRBTree(pRoot, k, blackCount);}bool _IsValidRBTree(Node* pRoot, size_t k, const size_t blackCount){//走到null之后，判断k和black是否相等if (nullptr == pRoot){if (k != blackCount){cout << "违反性质四：每条路径中黑色节点的个数必须相同" << endl;return false;}return true;}// 统计黑色节点的个数if (BLACK == pRoot->_col)k++;// 检测当前节点与其双亲是否都为红色Node* pParent = pRoot->_parent;if (pParent && RED == pParent->_col && RED == pRoot->_col){cout << "违反性质三：没有连在一起的红色节点" << endl;return false;}return _IsValidRBTree(pRoot->_left, k, blackCount) &&_IsValidRBTree(pRoot->_right, k, blackCount);}

七、红黑树与AVL树的比较

红黑树和AVL树都是高效的平衡二叉树，增删查改的时间复杂度都是O(log2Nlog_2 Nlog2​N),红黑树不追求绝对平衡，只要保证最长路径不超过最短路径的两倍。相对而言，插入和旋转的次数更少，在经常进行增删的结构中性能比AVL树更优，而且红黑树的实现比AVL树简单，因此更加常用。

总结

以上就是今天要讲的内容，本文介绍了C++中红黑树的相关概念。本文作者目前也是正在学习C++相关的知识，如果文章中的内容有错误或者不严谨的部分，欢迎大家在评论区指出，也欢迎大家在评论区提问、交流。
最后，如果本篇文章对你有所启发的话，希望可以多多支持作者，谢谢大家！

网络标签：

相关问题