网站建设公司如何,平面设计网站有哪些比较好,手机网页游戏排行榜前十名,做网站宁波有什么的网络公司#x1f984;个人主页:修修修也 #x1f38f;所属专栏:实战项目集 ⚙️操作环境:Visual Studio 2022 目录 一.了解项目功能 二.逐步实现项目功能模块及其逻辑详解 #x1f4cc;实现RBTreeNode类模板 #x1f38f;构造RBTreeNode类成员变量 #x1f38f;实现RBTreeNode类构… 个人主页:修修修也 所属专栏:实战项目集 ⚙️操作环境:Visual Studio 2022 目录 一.了解项目功能 二.逐步实现项目功能模块及其逻辑详解 实现RBTreeNode类模板 构造RBTreeNode类成员变量 实现RBTreeNode类构造函数 实现RBTree类模板 构造RBTree类成员变量 实现RBTree类构造函数 实现RBTree插入函数 实现RBTree插入左单旋(和AVL树一样) 实现RBTree插入右单旋(和AVL树一样) 判断红黑树是否符合红黑树规则函数 三.项目完整代码 test.c文件 RBTree.h文件 结语 一.了解项目功能 在本次项目中我们的目标是实现一个红黑树类模板,还不了解红黑树概念的朋友可以先移步[【数据结构】什么是红黑树(Red Black Tree)?]其结构图示如下: 红黑树结点(RBTreeNode)需要包含五个成员:键值对_kv, 左指针域_left, 右指针域_right, 父亲指针域_parent, 颜色标识_col.结点(RBTreeNode)逻辑结构图示如下: 红黑树类模板提供的功能有: 红黑树结点类的构造函数红黑树的构造函数红黑树的插入函数左单旋函数右单旋函数判断红黑树是否符合红黑树规则函数 二.逐步实现项目功能模块及其逻辑详解
通过第二部分对项目功能的介绍我们已经对 的功能有了大致的了解虽然看似需要实现的功能很多貌似一时间不知该如何下手但我们可以分步分模块来分析这个项目的流程最后再将各部分进行整合所以大家不用担心跟着我一步一步分析吧 注意该部分的代码只是为了详细介绍某一部分的项目实现逻辑故可能会删减一些与该部分不相关的代码以便大家理解需要查看或拷贝完整详细代码的朋友可以移步本文第四部分。 实现RBTreeNode类模板
构造RBTreeNode类成员变量 我们在一开始需求分析时就已经明确了红黑树结点(RBTreeNode)需要包含五个成员:键值对_kv, 左指针域_left, 右指针域_right, 父亲指针域_parent, 颜色标识_col.结点(RBTreeNode)逻辑结构图示如下: 对于颜色标识符,我们可以设置一个枚举来标识红色和黑色,增加代码的可读性: enum Colour
{RED,BLACK
}; 这里还有一个小的点需要提一下,我们在这里实现的RBTreeNode类,后续是要给RBTree类使用的,考虑到后续我们在红黑树的操作函数中会有直接操作结点成员变量的情况,如: cur-_left root-_right; //相当于在RBTreeNode外部直接通过类指针访问了类成员变量_left 基于class的封装特性,class的成员变量一般都是默认为私有的,如果我们要允许其他类直接访问class的成员变量和函数,就要将其都设置为public,或者通过友元/内部类来解决成员访问问题. 既然如此,我们不妨直接使用struct定义结点成员变量和函数,因为struct定义的类的成员变量和函数默认就是公有的,完全可以满足我们的需求. 综上所述,该部分代码如下: templateclass K,class V
struct RBTreeNode
{RBTreeNodeK, V* _left;RBTreeNodeK, V* _right;RBTreeNodeK, V* _parent;pairK, V _kv;Colour _col;
}; 实现RBTreeNode类构造函数 RBTreeNode的构造函数我们实现两个即可,一个是有参构造,一个是无参构造,而无参构造又可以通过给缺省值的方式和有参构造合二为一,所以我们用初始化列表来实现一下RBTreeNode的构造函数(我在红黑树的概念中已经分析过为什么新插入的结点一定是红色,这里就不多赘述了): //缺省值的作用是在无参调用时直接去调用模板实例化的类的无参构造函数
//这里一定不能将缺省值给0/nullptr!因为你不知道模板实例化的类具体到底是内置类型还是自定义类型(如Date)
//所以要显示调用pairK,V类型它自己的无参构造函数RBTreeNode(const pairK,V kvpairK,V()):_left(nullptr),_right(nullptr),_parent(nullptr),_kv(kv),_col(RED)
{} 实现RBTree类模板
构造RBTree类成员变量 RBTree类成员变量比较简单,就是一个根节点的指针,为了简化模板中出现的RBTreeNodeK,V类型的名字,我们将其简化命名为:Node 该部分实现代码如下: templateclass K,class V
class RBTree
{typedef RBTreeNodeK,V Node;private:Node* _root;
}; 实现RBTree类构造函数 RBTree类的构造函数非常简单,因为只有一个成员变量根节点指针_root,所以我们用初始化列表将该结点指针初始话为nullptr即可,代码如下: RBTree():_root(nullptr)
{} 实现RBTree插入函数 RBTree类的插入函数实现思路如下: 如果我们遇到了插入后违反红黑树规则的情况,那么红黑树的调整规则如下: 插入结点是根节点(即破坏了根节点是黑色的规则)---解决方法,直接将该节点变黑插入结点的父节点也是红色(即破坏了红结点的孩子必须是黑色的规则),分两种情况插入结点的叔叔结点是红色: 将叔叔和父亲变为黑色, 爷爷结点变为红色, 然后继续向上判定爷爷结点是否违反了红黑树的规则并进行调整插入结点的叔叔结点不存在或是黑色: 根据形态进行相应的旋转操作,旋转完成后,将旋转后的根节点变黑,将祖父结点变红即可 综上所述,红黑树的插入函数代码实现如下: bool Insert(const pairK, V kv)
{//前期的插入逻辑就是二叉搜索树的插入逻辑if (_root nullptr){_root new Node(kv);_root-_col BLACK;return true;}//找插入位置Node* cur _root;Node* parent nullptr;while (cur){if (cur-_kv.first kv.first){parent cur;cur cur-_right;}else if (cur-_kv.first kv.first){parent cur;cur cur-_left;}else{return false;}}//插入新结点cur new Node(kv);cur-_col RED;if (parent-_kv.first kv.first){//插右边parent-_right cur;}else{//插左边parent-_left cur;}cur-_parent parent;//控制红黑树的特性...控制颜色//插入的永远是红结点//插入的是根,把结点变红//插入时父节点是黑,就ok了//插入的父节点是红,看叔叔// 叔叔是红,把父亲叔叔都变黑,把爷爷变红(然后继续向上处理)// 叔叔是黑,旋转,转完父爷都变色while ( parent parent-_col RED parent-_parent){Node* grandfather parent-_parent;//因为我们在红黑树中不用平衡因子但是要判断是LL/RR/LR/RL型的旋转,因此需要在这里分情况讨论if (parent grandfather-_left){Node* uncle grandfather-_right;//叔叔存在且为红if (uncle uncle-_col RED){//变色parent-_col uncle-_col BLACK;grandfather-_col RED;//继续向上处理cur grandfather;parent cur-_parent;}else//叔叔不存在或存在且为黑,就旋转{if (cur parent-_left){RotateR(grandfather);//转完换色parent-_col BLACK;grandfather-_col RED;}else{RotateL(parent);RotateR(grandfather);//转完换色cur-_col BLACK;grandfather-_col RED;}}}else//parent grandfather-_right{Node* uncle grandfather-_left;if (uncle uncle-_col RED){//变色parent-_col uncle-_col BLACK;grandfather-_col RED;//继续向上处理cur grandfather;parent cur-_parent;}else{if (cur parent-_left){RotateR(parent);RotateL(grandfather);//改色cur-_col BLACK;grandfather-_col RED;}else{RotateL(grandfather);//祖父一定是红色,父子谁最后旋到根谁变黑//单旋父黑,双旋子黑//单旋爷变子,双旋子变父parent-_col BLACK;grandfather-_col RED;}}}}_root-_col BLACK;return true;
} 实现RBTree插入左单旋(和AVL树一样) 左单旋处理应用的情况为: 插入结点是父亲结点的右孩子父亲结点是爷爷结点的右孩子 左单旋的处理操作步骤为: 将父亲结点的左子树链接到爷爷结点的右孩子的位置将爷爷链接到父亲结点的左孩子位置 综上,实现代码及详解如下: //左单旋void RotateL(Node* parent){Node* cur parent-_right;Node* curleft cur-_left;Node* ppnode parent-_parent;//将失衡结点右孩子的左子树链接到失衡结点的右孩子parent-_right curleft;if (curleft){curleft-_parent parent;}//将失衡结点连接到失衡结点右孩子的左孩子位置parent-_parent cur;cur-_left parent;//处理父父结点的链接cur-_parent ppnode;if (ppnode nullptr)//为空代表parent就已经是root了{_root cur;}else{if (ppnode-_left parent)//失衡结点是其父节点的左孩子{ppnode-_left cur;}else //失衡结点是其父节点的右孩子{ppnode-_right cur;}}} 实现RBTree插入右单旋(和AVL树一样) 右单旋处理应用的情况为: 插入结点是父亲结点的左父亲结点是爷爷结点的左 右单旋的处理操作步骤为: 将父亲结点的右子树链接到爷爷结点的左孩子的位置将爷爷结点链接到父亲结点的右孩子位置 综上,实现代码及详解如下: //右单旋void RotateR(Node* parent){Node* cur parent-_left;Node* curright cur-_right;Node* ppnode parent-_parent;//将失衡结点左孩子的右子树连接到失衡结点的左孩子位置parent-_left curright;if (curright){curright-_parent parent;}//将失衡结点连接到失衡结点左孩子的右孩子位置parent-_parent cur;cur-_right parent;//链接父父结点cur-_parent ppnode;if (ppnode nullptr)//为空代表parent就已经是root了{_root cur;}else{if (ppnode-_left parent){ppnode-_left cur;}else{ppnode-_right cur;}}} 判断红黑树是否符合红黑树规则函数 判断一棵树是不是红黑树,就要从红黑树的几个规则出发,看其是否满足下面这几个规则: 每个结点不是红色就是黑色根结点是黑色如果一个结点是红色的,则它的子结点一定是黑色任一结点到NULL(树尾)的任何路径上,所含的黑色结点数一定相同每个NULL(树尾)空结点都是黑色的 综上,实现代码如下: //检查结点是否满足没有连续的两个红结点,以及所有路径的黑节点数量都相同函数
bool CheckColour(Node* root, int blacknum, int benchmark)
{if (root nullptr){if (benchmark ! blacknum)return false;return true;}//计算路径黑节点数量if (root-_col BLACK){blacknum;}//如果一个结点是红色,它的父亲也是红色,那就违反了没有两个连续红结点的规则if (root-_col RED root-_parent root-_parent-_col RED){cout root-_kv.first 连续红结点 endl;return false;}return CheckColour(root-_left,blacknum,benchmark) CheckColour(root-_right,blacknum,benchmark);
}//RBTree验证函数递归子函数
bool _IsBalance(Node* root)
{if (root nullptr)return true;//规则:根节点是黑色if (root-_col ! BLACK)return false;//求黑节点基准值(用左路的黑节点数量来计算)int benchmark 0;Node* cur _root;while (cur){if (cur-_col BLACK)benchmark;cur cur-_left;}//规则:不能有连续的红结点,且每条路径黑节点数量相同return CheckColour(root, 0, benchmark);
}//RBTree验证函数(嵌套的目的是为了方便传参)
bool IsBalance()
{return _IsBalance(_root);
}三.项目完整代码
我们将程序运行的代码分别在三个工程文件中编辑,完整代码如下:
test.c文件 该文件主要包含一些对AVL树的功能测试代码,大家可以酌情参考或自己编写测试用例: #includeRBTree.hvoid test1()
{int a[] { 16,3,7,11,9,26,18,14,15 };RBTreeint, int t;for (auto e : a){t.Insert(make_pair(e, e));cout Insert: e - t.IsBalance() endl;}
}void test2()
{int a[] { 14, 9, 5, 17, 11, 12, 7, 19, 16, 27 };RBTreeint, int t;for (auto e : a){t.Insert(make_pair(e, e));cout Insert: e - t.IsBalance() endl;}
}void test3()
{int a[] { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };RBTreeint, int t;for (auto e : a){t.Insert(make_pair(e, e));cout Insert: e - t.IsBalance() endl;}
}//随机数暴力测试
void test4()
{const int N 1000000;vectorint v;v.reserve(N);srand(time(0));for (size_t i 0; i N; i){v.push_back(rand());}cout 数据录入完毕,开始插入 endl;RBTreeint, int t;for (auto e : v){t.Insert(make_pair(e, e));}cout t.IsBalance() endl;t.InOrder();cout 插入结束 endl;
}int main()
{test4();return 0;
} RBTree.h文件
#pragma once#includeiostream
#includevector
using namespace std;enum Colour
{RED,BLACK
};templateclass K,class V
struct RBTreeNode
{RBTreeNode(const pairK,V kvpairK,V()):_left(nullptr),_right(nullptr),_parent(nullptr),_kv(kv),_col(RED){}RBTreeNodeK, V* _left;RBTreeNodeK, V* _right;RBTreeNodeK, V* _parent;pairK, V _kv;Colour _col;
};templateclass K,class V
class RBTree
{typedef RBTreeNodeK,V Node;
public:RBTree():_root(nullptr){}bool Insert(const pairK, V kv){if (_root nullptr){_root new Node(kv);_root-_col BLACK;return true;}Node* cur _root;Node* parent nullptr;while (cur)//查了半天是这里少写了个循环...(好在自己查到了,去比对了一下,果然...加上就好了{if (cur-_kv.first kv.first){parent cur;cur cur-_right;}else if (cur-_kv.first kv.first){parent cur;cur cur-_left;}else{return false;}}cur new Node(kv);cur-_col RED;if (parent-_kv.first kv.first){//插右边parent-_right cur;}else{//插左边parent-_left cur;}cur-_parent parent;//...控制颜色//插入的永远是红结点//插入的是根,把结点变红//插入时父节点是黑,就ok了//插入的父节点是红,看叔叔// 叔叔是红,把父亲叔叔都变黑,把爷爷变红(然后继续向上处理)// 叔叔是黑,旋转,转完父爷都变色while ( parent parent-_col RED parent-_parent){Node* grandfather parent-_parent;if (parent grandfather-_left){Node* uncle grandfather-_right;//叔叔存在且为红if (uncle uncle-_col RED){//变色parent-_col uncle-_col BLACK;grandfather-_col RED;//继续向上处理cur grandfather;parent cur-_parent;}else//叔叔不存在或存在且为黑,就旋转{if (cur parent-_left){RotateR(grandfather);//转完换色parent-_col BLACK;grandfather-_col RED;}else{RotateL(parent);RotateR(grandfather);//转完换色cur-_col BLACK;grandfather-_col RED;}}}else//parent grandfather-_right{Node* uncle grandfather-_left;if (uncle uncle-_col RED){//变色parent-_col uncle-_col BLACK;grandfather-_col RED;//继续向上处理cur grandfather;parent cur-_parent;}else{if (cur parent-_left){RotateR(parent);RotateL(grandfather);//改色cur-_col BLACK;grandfather-_col RED;}else{RotateL(grandfather);//祖父一定是红色,父子谁最后旋到根谁变黑//单旋父黑,双旋子黑//单旋爷变子,双旋子变父parent-_col BLACK;grandfather-_col RED;}}}}_root-_col BLACK;return true;}//左单旋void RotateL(Node* parent){Node* cur parent-_right;Node* curleft cur-_left;Node* ppnode parent-_parent;//将失衡结点右孩子的左子树链接到失衡结点的右孩子parent-_right curleft;if (curleft){curleft-_parent parent;}//将失衡结点连接到失衡结点右孩子的左孩子位置parent-_parent cur;cur-_left parent;//处理父父结点的链接cur-_parent ppnode;if (ppnode nullptr)//为空代表parent就已经是root了{_root cur;}else{if (ppnode-_left parent)//失衡结点是其父节点的左孩子{ppnode-_left cur;}else //失衡结点是其父节点的右孩子{ppnode-_right cur;}}}//右单旋void RotateR(Node* parent){Node* cur parent-_left;Node* curright cur-_right;Node* ppnode parent-_parent;//将失衡结点左孩子的右子树连接到失衡结点的左孩子位置parent-_left curright;if (curright){curright-_parent parent;}//将失衡结点连接到失衡结点左孩子的右孩子位置parent-_parent cur;cur-_right parent;//链接父父结点cur-_parent ppnode;if (ppnode nullptr)//为空代表parent就已经是root了{_root cur;}else{if (ppnode-_left parent){ppnode-_left cur;}else{ppnode-_right cur;}}}//中序遍历函数void InOrder(){_InOrder(_root); //代替成员函数完成递归cout endl; //方便后续观察测试用例}//中序遍历子递归函数void _InOrder(Node* root){if (root nullptr){return;}_InOrder(root-_left); //递归访问左子树cout root-_kv.first ; //访问根节点_InOrder(root-_right); //递归访问右子树}//验证双红结点和路径黑结点数是否相同函数bool CheckColour(Node* root, int blacknum, int benchmark){if (root nullptr){if (benchmark ! blacknum)return false;return true;}if (root-_col BLACK){blacknum;}if (root-_col RED root-_parent root-_parent-_col RED){cout root-_kv.first 连续红结点 endl;return false;}return CheckColour(root-_left,blacknum,benchmark) CheckColour(root-_right,blacknum,benchmark);}bool IsBalance(){return _IsBalance(_root);}//RBTree验证函数bool _IsBalance(Node* root){if (root nullptr)return true;//规则:根节点是黑色if (root-_col ! BLACK)return false;//求黑节点基准值int benchmark 0;Node* cur _root;while (cur){if (cur-_col BLACK)benchmark;cur cur-_left;}//规则:不能有连续的红结点,且每条路径黑节点数量相同return CheckColour(root, 0, benchmark);}private:Node* _root;
}; 结语
希望这篇红黑树的实现详解能对大家有所帮助,欢迎大佬们留言或私信与我交流.
学海漫浩浩,我亦苦作舟!关注我,大家一起学习,一起进步! 相关文章推荐 【C】模拟实现AVL树 【数据结构】什么是平衡二叉搜索树(AVL Tree)? 【C】STL标准模板库容器map 【C】STL标准模板库容器set 【C】模拟实现二叉搜索(排序)树 【数据结构】C语言实现链式二叉树(附完整运行代码) 【数据结构】什么是二叉搜索(排序)树? 【C】模拟实现priority_queue(优先级队列) 【C】模拟实现queue 【C】模拟实现stack 【C】模拟实现list 【C】模拟实现vector 【C】标准库类型vector 【C】模拟实现string类 【C】标准库类型string 【C】构建第一个C类:Date类 【C】类的六大默认成员函数及其特性(万字详解) 【C】什么是类与对象?
