前言
在二叉搜索树（BST）和 AVL 树之后，红黑树 终于登场！它是计算机科学中最经典、应用最广的数据结构，没有之一。
C++ STL： set / map / unordered_map 底层都是红黑树
Java： TreeMap / TreeSet 底层都是红黑树
Linux 内核： 进程调度、内存管理大量使用红黑树
为什么要用红黑树？
AVL 树太严格：高度差必须≤1，插入删除要大量旋转，效率低
红黑树：弱平衡、旋转少（最多 3 次）、性能极高
一、什么是红黑树？（一句话定义）
红黑树 = 自带颜色规则、弱平衡、自平衡二叉搜索树
通过节点颜色（红 / 黑） + 旋转 + 变色 ，保证从根到叶子的最长路径不超过最短路径的 2 倍 ，实现高效稳定的 O(logn) 操作。
二、红黑树 5 大核心性质（必须背！）
这是红黑树的灵魂，所有操作都围绕这 5 条规则：
每个节点只能是 红色 或 黑色
根节点永远是黑色
所有叶子节点（空节点）都是黑色
红色节点的两个孩子一定是黑色（不能出现连续红红）
从任意节点到其所有叶子路径上，黑色节点数量相同
核心口诀：根黑、叶黑、不红红、黑同长。
三、红黑树结构体设计
cpp
复制代码
typedef int ELEMTYPE;
// 颜色枚举
typedef enum { RED, BLACK } TYPE_COLOR;
// 红黑树节点
typedef struct RBNode
{
ELEMTYPE val; // 值
struct RBNode* leftchild; // 左孩子
struct RBNode* parent; // 父节点（核心！）
struct RBNode* rightchild; // 右孩子
TYPE_COLOR color; // 颜色
}RBNode;
// 红黑树管理结构
typedef struct
{
RBNode* root; // 树根
}RBTree;
新节点默认红色（插入红色破坏性质少，只需要处理 "红红冲突"）
头文件
cpp
复制代码
#pragma once
typedef int ELEMTYPE;
typedef enum { RED, BLACK }TYPE_COLOR;
//红黑树的有效节点定义
typedef struct RBNode
{
ELEMTYPE val;
struct RBNode* leftchild;
struct RBNode* parent;
struct RBNode* rightchild;
//bool color;//颜色//默认 true=红 black=黑
TYPE_COLOR color;
}RBNode;
//红黑树的辅助节点定义
typedef struct
{
RBNode* root;
}RBTree;
//工具函数
//1.购买新节点
RBNode* BuyNode();
//2.单左旋 返回值：旋转调整之后的新的根节点 Node：插入的节点
//注意:AVL树单旋，是直接让失衡节点旋转，也就是传进的Node自身旋转
// 但是红黑树单选，是直接让Node的爷爷自身旋转，
RBNode* Left_Rotate(RBNode* Node);
//3.单右旋 返回值：旋转调整之后的新的根节点 Node：插入的节点
//注意:AVL树单旋，是直接让失衡节点旋转，也就是传进的Node自身旋转
// 但是红黑树单选，是直接让Node的爷爷自身旋转，
RBNode* Right_Rotate(RBNode* Node);
//4.插入函数的通用平衡旋转函数 //难 Node：当前插入的节点，要进行平衡判断
void Insert_Adjust_Rotate(RBTree* pTree, RBNode* Node);
//5.删除函数的通用平衡旋转函数 //难难难
//void Delete_Adjust_Rotate(RBTree* pTree, RBNode* Node);//初版 //缺陷：1.双黑上移，遇到黑色节点，此时需要告诉这个函数，第二个参数Node是否需要被删除
//缺陷：2.双亲指针parent的修正
void Delete_Adjust_Rotate(RBTree* pTree, RBNode* Node, bool tag);
//普通函数
//1.初始化
void Init_RBTree(RBTree* pTree);
//2.插入
bool Insert_RBTree(RBTree* pTree, ELEMTYPE val);
//3.删除
bool Delete_RBTree(RBTree* pTree, ELEMTYPE val);
//4.查询
RBNode* Search_RBTree(RBTree* pTree, ELEMTYPE val);
//5.打印(用中序遍历打印)
void Show_inOrder(RBNode* root);//递归
void Show_inOrder2(RBTree* pTree);//非递归
四、红黑树核心工具函数（基石）
1. 购买新节点
cpp
复制代码
//1.购买新节点
RBNode* BuyNode()
{
RBNode* pnewnode = (RBNode*)malloc(sizeof(RBNode));
if (pnewnode == NULL)
exit(EXIT_FAILURE);
//memset(pnewnode, 0, sizeof(RBNode)); string.h memory.h
pnewnode->leftchild = pnewnode->parent = pnewnode->rightchild = NULL;
pnewnode->color = RED;//默认是红色
return pnewnode;
}
2. 左旋（RR 型）
注意：红黑树旋转是旋转祖父节点！
cpp
复制代码
//2.单左旋 返回值：旋转调整之后的新的根节点 Node：插入的节点
//注意:AVL树单旋，是直接让失衡节点旋转，也就是传进的Node自身旋转
// 但是红黑树单选，是直接让Node的爷爷自身旋转，
RBNode* Left_Rotate(RBNode* Node)
{
//1.申请两个指针用来指向它爸和它爷
RBNode* father = Node->parent;
RBNode* grandfather = Node->parent->parent;
//2.让它爷左旋到它爸的左边，这里提前先把冲突节点给处理掉(有可能冲突的节点：它爸的右孩子)
//口诀：冲突的左孩变右孩
grandfather->rightchild = father->leftchild;
if (grandfather->rightchild != NULL)
{
grandfather->rightchild->parent = grandfather;
}
//3.此时，它爷左旋到它爸的左边没有障碍物，则直接挪动指针即可
father->leftchild = grandfather;
grandfather->parent = father;
//4.返回新的根节点(它爸)
return father;
}
3. 右旋（LL 型）
cpp
复制代码
//3.单右旋 返回值：旋转调整之后的新的根节点 Node：插入的节点
//注意:AVL树单旋，是直接让失衡节点旋转，也就是传进的Node自身旋转
// 但是红黑树单选，是直接让Node的爷爷自身旋转，
RBNode* Right_Rotate(RBNode* Node)
{
//1.申请两个指针用来指向它爸和它爷
RBNode* father = Node->parent;
RBNode* grandfather = Node->parent->parent;
//2.让它爷右旋到它爸的右边，这里提前先把冲突节点给处理掉(有可能冲突的节点：它爸的右孩子)
//口诀：冲突的右孩变左孩
grandfather->leftchild = father->rightchild;
if (grandfather->leftchild != NULL)
{
grandfather->leftchild->parent = grandfather;
}
//3.此时，它爷右旋到它爸的右边没有障碍物，则直接挪动指针即可
father->rightchild = grandfather;
grandfather->parent = father;
//4.返回新的根节点(它爸)
return father;
}
五、红黑树插入（最难！）
插入规则：
按 BST 插入，新节点红色
若父节点是黑色 → 直接结束
若父节点是红色 → 违反性质 4（红红）→ 看叔叔脸色调整
调整分 2 大场景：
场景 1：叔叔是红色
变色即可，无需旋转
父、叔变黑
祖父变红
递归向上调整祖父
场景 2：叔叔是黑色
旋转 + 变色 分 4 种形态：LL、RR、LR、RL
cpp
复制代码
//4.插入函数的通用平衡旋转函数 //难 Node：当前插入的节点，要进行平衡判断
//终版(parent指针要管了)
void Insert_Adjust_Rotate(RBTree* pTree, RBNode* Node)
{
//1.若判读的插入节点Node是根节点 --> 直接变黑结束
if (Node->parent == NULL)
{
Node->color = BLACK;
Node->parent = NULL;
return;
}
//2.若判读的插入节点Node没有失衡(它爸是黑色) --> 无需调整，直接结束
if (Node->parent->color == BLACK)
{
return;
}
//3.执行到这里，代表着Node不是根节点，且Node节点违反了"不红红"性质，需要看其叔叔脸色行事
//此时，Node它自己和Node它爸以及Node它爷三个节点肯定都存在
//4.申领三个指针，用来它爸，它爷，它叔
RBNode* father = Node->parent;
RBNode* grandfather = Node->parent->parent;
RBNode* uncle = grandfather->leftchild == father ? grandfather->rightchild : grandfather->leftchild;//uncle有可能赋值为NULL
//5.若它叔是红色
if (uncle != NULL && uncle->color == RED)
{
//叔父爷变色
uncle->color = BLACK;
father->color = BLACK;
grandfather->color = RED;
//把它爷当成新的插入节点，重新进行逻辑判断
Insert_Adjust_Rotate(pTree, grandfather);
return;
}
else//它叔是黑色 --> 旋转+变色
{
//6.判断Node自己和它爸以及它爷，这三个节点符合哪一个型号
if (grandfather->leftchild == father)//L
{
if (father->leftchild == Node)//LL
{
//先变色
father->color = BLACK;
grandfather->color = RED;
//再旋转
RBNode* great_grandfather = grandfather->parent;//太爷节点 有可能存在，有可能不存在
RBNode* ptr = Right_Rotate(Node);
if (great_grandfather == NULL)
{
pTree->root = ptr;
ptr->parent = NULL;
}
else//太爷存在
{
if (ptr->val < great_grandfather->val)
great_grandfather->leftchild = ptr;
else
great_grandfather->rightchild = ptr;
ptr->parent = great_grandfather;
}
return;
}
else//LR
{
//先左旋
father->rightchild = Node->leftchild;
if (father->rightchild != NULL)
{
father->rightchild->parent = father;
}
Node->leftchild = father;
father->parent = Node;
grandfather->leftchild = Node;
Node->parent = grandfather;
//变色+再右旋
grandfather->color = RED;
Node->color = BLACK;
RBNode* great_grandfather = grandfather->parent;
RBNode* ptr = Right_Rotate(father);
if (great_grandfather == NULL)
{
pTree->root = ptr;
ptr->parent = NULL;
}
else
{
if (ptr->val < great_grandfather->val)
great_grandfather->leftchild = ptr;
else
great_grandfather->rightchild = ptr;
ptr->parent = great_grandfather;
}
return;
}
}
if (grandfather->rightchild == father)//R
{
if (father->rightchild == Node)//RR
{
//先变色
father->color = BLACK;
grandfather->color = RED;
RBNode* great_grandfather = grandfather->parent;
RBNode* ptr = Left_Rotate(Node);
if (great_grandfather == NULL)
{
pTree->root = ptr;
ptr->parent = NULL;
}
else//太爷存在
{
if (ptr->val < great_grandfather->val)
great_grandfather->leftchild = ptr;
else
great_grandfather->rightchild = ptr;
ptr->parent = great_grandfather;
}
//再旋转
return;
}
else//RL
{
//先右旋
father->leftchild = Node->rightchild;
if (father->leftchild != NULL)
{
father->leftchild->parent = father;
}
Node->rightchild = father;
father->parent = Node;
grandfather->rightchild = Node;
Node->parent = grandfather;
//变色+再左旋
grandfather->color = RED;
Node->color = BLACK;
RBNode* great_grandfather = grandfather->parent;
RBNode* ptr = Left_Rotate(father);
if (great_grandfather == NULL)
{
pTree->root = ptr;
ptr->parent = NULL;
}
else//太爷存在
{
if (ptr->val < great_grandfather->val)
great_grandfather->leftchild = ptr;
else
great_grandfather->rightchild = ptr;
ptr->parent = great_grandfather;
}
return;
}
}
}
}
完美处理所有 4 种失衡
严格维护 parent 指针
自动更新根节点
六、红黑树删除（数据结构天花板）
红黑树删除 = BST 删除 + 双黑调整
删除流程：
BST 删除（叶子 / 单分支 / 双分支→后继替换）
若删除红色节点 → 直接结束
若删除黑色节点 → 产生 "双黑" → 触发调整
调整分 4 种情况：
兄弟红色 → 变色 + 旋转，新兄弟必黑
兄弟黑色 + 兄弟孩子全黑 → 兄弟变红，双黑上移
兄弟黑色 + 远侄子红 → 旋转 + 变色
兄弟黑色 + 近侄子红 → 旋转 + 变色
cpp
复制代码
//tag如果为真，则代表第二个参数Node是需要准备被删除的
//tag如果为假，则代表第二个参数Node是不需要被删除的，只是作为判断的媒介
void Delete_Adjust_Rotate(RBTree* pTree, RBNode* Node, bool tag)//终版 //没有缺陷
{
//0.assert 安全性处理
assert(pTree != NULL);
assert(Node != NULL);
//1.申请三个指针，分别指向待删除节点的父，兄，子
RBNode* father = Node->parent;
RBNode* sibling = NULL;//sibling的赋值 依赖于父节点的存在，而此时father有可能==NULL
RBNode* child = Node->leftchild != NULL ? Node->leftchild : Node->rightchild;
//2.此时，我们知道Node要么是没有孩子，要么有一个孩子
//3.如果只有一个孩子(只有左孩子/右孩子)情况：--> 孩子顶替上来后变黑
if (tag && child != NULL)//--------------
{
//判断此时Node是不是根节点，如果是的话，一会要修改辅助节点里的root
if (Node->parent == NULL)
pTree->root = child;
else
if (child->val < father->val)
father->leftchild = child;
else
father->rightchild = child;
child->parent = father;
free(Node);
child->color = BLACK;
return;
}
//4.如果零个孩子 --> 要分情况处理
else
{
//4.1 如果此时Node指向的节点是根节点 -->直接删除
if (tag && Node->parent == NULL)//------------
{
pTree->root = NULL;
free(Node);
return;
}
else
{
//4.2 如果此时Node指向的节点非根节点，且颜色是红色 -->直接删除
if (tag && Node->color == RED)//------------
{
//因为释放Node，要把其father指向Node的指针断开(手放开)
if (Node == father->leftchild)//左手抓Node
{
father->leftchild = NULL;
}
else//右手抓Node
{
father->rightchild = NULL;
}
free(Node);
return;
}
//4.3 如果此时Node指向的节点非根节点，且颜色是黑色,此时立马去判断兄弟的颜色
else
{
sibling = Node == father->leftchild ? father->rightchild : father->leftchild;
RBNode* grandfather = father->parent;//爷爷指针提前定义好，下边只要旋转都会用到
// 如果是红色 --> 父兄变色，然后父节点朝着待删除节点一侧进行单旋，
// 此时待删除节点就会出现一个新的兄弟节点
if (sibling->color == RED)
{
//父兄变色
father->color = RED;
sibling->color = BLACK;
//father节点要朝着Node节点一侧进行单旋
RBNode* ptr = Node == father->leftchild ? Left_Rotate(sibling->rightchild) : Right_Rotate(sibling->leftchild);
//ptr用来接收旋转之后的返回节点
//判断爷爷节点是否存在，如果不存在，则用辅助节点来接收旋转之后的返回节点
if (grandfather == NULL)//旋转点就是根节点，此时旋转完成之后，由pTree->root来抓住旋转后返回的新根节点
pTree->root = ptr;
//判断爷爷节点是否存在，如果存在，则用爷爷来接收旋转之后的返回节点
else
if (ptr->val < grandfather->val)
grandfather->leftchild = ptr;
else
grandfather->rightchild = ptr;
ptr->parent = grandfather;
Delete_Adjust_Rotate(pTree, Node, true);//这里的第二个参数Node是必须删除的，因为待删除的Node还没有被处理的
return;
}
//兄弟是黑色
else
{
//能走到这里，则代表可以先把Node删除释放掉，因为后续不需要Node了
if (tag)
{
if (father->leftchild == Node)
father->leftchild = NULL;
else
father->rightchild = NULL;
free(Node);
Node = NULL;
}
//在此时申请一个指针redchild指向兄弟的红孩(如果有两个红孩的话，默认让其指向同侧)
RBNode* redchild = NULL;
if (sibling->leftchild != NULL && sibling->leftchild->color == RED)
redchild = sibling->leftchild;
else if (sibling->rightchild != NULL && sibling->rightchild->color == RED)
redchild = sibling->rightchild;
else
redchild = NULL;
//此时判断兄弟有没有红孩
//4.4 如果此时Node指向的节点非根节点，且颜色是黑色，且兄弟是黑色，且兄弟至少有一个红孩 --> 变色+旋转(注意：旋转要根据兄弟及其父子的情况去判断型号)
if (redchild != NULL)//至少有一个红孩-> 变色+旋转
{
//此时根据 兄弟，及其兄弟的红孩，及其兄弟它爸 三者去判断型号
if (father->leftchild == sibling)//L
{
if (sibling->leftchild != NULL && sibling->leftchild->color == RED)//LL
{
//旋转+变色
//变色规则：LL/RR型号：r变s，s变p，p变黑
// LR/RL型号：r变p，p变黑
redchild->color = sibling->color;
sibling->color = father->color;
father->color = BLACK;
//旋转规则不变，但是时刻注意旋转传进的参数，是旋转节点的孙子辈
//LL型需要单右旋
RBNode* ptr = Right_Rotate(redchild);
if (grandfather != NULL)//它爷爷指针不为NULL，则用爷爷节点来抓住ptr
if (ptr->val > grandfather->val)
grandfather->rightchild = ptr;
else
grandfather->leftchild = ptr;
else//它爷爷指针为NULL，则用辅助节点来接收ptr
pTree->root = ptr;
ptr->parent = grandfather;
return;
}
else//LR
{
//旋转+变色
//变色规则：LL/RR型号：r变s，s变p，p变黑
// LR/RL型号：r变p，p变黑
redchild->color = father->color;
father->color = BLACK;
//LR型号，怎么旋转先左旋，再右旋
//第一步：先左旋(手动用代码实现，不能直接调用Left_Rotate)
sibling->rightchild = redchild->leftchild;//用sibling的右手来接收red_child的有可能存在的左孩
if (sibling->rightchild != NULL)//Sibling的右手真的接收到了一个孩子节点
{
sibling->rightchild->parent = sibling;
}
redchild->leftchild = sibling;
sibling->parent = redchild;
father->leftchild = redchild;
redchild->parent = father;
//第二步：再右旋
RBNode* ptr = Right_Rotate(sibling);
if (grandfather != NULL)//它爷爷指针不为NULL，则用爷爷节点来抓住ptr
if (ptr->val > grandfather->val)
grandfather->rightchild = ptr;
else
grandfather->leftchild = ptr;
else//它爷爷指针为NULL，则用辅助节点来接收ptr
pTree->root = ptr;
ptr->parent = grandfather;
return;
}
}
else//R
{
if (sibling->rightchild != NULL && sibling->rightchild->color == RED)//RR
{
//注意：如果这种情况sibling有两个红孩，redchild此时指向的是左边的红孩,给redchild修正一下，让其指向右侧的红孩
redchild = sibling->rightchild;
//旋转+变色
//变色规则：LL/RR型号：r变s，s变p，p变黑
// LR/RL型号：r变p，p变黑
redchild->color = sibling->color;
sibling->color = father->color;
father->color = BLACK;
//旋转规则不变，但是时刻注意旋转传进的参数，是旋转节点的孙子辈
//RR型需要单左旋
RBNode* ptr = Left_Rotate(redchild);
if (grandfather != NULL)//它爷爷指针不为NULL，则用爷爷节点来抓住ptr
if (ptr->val > grandfather->val)
grandfather->rightchild = ptr;
else
grandfather->leftchild = ptr;
else//它爷爷指针为NULL，则用辅助节点来接收ptr
pTree->root = ptr;
ptr->parent = grandfather;
return;
}
else//RL
{
//旋转+变色
//变色规则：LL/RR型号：r变s，s变p，p变黑
// LR/RL型号：r变p，p变黑
redchild->color = father->color;
father->color = BLACK;
//RL型号，怎么旋转先右旋，再左旋
//第一步：先右旋(手动用代码实现，不能直接调用Right_Rotate)
sibling->leftchild = redchild->rightchild;//用sibling的左手来接收red_child的有可能存在的右孩
if (sibling->leftchild != NULL)//Sibling的右手真的接收到了一个孩子节点
{
sibling->leftchild->parent = sibling;
}
redchild->rightchild = sibling;
sibling->parent = redchild;
father->rightchild = redchild;
redchild->parent = father;
//第二步：再左旋
RBNode* ptr = Left_Rotate(sibling);
if (grandfather != NULL)//它爷爷指针不为NULL，则用爷爷节点来抓住ptr
if (ptr->val > grandfather->val)
grandfather->rightchild = ptr;
else
grandfather->leftchild = ptr;
else//它爷爷指针为NULL，则用辅助节点来接收ptr
pTree->root = ptr;
ptr->parent = grandfather;
return;
}
}
return;
}
//4.5 如果此时Node指向的节点非根节点，且颜色是黑色，且兄弟是黑色，且兄弟都是黑孩 --> 兄弟变红，双黑上移
else
{
sibling->color = RED;
//双黑上移，遇见的是红色节点或根节点 -> 直接变黑，结束
if (father->color == RED || father->parent == NULL)
{
father->color = BLACK;
return;
}
//双黑上移，遇见的是黑色节点，此时可以确定的是它一定有兄弟
//此时根据其兄弟的情况，继续判断即可
Delete_Adjust_Rotate(pTree, father, false);//这里的第二个参数father是不能删除的，因为删除的Node已将被被处理掉了
return;
}
}
}
}
}
}
带 tag 参数区分是否真删除节点
完整处理所有边界
全程维护 parent 指针
递归向上调整双黑
七、初始化+插入+删除+查找+打印（递归+非递归）
cpp
复制代码
//1.初始化
void Init_RBTree(RBTree* pTree)
{
//0.asssert
pTree->root = NULL;
}
//2.插入
bool Insert_RBTree(RBTree* pTree, ELEMTYPE val)
{
//0.assert
//0.5 购买新节点
RBNode* pnewnode = BuyNode();
pnewnode->val = val;
//1.申请两个变量p和pp，用来在红黑树里向下遍历，用来找到val值节点的插入位置
RBNode* p = pTree->root;
RBNode* pp = NULL;
if (p == NULL)//它是空树
{
pTree->root = pnewnode;
pnewnode->color = BLACK;
return true;
}
//2.进入循环，循环条件是p指向节点存在，且其值不是我所需要的
while (p != NULL && p->val != val)
{
//3.根据和p的有效值的比较，让指针p走自己的左侧或者右侧去遍历
pp = p;
p = val < p->val ? p->leftchild : p->rightchild;
}
//4.当while循环结束的时候，可能性1：p指向的节点值不存在,则准备插入pnewnode
//可能性2：p指向的节点，存在，不用插入pnewnode
if (p != NULL)
{
free(pnewnode);
return true;
}
else//可能性1：p指向的节点值不存在,则准备插入pnewnode
{
if (val < pp->val)
{
pp->leftchild = pnewnode;
}
else
{
pp->rightchild = pnewnode;
}
pnewnode->parent = pp;
}
if (pp->color == RED)//则违反"不红红"
{
Insert_Adjust_Rotate(pTree, pnewnode);
}
//5.结束
return true;
}
//3.删除 //洗菜切菜
bool Delete_RBTree(RBTree* pTree, ELEMTYPE val)
{
//0.assert 判断辅助节点存在与否
//1.判空 判断红黑树是否存在有效节点
if (pTree->root == NULL)
return true;
//2.找到待删除节点
RBNode* p = Search_RBTree(pTree, val);
if (p == NULL)
return true;
//3.判断此时待删除节点节点，什么情况
//删除节点，会存在3种情况：两个孩子/一个孩子/零个孩子
//4.待删除节点有两个孩子 --> 直接前驱/直接后继代替后，
// 替代后的节点就变成一个孩子情况或者零个孩子情况
if (p->leftchild != NULL && p->rightchild != NULL)
{
RBNode* cat = p->rightchild;
while (cat->leftchild != NULL)
cat = cat->leftchild;
p->val = cat->val;
p = cat;
}
//代码指向到这里，此时的p一定指向的是单分支/零分支情况
//5.直接调用删除调整函数即可
Delete_Adjust_Rotate(pTree, p, true);
return true;
}
//4.查询
RBNode* Search_RBTree(RBTree* pTree, ELEMTYPE val)
{
RBNode* p = pTree->root;
while (p != NULL && p->val != val)
p = val < p->val ? p->leftchild : p->rightchild;
return p;
}
//5.打印(用中序遍历打印)
void Show_inOrder(RBNode* root)//递归
{
if (root == NULL)
return;
Show_inOrder(root->leftchild);
printf("%d ", root->val);
Show_inOrder(root->rightchild);
}
#include
void Show_inOrder2(RBTree* pTree)//非递归
{
assert(pTree != NULL);
if (pTree->root == NULL) return;
std::stack
RBNode* p = pTree->root;
while (p != NULL || !st.empty())
{
// 一路左走入栈
while (p != NULL)
{
st.push(p);
p = p->leftchild;
}
// 出栈访问
p = st.top();
st.pop();
printf("%d ", p->val);
// 右子树
p = p->rightchild;
}
}
int main()
{
RBTree head;
Init_RBTree(&head);
Insert_RBTree(&head, 17);
Insert_RBTree(&head, 18);
Insert_RBTree(&head, 23);
Insert_RBTree(&head, 34);
Insert_RBTree(&head, 27);
Insert_RBTree(&head, 15);
Insert_RBTree(&head, 9);
Insert_RBTree(&head, 6);
Insert_RBTree(&head, 8);
Insert_RBTree(&head, 5);
Insert_RBTree(&head, 25);
Show_inOrder(head.root);
printf("\n");
Delete_RBTree(&head, 18);
Delete_RBTree(&head, 9);
Delete_RBTree(&head, 34);
//Delete_RBTree(&head, 25);
//Delete_RBTree(&head, 15);
//Delete_RBTree(&head, 6);
//Delete_RBTree(&head, 27);
//Delete_RBTree(&head, 17);
//Delete_RBTree(&head, 5);
//Delete_RBTree(&head, 23);
//Delete_RBTree(&head, 8);
Show_inOrder(head.root);
printf("\n");
Show_inOrder2(&head);
return 0;
}
运行结果：
八、红黑树高频15 问（背会直接拿分）
**红黑树是什么？**弱平衡二叉搜索树，用颜色维持平衡。
**红黑树 5 大性质？**根黑、叶黑、不红红、黑同长。
**新节点为什么是红色？**减少黑色节点变化，降低调整成本。
插入最坏旋转几次？ 最多 2 次。
删除最坏旋转几次？ 最多 3 次。
**AVL 和 红黑树 区别？**AVL 严格平衡查询快；红黑弱平衡插入删除快。
**什么是双黑？**删除黑色节点产生的虚拟黑色。
红黑树时间复杂度？ 严格 O(logn)。
**哪里用红黑树？**C++ STL map/set、Java TreeMap、Linux 内核。
**红红冲突怎么解决？**看叔叔，红变色，黑旋转。
**左旋和右旋区别？**处理 RR 型和 LL 型失衡。
**删除红色节点需要调整吗？**不需要。
**删除黑色节点需要调整吗？**需要，处理双黑。
**红黑树是完全二叉树吗？**不是，是弱平衡二叉树。
红黑树高度？ 最多 2log(n+1)。
九、总结（最核心口诀）
**红黑树五定律：**根黑、叶黑、不红红、黑路等长。
**插入：**新点红，父黑停，父红看叔情。叔红变色，叔黑旋形。
**删除：**删红无事，删黑双惊。兄红旋，兄黑看侄，双黑上行。
旋转少、效率高、STL 底层离不了！