红黑树的概念和性质
1. 概念
红黑树，是一种二叉搜索树，但在每个结点上增加一个存储位表示结点的颜色，可以是Red或Black。 通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路径会比其他路径长出俩倍，因而是接近平衡的
2. 性质
- 每个节点要么是红色，要么是黑色。
- 根节点是黑色的。
- 如果一个节点是红色的，那么它的两个子节点都是黑色的。
- 从任意节点到其每个叶子节点的每条路径都包含相同数量的黑色节点，这被称为“黑高相等性”。
- 每个叶子节点（NIL节点，通常表示为空节点）是黑色的。
红黑树的这些性质确保了树的平衡性，从而保证了树的高度在对数范围内，使得基本操作的时间复杂度保持在O(log n)级别
红黑树的结构
为了后续实现关联式容器简单，红黑树的实现中增加一个头结点，因为跟节点必须为黑色，为了与根节点进行区分，将头结点给成黑色，并且让头结点的 pParent 域指向红黑树的根节点，pLeft域指向红黑树中最小的节点，_pRight域指向红黑树中最大的节点。
当在红黑树的实现中增加一个头结点时，目的是为了简化操作和处理边界情况，而不必为特殊情况单独编写代码。这个头结点通常是一个黑色节点，位于红黑树的根节点之上，其pParent指向红黑树的根节点，pLeft指向红黑树中最小的节点，pRight指向红黑树中最大的节点。
以下是对头结点的作用和实现细节的解释：
- 简化边界条件处理：头结点的存在使得根节点始终是黑色的，因为根节点是头结点的右子节点。这样，在插入和删除等操作中，不需要特殊情况处理根节点的颜色和父节点是否存在的问题。
- 快速访问最小和最大节点：头结点的
pLeft指向红黑树中最小的节点，pRight指向最大的节点。这意味着你可以在O(1)时间内找到树中的最小和最大节点，而无需进行遍历。 - 统一根节点访问：无论是插入、删除还是其他操作，都可以始终从头结点开始进行操作，因为头结点的
pParent指向了真正的根节点。这简化了代码逻辑，因为你不必特殊处理根节点的情况。
下面是一个头结点的示例实现：
struct Node { int data; Color color; Node* left; Node* right; Node* parent; }; class RedBlackTree { private: Node* root; // 实际的根节点 Node* header; // 头结点 // ...其他成员函数和辅助函数... public: RedBlackTree() : root(nullptr), header(new Node) { header->color = BLACK; header->left = nullptr; header->right = nullptr; header->parent = nullptr; } // ...其他公共成员函数... };
在这个示例中，我们添加了一个名为header的成员变量，它是一个指向头结点的指针。头结点的初始化在构造函数中完成，并确保它始终是黑色的，根节点则位于头结点的pParent中。头结点的存在将简化红黑树的操作和边界情况处理。
这是一种实现方式,但在后面我们实现不是采用的这种方式,当然你也可以选择这种方式实现,更为简易,红黑树的实现过程只是为了让我们更熟悉它的底层,现实中需要我们实现的场景很少。
红黑树的节点定义及红黑树结构成员定义
这里我们的实现采用了三叉链的形式,后面我们会提到这种写法的好处
我们这里使用键值对的模板是为了方便后期模拟实现map和set
enum Colour { RED, BLACK }; template<class K, class V> struct RBTreeNode { RBTreeNode<K, V>* _left; RBTreeNode<K, V>* _right; RBTreeNode<K, V>* _parent; pair<K, V> _kv; Colour _col; RBTreeNode(const pair<K, V>& kv) :_left(nullptr) , _right(nullptr) , _parent(nullptr) , _kv(kv) {} }; template<class K, class V> struct RBTree { typedef RBTreeNode<K,V> Node; private: Node* _root = nullptr; };
- 枚举类型
Colour：这里定义了一个枚举类型，包括两个成员RED和BLACK。这个枚举类型用于表示红黑树中节点的颜色。在红黑树中，节点可以是红色或黑色，用这个枚举类型来表示节点颜色是一种常见的做法。 - 结构体
RBTreeNode<K, V>：这个结构体定义了红黑树的节点结构，其中包含以下成员变量：
_left和_right：分别指向节点的左子节点和右子节点的指针。_parent：指向节点的父节点的指针。_kv：用于存储键值对（Key-Value Pair）的成员变量。这个键值对通常用于存储节点的数据。_col：表示节点的颜色，可以是RED或BLACK。
- 构造函数
RBTreeNode(const pair<K, V>& kv)用于初始化节点对象，将各个成员变量赋初值，包括键值对_kv和颜色_col。 - 结构体
RBTree<K, V>：这个结构体定义了整个红黑树的结构，其中包含以下成员变量和一个别名：
_root：指向红黑树的根节点的指针。根节点是红黑树的起始点，所有操作都从根节点开始。
typedef RBTreeNode<K,V> Node;定义了一个别名Node，用于表示红黑树节点的类型。这样做可以简化代码，使得在代码中引用节点类型更加方便。
红黑树的插入
1. 按照二叉搜索的树规则插入新节点
bool Insert(const pair<K,V>& kv) { if (_root == nullptr)//为空直接插入 { _root = new Node(kv); _root->_col = BLACK; return true; } Node* parent = nullptr; Node* cur = _root; 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;//更新新插入节点的父指针 while (parent && parent->_col == RED) { Node* grandfater = parent->_parent; assert(grandfater); assert(grandfater->_col == BLACK); if (parent == grandfater->_left)//具体看下面讲解 { Node* uncle = grandfater->_right; // 情况一 : uncle存在且为红，变色+继续往上处理 if (uncle && uncle->_col == RED) { parent->_col = uncle->_col = BLACK; grandfater->_col = RED; // 继续往上处理 cur = grandfater; parent = cur->_parent; }// 情况二+三：uncle不存在 + 存在且为黑 else { // 情况二：右单旋+变色 if (cur == parent->_left) { RotateR(grandfater); parent->_col = BLACK; grandfater->_col = RED; } else { // 情况三：左右单旋+变色 RotateL(parent); RotateR(grandfater); cur->_col = BLACK; grandfater->_col = RED; } break; } } else // (parent == grandfater->_right) { Node* uncle = grandfater->_left; // 情况一 if (uncle && uncle->_col == RED) { parent->_col = uncle->_col = BLACK; grandfater->_col = RED; // 继续往上处理 cur = grandfater; parent = cur->_parent; } else { // 情况二：左单旋+变色 if (cur == parent->_right) { RotateL(grandfater); parent->_col = BLACK; grandfater->_col = RED; } else { // 情况三：右左单旋+变色 RotateR(parent); RotateL(grandfater); cur->_col = BLACK; grandfater->_col = RED; } break; } } } _root->_col = BLACK; return true; }
其实前面的代码和我们上一篇讲到的AVL树的插入类似,只不过这里的红黑树没有了平衡因子,而变为了颜色
接下来我们看每种情况的解析
2. 检测新节点插入后，红黑树的性质是否造到破坏
因为新节点的默认颜色是红色，因此：如果其双亲节点的颜色是黑色，没有违反红黑树任何性质，则不需要调整；但当新插入节点的双亲节点颜色为红色时，就违反了性质三不能有连在一起的红色节点，此时需要对红黑树分情况来讨论：
约定:cur为当前节点，p为父节点，g为祖父节点，u为叔叔节点
情况一: cur为红，p为红，g为黑，u存在且为红
cur和p均为红解决方式：将p,u改为黑，g改为红，然后把g当成cur，继续向上调整
情况二: cur为红，p为红，g为黑，u不存在/u存在且为黑
p为g的左孩子，cur为p的左孩子，则进行右单旋转；相反，p为g的右孩子，cur为p的右孩子，则进行左单旋转,p、g变色–p变黑，g变红
情况三: cur为红，p为红，g为黑，u不存在/u存在且为黑
p为g的左孩子，cur为p的右孩子，则针对p做左单旋转；相反，p为g的右孩子，cur为p的左孩子，则针对p做右单旋转，则转换成了情况2
3. 插入代码解析
- 如果
_root是空的，表示红黑树为空，那么将创建一个新的节点_root，并将其颜色设置为黑色。这是根节点，并且遵循红黑树规则的规定，根节点必须为黑色。 - 如果
_root不为空，那么代码会在树中查找正确的位置来插入新节点。通过遍历树的方式，找到正确的父节点parent，以及新节点要插入的位置cur。 - 如果要插入的键已经存在于树中，就返回
false，因为不允许键重复。 - 创建新节点
cur并将其颜色设置为红色。新节点的颜色一开始设置为红色，这是为了满足红黑树的性质。 - 然后，代码进入一个循环，循环的目的是确保插入新节点后仍然满足红黑树的性质。这是红黑树插入操作的关键部分。
- 在循环中，首先查看
parent节点的颜色，如果parent是红色，那么需要进一步处理来保持红黑树性质。 - 然后，代码会检查
uncle节点的颜色，即parent的兄弟节点。根据uncle的颜色，分为情况一、情况二和情况三。 - 最后，退出循环后将根节点的颜色设置为黑色，以确保根节点满足红黑树的性质。
4. 插入动态效果
1. 以升序插入构建红黑树
2. 以降序插入构建红黑树
3. 随机插入构建红黑树
