二叉搜索树

红黑树（不红红，黑路同）（各个黑色节点的黑路同意味着黑高相同）（根节点必须是黑色）

1.如果一个节点是红色，那么他的儿子必然是黑色，父亲也必然是黑色

2.如果某个节点只有一个儿子，那么这个节点必然是黑色，且儿子必然是红色，且没有孙子

前提

旋转

用tie和tuple批量交换指针

左旋：

以节点 x 为支点向左旋转，让 x 的右子节点 y 成为新的父节点，x 成为 y 的左子节点，y 原来的左子树成为 x 的右子树。

右旋：

以节点 y 为支点向右旋转，让 y 的左子节点 x 成为新的父节点，y 成为 x 的右子节点，x 原来的右子树成为 y 的左子树

插入（用logn的代价在插入时使得树平衡）

1.根节点

2.父亲是黑色

插入红色即可

3.叔叔是红色（问题收敛）（父亲也是红色）

在之前的叶子节点插入一个红色节点

他的父亲，父亲的兄弟变为黑色（之前是红色）

爷爷变为红色

递归检查爷爷是不是根节点

是的话变为红色即可

不是的话依次递归修改爷爷的父亲等为其余其儿子不同的颜色

4.叔叔是黑色（父亲是红色）

插入红色的儿子

自身等于父亲

改自身为黑色

对自身和父亲进行旋转（之前的父亲和爷爷）

对自己和自己的上一级（原来的父亲还是自己的父亲）进行递归检查

5.如果自己是父亲的（左/右）节点，父亲同时也是爷爷的（左/右）节点，那么就把父亲和爷爷左旋

6.如果情况和5中所描述的相反，及自己和父亲，父亲和爷爷的左右关系不一致，处理方法

先对自己和父亲进行“左旋变色”自己和父亲交换位置，父亲变色

然后对新的自己和自己现在的父亲（以前的爷爷） 进行右旋

假设现在的p的父亲是红色，递归修改收敛就行了

删除

在删完还保持性质

1.删除

无儿子直接删

有一个儿子，让儿子替代自己的位置

有两个儿子，把要删除的节点和他的右子树中的最小值交换值后删除（不是交换位置，颜色不变）

因为又要判断是左儿子还是右儿子去进行一个赋值，所以经常使用三元运算符

进行边界处理判断要删除的节点是否为根节点

红黑树上的删除问题

1.两个儿子时转化为一个或没有儿子

2.一个儿子是直接删除当前 P 节点，并把儿子节点由红色变为黑色，red=0 指黑色，red=1 指红色（改变颜色的方法）

3.没有儿子的情况

如果是红的话直接删，不会影响黑高

如果是根节点的话直接删，红黑树清空

上面这两种是特殊情况，一般情况是（删除节点是黑色，有父节点），如下，再分三种情况

1.兄弟节点是黑色，兄弟的儿子是黑色：3

删去黑色节点后，左右黑高差了一。

做法：（父节点为红色）让父节点和兄弟节点交换颜色，平衡黑高

2.兄弟结点是黑色，兄弟的儿子有红色：2，区分左右旋转的话分四种，和你写的rotate函数有关，看看能否在rotate函数内部区分左旋右旋

不是很能看懂

3.兄弟节点是红色：

完整代码：

前置条件：

#include <tuple> // 用于std::tie和std::tuple

#include <utility> // 用于std::swap

using namespace std;

struct Node {

int val; // 节点存储的值（可根据需求改为其他类型，如模板T）

Node* left; // 左孩子指针

Node* right; // 右孩子指针

Node* fa; // 父节点指针（代码核心依赖）

int red; // 颜色标记：0=黑色，1=红色

// 构造函数：新节点默认红色（符合红黑树插入规则）

Node(int value) : val(value), left(nullptr), right(nullptr), fa(nullptr), red(1) {}

//根节点

Node* root = nullptr;

// 通用旋转函数：将child旋转到parent的位置，成为parent的父节点

void rotate(Node* child, Node* parent) {

Node* grandfa = parent->fa;

// 1. 处理祖父节点的指针

if (grandfa) {

if (grandfa->left == parent) grandfa->left = child;

else grandfa->right = child;

} else {

// 如果原父节点是根，更新全局根节点

root = child;

}

child->fa = grandfa;

// 2. 处理父子节点的指针（区分左旋/右旋）

if (parent->left == child) {

// 右旋：child是parent的左孩子

parent->left = child->right;

if (child->right) child->right->fa = parent;

child->right = parent;

} else {

// 左旋：child是parent的右孩子

parent->right = child->left;

if (child->left) child->left->fa = parent;

child->left = parent;

}

// 3. 更新原父节点的父指针

parent->fa = child;

}

};

封装

封装为和map，set等相似的容器

目的：实现

一个完整的MAP