通过2-3-4树理解红黑树
在上一篇博文中，发现红黑树在批量删除最小值时性能非常的好
有点看不懂了，因此重新回顾了一下红黑树进行理解
上学时每次看算法导论的红黑树都是半懂，插入还行，删除部分的双重黑色实在太难理解了
其中的旋转变色部分也是觉得很奇怪，为什么要这么操作，能不能用别的操作方式
这一次尝试使用众多好评的2-3-4树来进行理解，加深印象
2-3-4树和红黑树是等价的
根据规则，任意一颗2-3-4树都可以转换为红黑树
推导，任意一颗红黑树都可以转换为2-3-4树：
- 黑节点就相当于2节点
- 一旦出现红节点
- 由于红色节点的子节点为黑色，所以不允许出现两个相同红色节点
- 那么红节点的父节点一定为黑色。因此红节点加上他的父节点，至少可以组成一个3节点
- 在这个基础上，如果红节点的兄弟节点也是红色的，红节点，父节点和兄弟节点可以组成一个4节点
因此2-3-4树和红黑树是等价的
并且，由于2-3-4树的节点最多只存在一个黑色节点，因此2-3-4树的高度 = 红黑树的高度
用2-3-4树来理解红黑树的操作
插入
寻找后插入叶子节点
从上往下搜索，直到达到叶子节点
被插入的叶子节点是2节点
变成3节点
graph TB
subgraph 如果叶子节点是2节点
subgraph 插入2前
a[1]
b[2]
end
subgraph 插入2后
c[1 and 2]
end
end对应红黑树：父节点为黑色
直接插入红色节点
graph TB
subgraph 父节点为黑色
subgraph 插入2前
a((1))---b((nil))
c((2))
end
style c fill:#f9f,stroke:#333,stroke-width:4px
subgraph 插入2后
d((1))---e((nil))
d((1))---f((2))
end
style f fill:#f9f,stroke:#333,stroke-width:4px
end被插入的叶子节点是3节点
变成4节点
graph TB
subgraph 如果叶子节点是3节点
subgraph 插入0前
a1[1 and 3]
b1[2]
end
subgraph 插入0后
a2[0 and 1 and 2]
end
subgraph 插入4前
a3[1 and 3]
b3[4]
end
subgraph 插入4后
a4[1 and 3 and 4]
end
subgraph 插入2前
a5[1 and 3]
b6[2]
end
subgraph 插入2后
a6[1 and 2 and 3]
end
end对应红黑树有3个插入位置，对应算法导论有三种情况（3为父节点，1为子节点的情况同理）
核心是让3节点变成4节点的时候，按序重排
这里的重排不只是3节点的两个节点和新插入的节点，（在4节点插入导致的向上递归后）还包含了两个节点原有的2个子树，一共五个节点要按顺序来排列好
五节点的位置是不确定的，因此算法不太好写，相对而言，算法导论中的左右旋转方法是一种比较好理解的巧妙算法
graph TB
subgraph 插入前
a1((1))---b1((位置1))
a1((1))---c1((3))
c1((3))---e1((位置2))
c1((3))---f1((位置3))
end
style c1 fill:#f9f,stroke:#333,stroke-width:4px对应红黑树：父节点为黑色
位置1，直接插入同上
对应红黑树（算法导论情况2）：父节点为红色，叔叔节点为黑色，和父节点还有祖父节点不为一条直线
位置2，对父节点（图中节点3）旋转，目的是为了使父节点和祖父节点为一条直线，从而转换到情况3
对应红黑树（算法导论情况3）：父节点为红色，叔叔节点为黑色，和父节点还有祖父节点为一条直线
位置3，对插入节点（图中节点2）进行旋转，目的是为了送一个节点给叔叔节点
graph TB
subgraph 父节点为红色,叔叔节点为黑色,和父节点还有祖父节点不为一条直线
subgraph 插入2前
a1((1))---b1((nil))
a1((1))---c1((3))
c1((3))---e1((2))
c1((3))---f1((nil))
end
style c1 fill:#f9f,stroke:#333,stroke-width:4px
style e1 fill:#f9f,stroke:#333,stroke-width:4px
subgraph 父节点右旋
a2((1))---b2((nil))
a2((1))---c2((2))
c2((2))---e2((nil))
c2((2))---f2((3))
end
style c2 fill:#f9f,stroke:#333,stroke-width:4px
style f2 fill:#f9f,stroke:#333,stroke-width:4px
endgraph TB
subgraph 父节点为红色,叔叔节点为黑色,和父节点还有祖父节点为一条直线
subgraph 插入4前
a1((1))---b1((nil))
a1((1))---c1((3))
c1((3))---e1((nil))
c1((3))---f1((4))
end
style c1 fill:#f9f,stroke:#333,stroke-width:4px
style f1 fill:#f9f,stroke:#333,stroke-width:4px
subgraph 父节点左旋,插入4后
a2((3))---b2((1))
a2((3))---c2((4))
end
style b2 fill:#f9f,stroke:#333,stroke-width:4px
style c2 fill:#f9f,stroke:#333,stroke-width:4px
end被插入的叶子节点是4节点
4节点的中值分裂上去，由于多了一个父节点，可以多一个子节点分叉，因此小值和大值各自成为一个子节点
上升后的节点当做新节点向上递归，直到不再插入4节点
graph TB
subgraph 如果叶子节点是4节点
subgraph 插入4前
a[0]---b[1 and 2 and 3]
c[4]
end
subgraph 插入4后
e[0 and 2]---f[1]
e[0 and 2]---g[3 and 4]
end
end对应红黑树有4个插入位置，对应算法导论同一个情况
graph TB
subgraph 插入4前
aa((0))---bb((nil))
aa((0))---a((2))
a((2))---b((1))
a((2))---c((3))
b((1))---d((位置1))
b((1))---e((位置2))
c((3))---f((位置3))
c((3))---g((位置4))
style b fill:#f9f,stroke:#333,stroke-width:4px
style c fill:#f9f,stroke:#333,stroke-width:4px
end对应红黑树（算法导论情况1）：父节点为红色，叔叔节点为红色
父节点和叔叔节点变黑色，祖父节点变红色，祖父节点当做新节点向上递归
如果祖父节点的父节点为黑色（说明成功插入了2-3-4树的一个2节点或者3节点的位置1）则递归结束，否则祖父节点当做新插入节点
除非遇到root节点，这就说明已经无法向上递归成为黑色节点的从节点了，只能自己成为一个2节点，从而使红黑树高度+1
graph TB
subgraph 父节点为红色,叔叔节点为红色
subgraph 插入4前
aa((0))---bb((nil))
aa((0))---a((2))
a((2))---b((1))
a((2))---c((3))
c((3))---e((nil))
c((3))---f((4))
end
style b fill:#f9f,stroke:#333,stroke-width:4px
style c fill:#f9f,stroke:#333,stroke-width:4px
subgraph 插入4后
gg((0))---hh((nil))
gg((0))---g((2))
g((2))---h((1))
g((2))---i((3))
i((3))---j((nil))
i((3))---k((4))
end
style g fill:#f9f,stroke:#333,stroke-width:4px
style f fill:#f9f,stroke:#333,stroke-width:4px
style k fill:#f9f,stroke:#333,stroke-width:4px
end删除
寻找删除节点的替代节点
从上往下搜索，直到达到需要删除的节点
如果在内部节点，找到后继节点，转换为删除后继叶子节点
从红黑树角度来看
当存在右子树的时候，红黑树和2-3-4树逻辑是一样的
但如果红黑树无右子树，又存在左子树，那么替代节点改为删除节点前继节点，也就是删除节点的左二子（由于红黑树的特殊性质，左子树一定为单独的红色节点）
被删除的替代节点是3或4节点
分别变成2或3节点
graph TB
subgraph 3或4节点
subgraph 删除2前
a[1 and 2]
end
subgraph 删除2后
b[1]
end
subgraph 删除3前
c[1 and 2 and 3]
end
subgraph 删除3后
d[1 and 2]
end
end对应红黑树有3个删除位置，对应算法导论同一种情况
对应红黑树：被删除节点为红色
直接删除
graph TB
subgraph 节点为红色
subgraph 删除2前
a((1))---b((nil))
a((1))---c((2))
end
style c fill:#f9f,stroke:#333,stroke-width:4px
subgraph 删除2后
d((1))
end
subgraph 删除3前
g((2))---h((1))
g((2))---i((3))
end
style h fill:#f9f,stroke:#333,stroke-width:4px
style i fill:#f9f,stroke:#333,stroke-width:4px
subgraph 删除3后
j((2))---k((1))
j((2))---l((nil))
end
style k fill:#f9f,stroke:#333,stroke-width:4px
end被删除的替代节点是2节点
对应红黑树：被删除节点为黑色
优先向相邻兄弟节点借，相邻兄弟节点是3或4节点，父节点不限
2-3-4树的父节点中，较近的节点替代当前节点，这时2-3-4树的父节点会产生一个空位
这个空位由2-3-4树的兄弟节点中，较近的节点来替代
graph TB
subgraph 相邻兄弟节点是3或4节点,父节点不限
subgraph 删除5前
a1[... and 4]---b1[...]
a1[... and 4]---c1[... and 2 and 3]
a1[... and 4]---d1[5]
end
subgraph 删除5后
a2[... and 3]---b2[...]
a2[... and 3]---c2[... and 2]
a2[... and 3]---d2[4]
end
end对应红黑树有3个删除位置，但是对应算法导论3种情况
graph TD
subgraph id[" "]
subgraph 父为3节点
a1((4))---b1((1))
a1((4))---c1((位置3))
b1((1))---d1((位置1))
b1((1))---e1((位置2))
style b1 fill:#f9f,stroke:#333,stroke-width:4px
end
subgraph 父为4节点
a2((1))---b2((0))
a2((1))---c2((4))
b2((0))---d2((位置1))
b2((0))---e2((位置2))
c2((4))---f2((位置2))
c2((4))---g2((位置1))
style b2 fill:#f9f,stroke:#333,stroke-width:4px
style c2 fill:#f9f,stroke:#333,stroke-width:4px
end
end对应红黑树（算法导论情况1）：兄弟节点为红色
和算法导论相印证，情况1兄弟节点为红色，对父节点右旋以后变色，变成情况1，情况3或者情况4
graph TD
subgraph 兄弟节点为红色
subgraph 父为3节点在删除5前
a1((4))---b1((1))
a1((4))---c1((5))
b1((1))---d1((...))
b1((1))---e1((2))
e1((2))---f1((...))
e1((2))---g1((...))
style b1 fill:#f9f,stroke:#333,stroke-width:4px
end
subgraph 父为3节点在右旋后
a2((1))---b2((...))
a2((1))---c2((4))
c2((4))---d2((2))
c2((4))---e2((5))
d2((2))---f2((...))
d2((2))---g2((...))
style a2 fill:#f9f,stroke:#333,stroke-width:4px
end
subgraph 父为3节点在变色后
a3((1))---b3((...))
a3((1))---c3((4))
c3((4))---d3((2))
c3((4))---e3((5))
d3((2))---f3((...))
d3((2))---g3((...))
style c3 fill:#f9f,stroke:#333,stroke-width:4px
end
end情况3和4根据2-3-4树来看，最终都是侄子节点和兄弟节点中较近的节点上移为父亲节点，原本的父亲节点替换当前节点
对应红黑树（算法导论情况3）：兄弟节点为黑色,较近侄子节点为红色
父节点可以为红色也可以为黑色
和算法导论相印证，情况3较近侄子节点为红色，对侄子节点左旋，并变色变成情况4
对应红黑树（算法导论情况4）：兄弟节点为黑色,较远侄子节点为红色
父节点可以为红色也可以为黑色
和算法导论相印证，较远的侄子节点为红色，此时再对兄弟节点右旋，变色，即达到平衡
graph TD
subgraph 兄弟节点为黑色,较近侄子节点为红色
subgraph 删除5前
a1((4))---b1((2))
b1((2))---c1((...))
b1((2))---d1((3))
a1((4))---e1((5))
style a1 fill:#fff,stroke:#333,stroke-width:4px
style d1 fill:#f9f,stroke:#333,stroke-width:4px
end
subgraph 对侄子节点左旋后
a2((4))---b2((3))
a2((4))---c2((5))
b2((3))---d2((2))
b2((3))---e2((nil))
d2((2))---f2((...))
d2((2))---g2((nil))
style a2 fill:#fff,stroke:#333,stroke-width:4px
style b2 fill:#f9f,stroke:#333,stroke-width:4px
end
subgraph 变色后
a3((4))---b3((3))
a3((4))---c3((5))
b3((3))---d3((2))
b3((3))---e3((nil))
d3((2))---f3((...))
d3((2))---g3((nil))
style a3 fill:#fff,stroke:#333,stroke-width:4px
style d3 fill:#f9f,stroke:#333,stroke-width:4px
end
endgraph TD
subgraph 兄弟节点为黑色,较远侄子节点为红色
subgraph 较近侄子为红转换后,或较远侄子节点为红
a3((4))---b3((3))
a3((4))---c3((5))
b3((3))---d3((2))
b3((3))---e3((nil))
d3((2))---f3((...))
d3((2))---g3((nil))
style a3 fill:#fff,stroke:#333,stroke-width:4px
style d3 fill:#f9f,stroke:#333,stroke-width:4px
end
subgraph 对兄弟节点右旋后
a4((3))---b4((2))
a4((3))---c4((4))
b4((2))---d4((...))
b4((2))---e4((nil))
c4((4))---f4((nil))
c4((4))---g4((5))
style c4 fill:#fff,stroke:#333,stroke-width:4px
style b4 fill:#f9f,stroke:#333,stroke-width:4px
end
subgraph 变色后
a5((3))---b5((2))
a5((3))---c5((4))
b5((2))---d5((...))
b5((2))---e5((nil))
c5((4))---f5((nil))
c5((4))---g5((5))
style a5 fill:#fff,stroke:#333,stroke-width:4px
end
subgraph 删除5后
a6((3))---b6((2))
b6((2))---c6((...))
b6((2))---d6((nil))
a6((3))---e6((4))
style a6 fill:#fff,stroke:#333,stroke-width:4px
end
end然后向父节点借：相邻兄弟节点是2节点且父亲节点是3或4节点
由于确定红黑树的兄弟节点没得借了，只能父节点下降为当前节点
下降以后，父节点会少一个分叉，因此只能把兄弟节点和父节点合并为同一个节点
graph TB
subgraph 相邻兄弟节点是2节点且父亲节点是3或4节点
subgraph 删除5前
a1[... and 2 and 4]---b1[...]
a1[... and 2 and 4]---c1[3]
a1[... and 2 and 4]---d1[5]
end
subgraph 删除5后
a2[... and 2]---b2[...]
a2[... and 2]---c2[3 and 4]
end
end对应红黑树有3个删除位置，对应算法导论有两种情况
graph TD
subgraph id[" "]
subgraph 父为3节点
a1((4))---b1((2))
a1((4))---c1((位置3))
b1((2))---d1((位置1))
b1((2))---e1((位置2))
style b1 fill:#f9f,stroke:#333,stroke-width:4px
end
subgraph 父为4节点
a2((4))---b2((2))
a2((4))---c2((5))
b2((2))---d2((位置1))
b2((2))---e2((位置2))
c2((5))---f2((位置2))
c2((5))---g2((位置1))
style b2 fill:#f9f,stroke:#333,stroke-width:4px
style c2 fill:#f9f,stroke:#333,stroke-width:4px
end
end父为3节点对应红黑树（算法导论情况1）：兄弟节点为红色
和算法导论相印证，情况1通过右旋后变色转换为情况2
父为4节点对应红黑树（算法导论情况2）：兄弟节点为黑色，侄子节点为黑色
和算法导论相印证，情况2将兄弟节点变成红色后，将父节点作为新的替代节点向上追溯，由于父节点是红色，因此红变黑且追溯结束
graph TD
subgraph 兄弟节点为红色
subgraph 父为3节点在删除5前
a1((4))---b1((2))
a1((4))---c1((5))
b1((2))---d1((...))
b1((2))---e1((3))
style b1 fill:#f9f,stroke:#333,stroke-width:4px
end
subgraph 父为3节点在右旋后
a2((2))---b2((...))
a2((2))---c2((4))
c2((4))---d2((3))
c2((4))---e2((5))
style a2 fill:#f9f,stroke:#333,stroke-width:4px
end
subgraph 父为3节点在变色后,或父为4节点
a3((2))---b3((...))
a3((2))---c3((4))
c3((4))---d3((3))
c3((4))---e3((5))
style c3 fill:#f9f,stroke:#333,stroke-width:4px
end
subgraph 父为3或4节点在删除5后
a4((2))---b4((...))
a4((2))---c4((4))
c4((4))---d4((3))
c4((4))---e4((nil))
style d4 fill:#f9f,stroke:#333,stroke-width:4px
end
end最后都没得借：相邻兄弟节点和父亲节点都是2节点
兄弟节点和父亲节点合并成一个3节点
向上递归修复，合并后的节点当做是一个新的处理节点，查看他的兄弟节点和父亲节点
graph TB
subgraph 相邻兄弟节点和父亲节点都是2节点
subgraph 删除1前
a1[...]---b1[2]
b1[2]---c1[1]
b1[2]---d1[3]
end
subgraph 删除3后
a2[...]---b2[1 and 2]
end
end对应红黑树有1个删除位置，对应算法导论只有一种情况
graph TD
a1((2))---b1((1))
a1((2))---c1((位置1))对应红黑树（算法导论情况2）：兄弟节点为黑色，侄子节点为黑色
最终状态：将兄弟节点变成红色，并向上追溯
和算法导论相印证，情况2将兄弟节点变成红色后，将父节点作为新的替代节点向上追溯，同样的，当追溯后新的节点为红色，红变黑且追溯结束
否则直到追溯到root节点（必然是黑色的，没得借，因此整个树高度-1）
graph TD
subgraph 兄弟节点为黑色,侄子节点为黑色
subgraph 删除3前
a1((...))---b1((2))
b1((2))---c1((1))
b1((2))---d1((3))
end
subgraph 删除3后
a2((...))---b2((2))
b2((2))---c2((1))
b2((2))---d2((nil))
style c2 fill:#f9f,stroke:#333,stroke-width:4px
end
end小结
找替代节点
有右子树找后继，没有右子树找前继（就是左儿子），左右子树都不存在就不需要替代节点了
兄弟节点为红色的旋转
然后，根据删除的各步骤操作，可以把兄弟节点为红色的部分单独提取出来
在红黑树中不管是向相邻兄弟节点借，还是向父节点借，在兄弟节点为红色的时候，都需要进行旋转
兄弟节点为红色，意味着该节点的父节点是一个3节点
而2-3-4树的3节点是对应着两种红黑树的，左倾或者右倾
graph TD
subgraph id[" "]
subgraph 父为3节点,左倾红黑树
a1((4))---b1((2))
a1((4))---c1((...))
b1((2))---d1((...))
b1((2))---e1((...))
style b1 fill:#f9f,stroke:#333,stroke-width:4px
end
subgraph 父为3节点,右倾红黑树
a2((2))---b2((...))
a2((2))---c2((4))
c2((4))---d2((...))
c2((4))---e2((...))
style c2 fill:#f9f,stroke:#333,stroke-width:4px
end
end此时对其旋转，对2-3-4树来说不代表任何操作，只是为了操作红黑树时更好的借相邻兄弟节点
借2-3-4树的相邻节点，红黑树查看红色侄子节点
旋转后才是正式的2-3-4树开始借相邻节点，而不影响2-3-4树的高度
从红黑树视角看：
旋转以后就可以统一为兄弟节点为黑色的情况，然后就可以查看是否存在红色侄子节点可以借过来替代删除，而不影响红黑树的高度
借2-3-4树的父节点，红黑树向上追溯红色节点去借
如果2-3-4树的相邻节点不存在（红黑树的侄子红色节点不存在），就向2-3-4树的父节点强行借一个下来
如果被借的2-3-4树父节点是一个2节点，那么2-3-4树的高度会减少，他自然会向2-3-4树的祖父节点递归向上去借，直到root节点没得借了，2-3-4树整个高度-1
从红黑树的视角看：
也就是向上追溯去借红色节点
理解Nil节点
由于树是从下往上递归生长的，因此只有叶子节点的判定的时候，会出现节点不存在的情况
递归向上以后会变成内部节点，此时需要进行两种区分，例如在插入4节点时
叶子节点的判定是parent->parent->left && parent->parent->right
递归向上后叶子节点的判定是parent->parent->left && parent->parent->left->isRed && parent->parent->right && parent->parent->right->isRd
利用Nil节点，可以统一判定parent->parent->left->isRed && parent->parent->right->isRed
理解左旋右旋
如下图，染色节点是受影响节点，绿色节点（5）是旋转轴节点，一共有4个受影响节点
由于旧的父节点（3）即将占用旧的子节点（4）位置，而旧的父节点（3）原有的子树（5）即将挪走，变成旧的父节点（3）的父节点
因此一拍即合，旧的父节点（3）的子树设为旧的子节点（4）
顺便祖父节点（1）也需要更新他的子树
当然还有一些边界条件，旧的子节点（4）不存在，或者祖父节点不存在（1）
graph TD
subgraph id[ ]
subgraph 左旋2前
a1((1))---b1((..))
a1((1))---c1((3))
c1((3))---d1((2))
c1((3))---e1((5))
e1((5))---f1((4))
e1((5))---g1((6))
style a1 fill:#9ff,stroke:#333,stroke-width:4px
style c1 fill:#9ff,stroke:#333,stroke-width:4px
style e1 fill:#9f9,stroke:#333,stroke-width:4px
style f1 fill:#9ff,stroke:#333,stroke-width:4px
end
subgraph 左旋2后
a2((1))---b2((..))
a2((1))---d2((5))
d2((5))---e2((3))
d2((5))---f2((6))
e2((3))---g2((2))
e2((3))---h2((4))
style a2 fill:#9ff,stroke:#333,stroke-width:4px
style d2 fill:#9f9,stroke:#333,stroke-width:4px
style e2 fill:#9ff,stroke:#333,stroke-width:4px
style h2 fill:#9ff,stroke:#333,stroke-width:4px
end
end对一个节点，向哪一个方向旋转，简单来说就是将这个方向的父节点变成自己的对应子树（左旋将父节点变成左子树，右旋将父节点变成右子树）
根本目的是为了将一个节点迁移到另外一颗子树上，从而达到插入时迁移走多余红色节点；或者替代删除时借一个红色节点过来变黑
理解变色
上面提到，旋转的主要目的是插入送走一个节点或是删除是借一个节点
旋转以后需要变色才能平衡黑色
深入理解一下变色的各个Case
左倾/右倾红黑树转换
2-3-4树的3节点通过一次旋转后变色完成左倾或者右倾，有如下Case
- 插入3节点（插入算法导论情况3）
- 删除先左倾/右倾变化（删除算法导论情况1）
- 删除向相邻兄弟节点借（删除算法导论情况3）
插入时将4节点分裂成两个2节点，并且中间节点往上插入（插入算法导论情况1）
4节点分裂的两个2节点，在红黑树中由原先4节点的红色变成黑色，中间节点往上插入，因此要黑变红，成为某个黑节点的从节点才能变成2-3-4树的3或4节点
直到root节点（必然没有父节点，只能自己成为一个2节点，因此出现唯一的整个树高度+1的场景）
删除时兄弟节点为黑色，侄子节点为黑色（删除算法导论情况2）
2-3-4树的父节点和相邻兄弟节点合并成3节点，因此把红黑树的兄弟节点变红，父节点变黑
如果红黑树的父节点原本是红色，说明2-3-4树的父节点原本至少是个3节点，因此能借到节点，向上追溯停止。
如果红黑树的父节点原本是黑色，那么2-3-4树的父节点是个2节点，需要继续向上追溯借节点，直到root节点（必然是黑色的，没得借，因此出现唯一的整个树高度-1的场景）
删除时兄弟节点为黑色，较远侄子节点为红色（删除算法导论情况4）
通过旋转借来一个红色节点以后，就可以让当前子树多一个黑色节点来删除
为了这个目的而红变黑
理解删除最小节点性能
如上一篇博客所述，红黑树在批量删除最小节点时，性能非常好，几乎达到了\(O(n)\)的时间消耗
而众所周知红黑树的删除单个值性能是\(O(\log n)\)
那么为什么会有这个差异呢
根据本文的理解，删除分查找值，查找删除值的替代后继节点和删除替代后继节点三个步骤
查找值：
删除时第一次找到最小节点确实是\(O(log n)\)
后续的删除最小节点的查找，只需要取上一个删除项的后继节点是\(O(1)\)的复杂度
删除n个的查找是\(O(n)\)
查找删除值的替代后继节点：
由于每次删除都是最小值，因此不需要替代后继节点
删除替代后继节点：
实际上就是删除当前的最小值
从2-3-4树来进行理解
3-4节点的删除不需要任何操作
2节点的删除比较坏的情况下旋转3次（情况1转情况3转情况4）
最坏情况下向上回溯，每一次回溯都需要删除了指数级别的节点数，次数很少
3-4-节点和2节点的删除可以平均为\(O(n)\)的时间复杂度，回溯的消耗忽略不计，因此这一步可以达到几乎\(O(n)\)的复杂度
总结3个步骤，是\(O(n)\)的复杂度
总结
核心是理解2-3-4树的各个节点在对应这个图的位置的插入删除操作
graph TB
subgraph id[ ]
subgraph 2节点
a1((1))---b1((位置1))
a1((1))---c1((位置2))
end
subgraph 3节点
a2((1))---b2((位置3))
a2((1))---c2((3))
c2((3))---e2((位置4))
c2((3))---f2((位置5))
style c2 fill:#f9f,stroke:#333,stroke-width:4px
end
subgraph 4节点
c3((2))---d3((1))
c3((2))---e3((3))
d3((1))---f3((位置6))
d3((1))---g3((位置7))
e3((3))---h3((位置8))
e3((3))---i3((位置9))
style d3 fill:#f9f,stroke:#333,stroke-width:4px
style e3 fill:#f9f,stroke:#333,stroke-width:4px
end
end通过本篇总结的理解后，我也手撸了一个红黑树，性能看着比标准库还高一些（O0下快60%，O2下快20%）。。。
1 | Tree insert: Cost 514 ms |
参考资料
红黑树的传统理解
-
这一篇从数学公式上证明了红黑树为什么是平衡的
-
非常枯燥的不好理解的资料，只是作为权威资料列在这里
-
一个红黑树在线插入删除动画生成的好网站，对理解红黑树有所帮助，强力推荐
-
传统理解方式中，可以对照算法导论一起看的较好博文
相比算法导论有些图表一步到位，这篇博文有一些中间转换状态，更利于理解
但是传统理解方式看完也不知道为什么要这么旋转变色
AVL树，红黑树，B树，B+树，Trie树都分别应用在哪些现实场景中？
介绍对比了各种树，对红黑树的介绍是：
红黑树利用了缓存
Robert Sedgewick, 红黑树的发明人，在《算法（第4版）》 中说过， 红黑树等价于2-3树
其中2-节点 等价于普通平衡二叉树的节点，3-节点 本质上是非平衡性的缓存。
当需要再平衡（rebalance）时，增删操作时，2-节点 与 3-节点间 的 转化会吸收不平衡性，减少旋转次数，使再平衡尽快结束。
在综合条件下，增删操作相当时，数据的随机性强时，3-节点的非平衡性缓冲效果越明显。因此红黑树的综合性能更优。
继续追根溯源，红黑树的性能优势，本质上是用空间换时间。
这个理解非常深入了
-
用于实现红黑树的迭代器自增遍历
-
解释了为什么遍历map是\(O(n)\)的
2-3-4树的理解
2-3-4树的实现
简单一个2-3-4树的实现在网上就五花八门，而且大部分都不太正确
-
这里四篇都是左倾红黑树的实现，并且在查找时对路径上的全部节点进行了分裂
我认为这样就失去了红黑树的缓存性，多了很多无效操作，使性能降低
-
这一篇是少有的图画的比较细的博文，给了我一定启发
但是其中关于删除的情况分解是错误的，而且图画的也不够全
-
对2-3-4树的算法写的非常细非常全，而且完全正确
通过这一篇文章，我大致理解了2-3-4树的插入删除逻辑
-
这一篇文章打开了我通过2-3-4树理解红黑树的大门，让我有一点隐隐约约抓住了红黑树的核心理念
但是他的图，画的情况不够全，理解的也不够彻底
所以有了这一篇博文，我自己从头到尾推导了一遍