红黑树（Red-Black Tree）是一种经典的自平衡二叉查找树，它通过一系列精妙的规则来维持树的平衡，从而保证了各项操作在最坏情况下的时间复杂度为 O(logn)。它属于平衡树，但又不像AVL树那样追求“绝对平衡”，这种“适度”的平衡策略使它在增删操作频繁的场景中更具优势。

红黑树 vs. AVL树：如何选择？

在选择使用哪种平衡树时，通常根据具体的应用场景来权衡：

选择建议：

• 高频查询，低频增删：选择 AVL树。AVL树是高度平衡的，其查询效率略高于红黑树，因为树的高度更低。
• 高频增删：选择 红黑树。红黑树在插入和删除时，需要进行的旋转和颜色调整操作相对较少，平均性能更优。例如，Java中的 TreeMap 和 TreeSet，以及C++ STL中的 map 和 set 都是基于红黑树实现的。

红黑树的五个基本性质

为了维持平衡，红黑树严格遵守以下五个性质：

1. 颜色属性：每个节点要么是红色，要么是黑色。
2. 根节点：根节点必须是黑色的。
3. 叶子节点：所有叶子节点（NILL节点）都视为黑色的。
4. 红色节点约束：从根到叶子的任何路径上，都不能出现两个连续的红色节点。
5. 黑色高度：从任意一个节点到其所有后代叶子节点的路径上，所包含的黑色节点的数量必须相同。

【思考】节点的左右子树高度差最多不能超过多少？

答案是：最长路径（子树）的高度不超过最短路径（子树）的两倍。

推导：根据性质5，从一个节点出发到其所有叶子节点的路径上，黑色节点的数量是相等的（我们称之为 BH）。

• 最短路径：当路径上全是黑色节点时，路径最短，长度为 BH。
• 最长路径：根据性质4，红色节点不能连续，所以最长路径的情况是红黑相间的节点排列。在这种情况下，路径上最多可以有 BH 个红色节点和 BH 个黑色节点，总长度为 2 * BH。

因此，最长路径长度不会超过最短路径长度的两倍，这保证了红黑树不会退化成链表。

红黑树的插入操作

BST树的插入方式进行的

红黑树的插入操作：

1、空树：插入节点（黑色）

2、非空：插入节点 红色！！！ 此时要检查父节点的颜色，如果父节点是黑色，插入完成！！！否则出现连续的红色节点了，开始做红黑树的插入调整。

插入看叔叔的颜色

调整分为以下4种情况：

情况1：

叔叔是红色

把父亲和叔叔都涂成黑色，爷爷涂成红色。调整没有结束，当前指针继续指向爷爷，继续向上调整

情况2：

叔叔是黑色， 且插入的节点和父亲、爷爷在同一侧

让父亲是黑色，爷爷是红色。再以爷爷为轴进行右旋转

情况3：

叔叔是黑色， 且插入的节点和父亲、爷爷不在同一侧

以B为根节点进行左旋， 就变成情况2了

红黑树的删除操作

1、如果删除的是一个红色节点，就是一个BST树节点的删除，不用做任何删除调整操作

2、如果删除的是一个黑色节点，分两种情况

1）如果补上来的孩子是红色节点，直接把这个孩子涂成黑色，调整完成！！！

2）如果 补上来的孩子是黑色节点，那在当前这个路径上没办法再补一个黑色节点出来，只能从兄弟那里借调黑色节点（分成4种情况， 如下）

情况1：

删除的节点在左边，右边的兄弟是黑色，兄弟的右孩子是红色

交换 A, C 颜色，D变成黑色，以A左旋

情况2：

删除的节点在左边，右边的兄弟是黑色，兄弟的左孩子是红色（兄弟的右孩子是黑色）

交换C, D颜色，以C右旋。变成情况1

情况3：

删除的节点在左边，右边的兄弟是黑色，兄弟的左右孩子都是黑色

把兄弟节点涂红，调整还没有完，指向当前节点的父节点继续调整

继续落在四种情况之内

情况4：

兄弟本身就是红色

交换A, C颜色，以A左旋。于是又归结到上面的三种情况了

