【C++】模拟实现红黑树

一.了解项目功能

在本次项目中我们的目标是实现一个红黑树类模板,还不了解红黑树概念的朋友可以先移步[【数据结构】什么是红黑树(Red Black Tree)?]其结构图示如下:

红黑树结点(RBTreeNode)需要包含五个成员:键值对_kv, 左指针域_left, 右指针域_right, 父亲指针域_parent, 颜色标识_col.结点(RBTreeNode)逻辑结构图示如下:

红黑树类模板提供的功能有:

1. 红黑树结点类的构造函数
2. 红黑树的构造函数
3. 红黑树的插入函数
4. 左单旋函数
5. 右单旋函数
6. 判断红黑树是否符合红黑树规则函数

---

二.逐步实现项目功能模块及其逻辑详解

通过第二部分对项目功能的介绍，我们已经对 的功能有了大致的了解，虽然看似需要实现的功能很多，貌似一时间不知该如何下手，但我们可以分步分模块来分析这个项目的流程，最后再将各部分进行整合，所以大家不用担心，跟着我一步一步分析吧！

---

！！！注意，该部分的代码只是为了详细介绍某一部分的项目实现逻辑，故可能会删减一些与该部分不相关的代码以便大家理解，需要查看或拷贝完整详细代码的朋友可以移步本文第四部分。

---

发布者：admin，转转请注明出处：http://www.yc00.com/web/1755027640a5228496.html