#include <iostream>
using namespace std;template<typename T>
class RBTree{
public:RBTree() : root_(nullptr){}//插入操作void insert(const T &val){if(root_ == nullptr){root_ = new Node(val);return;}Node* cur = root_;Node* parent = nullptr;while(cur != nullptr){parent = cur;if(val < cur->data_){cur = cur->left_;}else if(val > cur->data_){cur = cur->right_;}else{return;}}//设置当前节点的parent和颜色Node* node = new Node(val, parent, nullptr, nullptr, RED);if(parent->data_ > val){parent->left_ = node;}else{parent->right_ = node;}//如果新插入的红色节点，父节点也是红色，不满足红黑树的性质，进行插入调整if(RED == color(parent)){fixAfterInsert(node);}}//删除操作void remove(const T &val){if(root_ == nullptr){return;}Node* cur = root_;while(cur != nullptr){if(cur->data_ > val){cur = cur->left_;                           }else if(cur->data_ < val){cur  = cur->right_;}else{break;}}//没找到val节点，返回if(cur == nullptr){return;}//删除cur节点if(cur->left_ != nullptr && cur->right_ != nullptr){Node* pre = cur->left_;while(pre->right_ != nullptr){pre = pre->right_;}cur->data_ = pre->data_;cur = pre;   //cur指向前驱节点}//删除cur指向的节点  情况一和二Node* child = cur->left_;    //让child指向不为空的孩子if(child == nullptr){child = cur->right_;}if(child != nullptr){child->parent_ = cur->parent_;if(cur->parent_ == nullptr){root_ = child;}else{if(cur->parent_->left_ == cur){cur->parent_->left_ = child;}else{cur->parent_->right_ = child;}}Color c = color(cur);delete cur;if(c == BLACK){   //删除的是黑色节点，要进行删除调整操作fixAfterRemove(child);}}else{//child == nullptr;if(cur->parent_ == nullptr){delete cur;root_ = nullptr;return;}else{//删除的cue就是叶子节点了if(color(cur) == BLACK){fixAfterRemove(cur);}if(cur->parent_->left_ == cur){cur->parent_->left_ = nullptr;}else{cur->parent_->right_ = nullptr;}delete cur;}}}private://节点颜色enum Color{BLACK,RED};//节点类型struct Node{Node(T data = T(), Node* parent = nullptr, Node* left = nullptr, Node* right = nullptr, Color color = BLACK): data_(data), left_(left), right_(right), parent_(parent), color_(color){}T data_;Node* left_;Node* right_;Node* parent_;   //指向当前节点的父节点Color color_;    //节点颜色};//获取节点颜色Color color(Node* node){return node == nullptr ? BLACK : node->color_;}//设置节点颜色void setColor(Node* node, Color color){node->color_ = color;}//返回节点的左孩子Node* left(Node* node){return node->left_;}//返回节点的左孩子Node* right(Node* node){return node->right_;}//返回节点的父亲Node* parent(Node* node){return node->parent_;}//左旋转void leftRotate(Node* node){Node* child = node->right_;child->parent_ = node->parent_;if(node->parent_ == nullptr){root_ = child;}else{if(node->parent_->left_ == node){node->parent_->left_ = child;}else{node->parent_->right_ = child; }}node->right_ = child->left_;if(child->left_ != nullptr){child->left_->parent_ = node;}child->left_ = node;node->parent_ = child; }//右旋转void rightRotate(Node* node){Node* child = node->left_;child->parent_ = node->parent_;if(node->parent_ == nullptr){root_ = child;}else{if(node->parent_->left_ == node){node->parent_->left_ = child;}else{node->parent_->right_ = child;}}node->left_ = child->right_;if(child->right_ != nullptr){child->right_->parent_ = node;}child->right_ = node;node->parent_ = child;}//红黑树的插入调整操作void fixAfterInsert(Node* node){//如果红色节点的父节点也是红色，继续调整while(node != root_ && color(parent(node)) == RED){if(left(parent(parent(node))) == parent(node)){//插入的节点在左子树中Node *uncle = right(parent(parent(node)));if(RED == color(uncle)){   //情况1setColor(parent(node), BLACK);setColor(uncle, BLACK);setColor(parent(parent(node)), RED);node = parent(parent(node));}else{//先处理情况3if(right(parent(node)) == node){node = parent(node);leftRotate(node);}//统一处理情况2setColor(parent(node), BLACK);setColor(parent(parent(node)), RED);rightRotate(parent(parent(node)));break;    //调整完成}}else{//插入的节点在右子树当中Node* uncle = left(parent(parent(node)));if(RED == color(uncle)){setColor(parent(node), BLACK);setColor(uncle, BLACK);setColor(parent(parent(node)), RED);node = parent(parent(node));}else{//先处理情况3if(left(parent(node)) == node){node = parent(node);rightRotate(node);}//再统一处理情况2setColor(parent(node), BLACK);setColor(parent(parent(node)), RED);leftRotate(parent(parent(node)));break;    //调整完成}}}//此处强制root为黑色节点setColor(root_, BLACK);}//红黑树的删除调整操作void fixAfterRemove(Node* node){while(node != root_ && color(node) == BLACK){if(left(parent(node)) == node){//删除的黑色节点在左子树Node* brother = right(parent(node));if(color(brother) == RED){   //情况四setColor(parent(node), RED);setColor(brother, BLACK);leftRotate(parent(node));brother = right(parent(node));}if(color(brother->left_) == BLACK && color(brother->right_) == BLACK){    //情况三setColor(brother, RED);node = parent(node);}else{if(color(right(brother)) != RED){   //情况二setColor(brother, RED);setColor(left(brother), BLACK);rightRotate(brother);brother = right(parent(node));}//归结到情况一setColor(brother, color(parent(node)));setColor(parent(node), BLACK);setColor(right(brother), BLACK);leftRotate(parent(node));break;}}else{//删除的黑色节点在右子树Node* brother = left(parent(node));if(color(brother) == RED){   //情况四setColor(parent(node), RED);setColor(brother, BLACK);rightRotate(parent(node));brother = left(parent(node));}if(color(brother->left_) == BLACK && color(brother->right_) == BLACK){    //情况三setColor(brother, RED);node = parent(node);}else{if(color(left(brother)) != RED){   //情况二setColor(brother, RED);setColor(right(brother), BLACK);leftRotate(brother);brother = left(parent(node));}//归结到情况一setColor(brother, color(parent(node)));setColor(parent(node), BLACK);setColor(left(brother), BLACK);rightRotate(parent(node));break;}                }}//如果发现node指向的节点是红色，直接涂成黑色，调整结束setColor(node, BLACK);}Node* root_;   //只想红黑树的根节点
};int main(){RBTree<int> rb;for(int i = 1; i <= 10; i++){rb.insert(i);}rb.remove(9);return 0;
}