算法

1. 二叉树

二叉树图，为便于查看，省略部分nil节点。

1.1 概念

二叉树作为常用的数据结构，目的是优化查找、添加、删除的效率。

1.1.1 二叉树

每个节点最多只有Left和Right2个分支的树。

graph TB
5((5)) --- 6((6))
5 --- 4((4))
4 --- 2((2))
4 --- 3((3))
6 --- nil((nil))
6 --- 7((7))
classDef node fill:#fff,stroke:#333;

1.1.2 二叉查找树

满足二叉树条件
任意节点的左子树上的所有节点的值小于这个任意节点的值
任意节点的右子树上的所有节点的值大于这个任意节点的值
任意节点的左右子树，也都是二叉查找树

graph TB
7((7)) --- 5((5))
5 --- 4((4))
5 --- 6((6))
7 --- 9((9))
9 --- 8((8))
9 --- 12((12))
12 --- nil1((nil))
12 --- 11((11))
11 --- 10((10))
11 --- nil2((nil))
classDef node fill:#fff,stroke:#333;

1.1.3 平衡二叉树（AVL）

满足二叉查找树
任意节点的左右树高度绝对值⇐1
任意节点的左右树都是平衡二叉树

假设，上面二叉查找树，是按照值的顺序添加的，结构会变成：

graph TB
12((12)) --- nil1((nil))
12 --- 11((11))
11 --- nil2((nil))
11 --- 10((10))
10 --- nil3((nil))
10 --- 9((9))
9 --- 8((8))
9 --- nil4((nil))
8 --- 7((7))
8 --- nil5((nil))
classDef node fill:#fff,stroke:#333;

此时依然满足二叉查找树的条件，但是查找的时间复杂度变成了O(n)，和链表一样的了。但是如果变成平衡二叉树：

graph TB
9((9)) --- 8((8))
9 --- 11((11))
11 --- 10((10))
11 --- 12((12))
8 --- 7((7))
8 --- nil2((nil))
classDef node fill:#fff,stroke:#333;

此时查找的时间复杂度变成了O(logN)，树的高度越高，提升的效率越高。

1.2 红黑树

平衡二叉树的查找性能很强，但是要求太严格了，左右树高度差不能超过1，导致只要插入/删除了就会打破平衡，就需要通过左旋/右旋来调整，所以对于插入/删除操作很多的时候，需要频繁旋转，性能就下降了。为了解决这个问题，又引申出了红黑树，红黑树并不是严格意义上的平衡二叉树，红黑树在查找性能上要弱于平衡二叉树，但是插入和删除方面性能更强。

特点：

满足二叉查找树
根节点是黑色的
空节点（叶子节点，nil节点）是黑色的
不能出现连续的2个红色节点
任意节点到达其所有叶子节点的路径中包含的黑色节点数相同（任意节点到达其所有叶子节点的路都是唯一的【实际上不只是到达叶子节点的路径是唯一，而是到达任意子节点的路也是唯一的】，因为父节点唯一。也就是这些路径上的黑色节点数量都是一样的，只要影响了任意一条路径上的黑色节点数量，则不满足规则5，需要进行平衡，最终目的就是所有路径黑色节点数量一致）。

4和5可以确保从任意一个节点出发到其叶子节点的所有路径中，最长路径不会超过最短路径的2倍。对比平衡二叉树的高度差不能超过1，显然红黑树的查找性能要低一些。

graph TB
linkStyle default fill:none,stroke:#333,stroke-width:2px;
classDef red fill:red,color:#fff,stroke:none;
classDef black fill:#333,color:#fff,stroke:none;
classDef nil fill:#333,color:#fff,stroke:none;
a((a)) --- b((b))
a --- c((c))
b --- d((d))
b --- e((e))
c --- f((f))
d --- h((h))
d --- nil1((nil))
e --- nil2((nil))
e --- nil3((nil))
f --- nil4((nil))
f --- nil5((nil))
c --- nil6((nil))
h --- nil8((nil))
h --- nil9((nil))
class a,c,d,e black
class b,f,g,h red
class nil1,nil2,nil3,nil4,nil5,nil6,nil7,nil8,nil9 nil

从a出发，到达任意叶子节点，都只经过2个黑色节点，且没有连续红色节点，这是一个颗红黑树。

1.2.1 查找

红黑树的查找和二叉查找树相同。

前序遍历（根 — 左 — 右）
中序遍历（左 — 根 — 右）

中序遍历，实际就是按小到大的顺序遍历。很多时候很有用。
后序遍历（左 — 右 — 根）
顺序遍历

1.2.2 旋转

红黑树的调整主要依赖于旋转和变色。

旋转分为左旋和右旋。

左旋针对右树，是以对任意节点和该节点的右子节点进行旋转。

左旋过程：旋转节点的右子节点替换它的位置，旋转节点变成右子节点的左子节点，右子节点的左子节点变成旋转节点的右子节点。

**速记：**左旋变左，失去右，多的左变成右。

graph TB
linkStyle default fill:none,stroke:#333,stroke-width:2px;
classDef red fill:red,color:#fff,stroke:none;
classDef black fill:#333,color:#fff,stroke:none;
classDef nil fill:#333,color:#fff,stroke:none;

subgraph a左旋后
bl((b)) --- al((a))
bl --- nil1l((nil))
al --- cl((c))
al --- el((e))
cl --- dl((d))
cl --- nil3l((nil))
end

subgraph a左旋前
a((a)) --- b((b))
a --- c((c))
c --- d((d))
c --- nil1((nil))
b --- e((e))
b --- nil2((nil))
end

class a,al,c,cl,dl,e,el black
class b,bl,d red
class nil1,nil2,nil3,nil4,nil1l,nil2l,nil3l nil

右旋针对左树，是对任意节点和该节点的左子节点进行旋转。

graph TB
linkStyle default fill:none,stroke:#333,stroke-width:2px;
classDef red fill:red,color:#fff,stroke:none;
classDef black fill:#333,color:#fff,stroke:none;
classDef nil fill:#333,color:#fff,stroke:none;

subgraph a右旋后
cr((c)) --- dr((d))
cr --- ar((a))
ar --- nil1r((nil))
ar --- br((b))
br --- er((e))
br --- nil2r((nil))
end

subgraph a右旋前
a((a)) --- b((b))
a --- c((c))
c --- d((d))
c --- nil1((nil))
b --- e((e))
b --- nil2((nil))
end

class a,ar,c,cr,e,er black
class b,br,d,dr red
class nil1,nil2,nil3,nil4,nil1r,nil2r nil

右旋过程：旋转节点的左子节点替代它的位置，旋转节点变成左子节点的右子节点，左子节点的右子节点变成旋转节点的左子节点。

**速记：**右旋变右，失去左，多余的右变成左。

规律：旋转的2个节点都是红色时，不会改变黑色高度。旋转也不会改变二叉查找树的特征。

1.2.3 插入

插入可能会破坏红黑树规则，就需要进行调整fix。

试想插入的过程，插入必然是替换某一个nil节点，插入的节点应该是红色还是黑色？如果插入黑色，特征5一定破坏，此时一定会调整，但是如果插入的是红色，此时只有规则4可能破坏（除非没有root节点，此时破坏规则2），即parent节点也是红色的时候才需要调整。

所以一般插入的节点预设的颜色是红色。此时考虑父节点是红色的几种情况：

graph TB
linkStyle default fill:none,stroke:#333,stroke-width:2px;
classDef red fill:red,color:#fff,stroke:none;
classDef black fill:#333,color:#fff,stroke:none;
classDef yellow fill:#EEEE00,color:#fff,stroke:none;
classDef nil fill:#333,color:#fff,stroke:none;

grand((g)) --- parent((p))
grand --- uncle((u?))
parent --- brother((b?))
parent --- nil((nil))

class grand black
class parent red
class uncle,brother yellow
class nil nil

上图中：

假如插入的节点current会放在parent节点下，此时brother节点一定是nil节点，因为如果是红色破坏规则4，是黑色破坏规则5。

uncle节点的颜色未定，如果为黑色，则一定是nil节点，否则破坏规则5；如果为红色，则他的子节点不能是红色，否则破坏规则4，如果子节点为黑色破坏规则5，此时只能是nil节点。

所以此时的情况，如果不考虑parent和uncle的左右，可以分为2大类情况：

1.2.3.1 uncle节点为nil

如果current < parent：

graph TB
linkStyle default fill:none,stroke:#333,stroke-width:2px;
classDef red fill:red,color:#fff,stroke:none;
classDef black fill:#333,color:#fff,stroke:none;
classDef yellow fill:#EEEE00,color:#fff,stroke:none;
classDef nil fill:#333,color:#fff,stroke:none;
classDef text fill:#fff,color:#333,stroke:none;

subgraph 步骤一insert
grand1((g)) --- parent1((p))
grand1 --- nil11((nil))
current1 --- nil31((nil))
current1 --- nil41((nil))
parent1 --- current1((c))
parent1 --- nil21((nil))
end

subgraph 步骤二grand和parent换颜色
grand2((g)) --- parent2((p))
grand2 --- nil12((nil))
current2 --- nil32((nil))
current2 --- nil42((nil))
parent2 --- current2((c))
parent2 --- nil22((nil))
end

subgraph 步骤三grand右旋
parent3((p)) --- current3((c))
current3 --- nil33((nil))
current3 --- nil43((nil))
parent3 --- grand3((g))
grand3 --- nil13((nil))
grand3 --- nil23((nil))
end

class grand1,parent2,parent3 black
class grand2,parent1,current1,current2,current3,grand3 red
class nil11,nil21,nil31,nil41,nil12,nil22,nil32,nil42,nil13,nil23,nil33,nil43 nil
class text1,text2 text

步骤二换颜色后，规则4满足，但是影响了最右边的一条路径，黑色数量-1了，不满足规则5，grand右旋后，前面受影响的路径黑色数量+1，数量复原，此时满足5，也满足4，并且原来grand的位置也还是黑色，也就不会影响祖父节点，至此调整完成。（并不是为了保证这个局部地方所有路径的黑色节点数量相同，而是要保证和之前的数量相同，这样才不会影响整棵树，如果都增加或减少了，虽然局部平衡了，但是整体必然失衡，还需要继续调整）

如果current > parent：

graph TB
linkStyle default fill:none,stroke:#333,stroke-width:2px;
classDef red fill:red,color:#fff,stroke:none;
classDef black fill:#333,color:#fff,stroke:none;
classDef yellow fill:#EEEE00,color:#fff,stroke:none;
classDef nil fill:#333,color:#fff,stroke:none;
classDef text fill:#fff,color:#333,stroke:none;

subgraph 步骤一insert
grand1((g)) --- parent1((p))
grand1 --- nil11((nil))
parent1 --- nil21((nil))
parent1 --- current1((c))
current1 --- nil31((nil))
current1 --- nil41((nil))
end

subgraph 步骤二parent左旋
grand2((g)) --- current2((c))
grand2 --- nil12((nil))
parent2 --- nil22((nil))
parent2 --- nil32((nil))
current2 --- parent2((p))
current2 --- nil42((nil))
end

class grand1,grand2 black
class parent1,parent2,current1,current2 red
class uncle,brother yellow
class nil11,nil21,nil31,nil41,nil12,nil22,nil32,nil42 nil
class text1,text2 text

左旋后和上面的insert状态一致，后续同样处理即可。

注意：对于parent在右，uncle在左的情况，最后grand旋转的时候，左旋即可。

1.2.3.2 uncle节点为red

graph TB
linkStyle default fill:none,stroke:#333,stroke-width:2px;
classDef red fill:red,color:#fff,stroke:none;
classDef black fill:#333,color:#fff,stroke:none;
classDef yellow fill:#EEEE00,color:#fff,stroke:none;
classDef nil fill:#333,color:#fff,stroke:none;

subgraph 步骤一insert
grand1((g)) --- parent1((p))
parent1 --- nil21((nil))
parent1 --- current1((c))
current1 --- nil51((nil))
current1 --- nil61((nil))
grand1 --- uncle1((u))
uncle1 --- nil31((nil))
uncle1 --- nil41((nil))
end

subgraph 步骤二颜色翻转
grand2((g)) --- parent2((p))
parent2 --- nil22((nil))
parent2 --- current2((c))
current2 --- nil52((nil))
current2 --- nil62((nil))
grand2 --- uncle2((u))
uncle2 --- nil32((nil))
uncle2 --- nil42((nil))
end

class grand1,parent2,uncle2 black
class parent1,uncle1,current1,current2,grand2 red
class nil11,nil21,nil31,nil41,nil51,nil61,nil12,nil22,nil32,nil42,nil52,nil62 nil

注意：不管current是在左边还是右边，parent和uncle的位置是在左边还是右边，调整的过程都是一样的，都是颜色翻转。

parent,uncle和grand的颜色翻转后，4条路径的黑色节点数量没有变化。看起来是没问题了，但是grand变成了红色，如果祖父节点也是红色，还需要继续调整，调整过程就是上述整个插入调整过程，因为插入调整就是处理2个连续红色节点问题，循环开始。最后调整完只要将root设置为黑色即可。

1.2.4 删除

红黑树首先是一颗二叉查找树，所以删除实际分2步走：

1.2.4.1 按二叉查找树删除

二叉树的结构决定了删除某个节点，这个节点的所在位置会被其他节点占据，除非这个节点没有后代。所以并不是简单的直接删除，还需要一个替换的动作。为了避免删除的过程中移动过多的节点，都是先找到替换者节点进行替换，然后再删除这个替换者。直至最后那个替换者是没有后代的，直接删除接可。

怎么找到替换者节点呢？

如果要删除的节点有右子树，那么替换的值必须要小于右子树中最小的值，所以用右子树中最小的值替换就行了，这个值肯定大于所有左子树的值，然后小于右子树所有值。

如果要删除的节点只有左子树，那么替换的值必须要大于所有左子树的值，很显然取左子树中的最大值替换即可。

现在问题变成了要获取右子树的最小值，左子树的最大值，这2个值就是中序遍历时，根节点左右2边的值。

1.2.4.1.1 删除没有后代的节点

比如0、7、13、36直接删除即可。

graph TB
2((2)) --- 1((1))
2 --- 33((33))
33 --- 25((25))
33 --- 40((40))
25 --- 11((11))
25 --- nil2((nil))
11 --- 7((7))
11 --- 12((12))
12 --- nil3((nil))
12 --- 13((13))
1 --- 0((0))
1 --- nil1((nil))
40 --- 34((34))
40 --- nil4((nil))
34 --- nil5((nil))
34 --- 36((36))

classDef node fill:#fff,stroke:#333;
classDef delete fill:#f8cecc;
class 0,7,13,36 delete

1.2.4.1.2 删除有右后代的节点

对33进行中序遍历，后面紧跟的是34，所以用34替换，然后再删除34节点。删除34的过程同样。

graph TB
2((2)) --- 1((1))
2 --- 33((33))
33 --- 25((25))
33 --- 40((40))
25 --- 11((11))
25 --- nil2((nil))
11 --- 7((7))
11 --- 12((12))
12 --- nil3((nil))
12 --- 13((13))
1 --- 0((0))
1 --- nil1((nil))
40 --- 34((34))
40 --- nil4((nil))
34 --- nil5((nil))
34 --- 36((36))

classDef node fill:#fff,stroke:#333;
classDef delete fill:#f8cecc;
classDef successor fill:#dae8fc;
class 33 delete
class 34 successor

1.2.4.1.3 删除只有左后代的节点

对25进行中序遍历，前面的值是13，所以用13替换，然后删除13。

graph TB
2((2)) --- 1((1))
2 --- 33((33))
33 --- 25((25))
33 --- 40((40))
25 --- 11((11))
25 --- nil2((nil))
11 --- 7((7))
11 --- 12((12))
12 --- nil3((nil))
12 --- 13((13))
1 --- 0((0))
1 --- nil1((nil))
40 --- 34((34))
40 --- nil4((nil))
34 --- nil5((nil))
34 --- 36((36))

classDef node fill:#fff,stroke:#333;
classDef delete fill:#f8cecc;
classDef successor fill:#dae8fc;
classDef predecessor fill:#d5e8d4;
class 25 delete
class 13 predecessor

上面整体是分了3种情况进行删除，实际仔细观察，删除25的情况，25只有左子节点，用上面的方法是13来替换，实际完全可以直接用11挂上去，此时11及它的后代依然满足二叉查找树，且都小于25的父节点33。同理只有右子节点的情况。

所以此时还可以分为以下3种情况：

没有后代，直接删除
只有一个后代，用该后代直接挂上去
有2个后代，按上述删除有右后代的节点的情况处理

2种模式都可以，前面一种模式更好理解。

1.2.4.2 按红黑树逻辑进行调整

根据二叉查找树的删除逻辑，删除实际上最后都是删除树叶（没有后代的节点），如果树叶是红色，删除不影响黑高，不需要调整，所以只需要考虑删除是黑色树叶的情况。

黑色树叶，意味着，必然存在兄弟节点（除非黑色树叶就是树根）。

考虑到对称性，此时只考虑要删除的黑色树叶是左子节点的情况，如果是右子节点作对称处理接可。

整体分为以下3种情况：

为便于理解，省略部分nil节点。

1.2.4.2.1 parent是红色，brother是黑色

1.2.4.2.1.1 brother没有后代，或者brother没有红色左子节点

graph TB
linkStyle default fill:none,stroke:#333,stroke-width:2px;
classDef red fill:red,color:#fff,stroke:none;
classDef black fill:#333,color:#fff,stroke:none;
classDef nil fill:#333,color:#fff,stroke:none;

subgraph 步骤一原始图
parent((p)) --- current((c))
parent --- brother((b))
end

subgraph 步骤二删除current
parent1((p)) --- nil1((nil))
parent1 --- brother1((b))
end

subgraph 步骤三parent左旋
brother2((b)) --- parent2((p))
brother2 --- nil2((nil))
parent2 --- nil4((nil))
end

class current,brother,brother1,brother2 black
class parent,parent1,parent2 red
class nil1,nil2,nil3,nil4 nil

说明：删除current，parent子树，左子树黑高 x - 1，右子树黑高x不变，parent左旋，左子树黑高 x - 1 + 1，右子树黑高x不变。整个parent子树黑高回到x，由parent子树内部解决冲突。

尝试把current看作一个子树来理解，有助于后面的理解。

1.2.4.2.1.2 brother有一个红色左子节点

brother是否有红色右子节点不影响。

graph TB
linkStyle default fill:none,stroke:#333,stroke-width:2px;
classDef red fill:red,color:#fff,stroke:none;
classDef black fill:#333,color:#fff,stroke:none;
classDef nil fill:#333,color:#fff,stroke:none;

subgraph 步骤一原始图
parent((p)) --- current((c))
parent --- brother((b))
brother --- left((l))
brother --- nil((nil))
end

subgraph 步骤二删除current
parent1((p)) --- nil1((nil))
parent1 --- brother1((b))
brother1 --- left1((l))
brother1 --- nil3((nil))
end

subgraph 步骤三brother右旋parent换色
parent2((p)) --- nil2((nil))
parent2 --- left2((l))
left2 --- nil4((nil))
left2 --- brother2((b))
end

subgraph 步骤四parent左旋
left3((l)) --- parent3((p))
left3 --- brother3((b))
end

class current,brother,brother1,brother2,parent2,parent3,brother3 black
class parent,parent1,left,left1,left2,left3 red
class nil,nil1,nil2,nil3,nil4 nil

说明：删除之前parent黑高为x，删除current之后，经过转换、旋转黑高依然为x，内部解决冲突。

1.2.4.2.2 parent是黑色，brother是红色

1.2.4.2.2.1 brother的左黑色子节点没有后代

brother右黑色子节点，有没有红色后代不影响。

graph TB
linkStyle default fill:none,stroke:#333,stroke-width:2px;
classDef red fill:red,color:#fff,stroke:none;
classDef black fill:#333,color:#fff,stroke:none;
classDef nil fill:#333,color:#fff,stroke:none;

subgraph 步骤一原始图
parent((p)) --- current((c))
parent --- brother((b))
brother --- left((l))
brother ---right((r))
end

subgraph 步骤二删除current
parent1((p)) --- nil1((nil))
parent1 --- brother1((b))
brother1 --- left1((l))
brother1 ---right1((r))
end

subgraph 步骤三parent左旋brother和left换色
brother2((b)) --- parent2((p))
brother2 --- right2((r))
parent2 --- nil4((nil))
parent2 --- left2((l))
end

class parent,parent1,current,brother2,left,right,left1,right1,parent2,right2 black
class brother,brother1,left2 red
class nil1,nil2,nil3,nil4 nil

说明：依然在parent子树内部解决冲突。

1.2.4.2.2.2 brother的左黑色子节点有红色右子节点

此时同样brother的右黑子节点有没有后代不影响

graph TB
linkStyle default fill:none,stroke:#333,stroke-width:2px;
classDef red fill:red,color:#fff,stroke:none;
classDef black fill:#333,color:#fff,stroke:none;
classDef nil fill:#333,color:#fff,stroke:none;

subgraph 步骤一原始图
parent((p)) --- current((c))
parent --- brother((b))
brother --- left((l))
brother ---right((r))
left --- nil((nil))
left --- left-right((lr))
end

subgraph 步骤二删除current
parent1((p)) --- nil1((nil))
parent1 --- brother1((b))
brother1 --- left1((l))
brother1 ---right1((r))
left1 --- nil2((nil))
left1 --- left-right1((lr))
end

subgraph 步骤三left-right换色brother右旋
parent2((p)) --- nil3((nil))
parent2 --- left2((l))
left2 --- nil4((nil))
left2 --- brother2((b))
brother2 --- left-right2((lr))
brother2 --- right2((r))
end

subgraph 步骤四parent左旋
left3((l)) --- parent3((p))
left3 --- brother3((b))
brother3 --- left-right3((lr))
brother3 --- right3((r))
end

class parent,parent1,current,left,right,left1,right1,parent2,right2,left2,left-right2,left3,parent3,left-right3,right3 black
class brother,brother1,left-right,left-right1,brother2,brother3 red
class nil,nil1,nil2,nil3,nil4,nil11 nil

说明：此时依然parent子树内部解决。

1.2.4.2.2.3 brother的左黑子节点有红色左子节点

brother左黑子节点有没有红色右子节点不影响。brother的右黑子节点有没有后代不影响。

graph TB
linkStyle default fill:none,stroke:#333,stroke-width:2px;
classDef red fill:red,color:#fff,stroke:none;
classDef black fill:#333,color:#fff,stroke:none;
classDef nil fill:#333,color:#fff,stroke:none;

subgraph 步骤一原始图
parent((p)) --- current((c))
parent --- brother((b))
brother --- left((l))
brother ---right((r))
left --- left-left((ll))
left --- left-right((lr))
end

subgraph 步骤二删除current
parent1((p)) --- nil1((nil))
parent1 --- brother1((b))
brother1 --- left1((l))
brother1 ---right1((r))
left1 --- left-left1((ll))
left1 --- left-right1((lr))
end

subgraph 步骤三left-left换色left右旋
parent2((p)) --- nil2((nil))
parent2 --- brother2((b))
brother2 --- left-left2((ll))
brother2 ---right2((r))
left-left2 --- nil3((nil))
left-left2 --- left2((l))
left2 --- nil4((nil))
left2 --- left-right2((lr))
end

class parent,parent1,current,left,right,left1,right1,parent2,right2,left2,left-left2 black
class brother,brother1,left-right,left-right1,brother2,left-left,left-left1,left-right2 red
class nil,nil1,nil2,nil3,nil4 nil

此时和上面的情况一样的了，对brother进行右旋，再对parent左旋。

1.2.4.2.3 parent是黑色，brother是黑色

1.2.4.2.3.1 brother有红色右子节点

graph TB
linkStyle default fill:none,stroke:#333,stroke-width:2px;
classDef red fill:red,color:#fff,stroke:none;
classDef black fill:#333,color:#fff,stroke:none;
classDef nil fill:#333,color:#fff,stroke:none;

subgraph 步骤一原始图
parent((p)) --- current((c))
parent --- brother((b))
brother --- nil((nil))
brother --- right((r))
end

subgraph 步骤二删除current
parent1((p)) --- nil1((nil))
parent1 --- brother1((b))
brother1 --- nil2((nil))
brother1 --- right1((r))
end

subgraph 步骤三right换色parent左旋
brother2((b)) --- parent2((p))
brother2 --- right2((r))
end

class parent,parent1,parent2,current,brother,brother1,brother2,right2 black
class right,right1 red
class nil,nil1,nil2,nil3 nil

1.2.4.2.3.2 brother只有红色左子节点

graph TB
linkStyle default fill:none,stroke:#333,stroke-width:2px;
classDef red fill:red,color:#fff,stroke:none;
classDef black fill:#333,color:#fff,stroke:none;
classDef nil fill:#333,color:#fff,stroke:none;

subgraph 步骤一原始图
parent((p)) --- current((c))
parent --- brother((b))
brother --- left((l))
brother --- nil((nil))
end

subgraph 步骤二删除current
parent1((p)) --- nil1((nil))
parent1 --- brother1((b))
brother1 --- left1((l))
brother1 --- nil2((nil))
end

subgraph 步骤三left换色brother右旋parent左旋
left2((l)) --- parent2((p))
left2 --- brother2((r))
end

class parent,parent1,parent2,current,brother,brother1,brother2,left2 black
class left,left1 red
class nil,nil1,nil2,nil3 nil

1.2.4.2.3.3 brother没有后代

graph TB
linkStyle default fill:none,stroke:#333,stroke-width:2px;
classDef red fill:red,color:#fff,stroke:none;
classDef black fill:#333,color:#fff,stroke:none;
classDef nil fill:#333,color:#fff,stroke:none;

subgraph 步骤一原始图
parent((p)) --- current((c))
parent --- brother((b))
end

subgraph 步骤二删除current
parent1((p)) --- nil1((nil))
parent1 --- brother1((b))
end

subgraph 步骤三brother换色
parent2((p)) --- nil2((nil))
parent2 --- brother2((b))
end

class parent,parent1,parent2,current,brother,brother1 black
class brother2 red
class nil1,nil2 nil

当前情况下想通过parent子树内部完成平衡是不可能的了，处理方式是将整个parent子树黑高 - 1。

此时可以把整个parent子树当作current，current是一颗根为黑色的子树，然后current黑高 - 1了，现在需要进行平衡，同样的根据parent和brother的情况判断：

此时current子树初始黑高肯定是大于1的，则current兄弟子树黑高 >= 2。

一颗树或子树的根到任意叶子节点的黑高相同，则该树或子树的任意节点至任意可到达的叶子节点的黑高也是相同的。所以只需要关注根到叶子节点黑色高度的变化。而-tree子树内部不需要关注，只需要保证-tree至根经过的黑色节点数量和以前一样即可。**

1.2.4.2.3.4 brother左子节点不是红色，对应上面1.2.4.2.1.1，操作也是parent直接左旋。

可以把brother的左子节点left看作根是黑色的子树，黑高x-1

graph TB
linkStyle default fill:none,stroke:#333,stroke-width:2px;
classDef red fill:red,color:#fff,stroke:none;
classDef black fill:#333,color:#fff,stroke:none;
classDef nil fill:#333,color:#fff,stroke:none;
classDef white fill:#fff,color:#333,stroke:none;

parent((p)) --- current((c))
parent --- brother((b))
current --- c-left((c-l-tree))
current --- c-right((c-r-tree))
brother --- b-left((l))
brother --- b-right((b-r-tree))

class current,brother,b-left black
class parent red
class c-left,c-right,b-right white
class nil1,nil2,nil3,nil4 nil

1.2.4.2.3.5 brother有一个红色左子节点，操作同上面1.2.4.2.1.2，brother右旋，parent换色，parent左旋

此时l-l-tree,l-l-tree黑高x-1,b-r-tree黑高也是x-1。brother右旋，l-l-tree为brother左子节点，parent左旋，l-l-tree为parent右子节点，且parent为黑色，此时从left出发，到所有tree黑高都是x，调整完成。

graph TB
linkStyle default fill:none,stroke:#333,stroke-width:2px;
classDef red fill:red,color:#fff,stroke:none;
classDef black fill:#333,color:#fff,stroke:none;
classDef nil fill:#333,color:#fff,stroke:none;
classDef white fill:#fff,color:#333,stroke:none;

parent((p)) --- current((c))
parent --- brother((b))
current --- c-left((c-l-tree))
current --- c-right((c-r-tree))
brother --- b-left((l))
brother --- b-right((b-r-tree))
b-left --- l-left((l-l-tree))
b-left --- l-right((l-r-tree))

class current,brother black
class parent,b-left red
class c-left,c-right,b-right,l-left,l-right white
class nil1,nil2,nil3,nil4 nil

1.2.4.2.3.6 parent黑色，brother红色，brother左黑子节点没有直接红色后代，操作同样对应1.2.4.2.2.1。brother、left换色，parent左旋

l-l-tree和l-r-tree的根不是红色

graph TB
linkStyle default fill:none,stroke:#333,stroke-width:2px;
classDef red fill:red,color:#fff,stroke:none;
classDef black fill:#333,color:#fff,stroke:none;
classDef nil fill:#333,color:#fff,stroke:none;
classDef white fill:#fff,color:#333,stroke:none;

parent((p)) --- current((c))
parent --- brother((b))
current --- c-left((c-l-tree))
current --- c-right((c-r-tree))
brother --- b-left((l))
brother --- b-right((r))
b-left --- l-left((l-l-tree))
b-left --- l-right((l-r-tree))
b-right --- r-left((r-l-tree))
b-right --- r-right((r-r-tree))
class parent,current,b-right,b-left black
class brother,b-left,brother red
class c-left,c-right,l-left,l-right,r-left,r-right white
class nil1,nil2,nil3,nil4 nil

1.2.4.2.3.7 parent黑色，brother红色，brother左黑子节点有红色右子节点且左子节点不是红色，同样对应上面操作1.2.4.2.2.2。lr换色，brother右旋，parent左旋。

graph TB
linkStyle default fill:none,stroke:#333,stroke-width:2px;
classDef red fill:red,color:#fff,stroke:none;
classDef black fill:#333,color:#fff,stroke:none;
classDef nil fill:#333,color:#fff,stroke:none;
classDef white fill:#fff,color:#333,stroke:none;

parent((p)) --- current((c))
parent --- brother((b))
current --- c-left((c-l-tree))
current --- c-right((c-r-tree))
brother --- b-left((l))
brother --- b-right((r))
b-left --- l-left((l-l-tree))
b-left --- l-right((lr))
b-right --- r-left((r-l-tree))
b-right --- r-right((r-r-tree))
class parent,current,b-right,b-left black
class brother,b-left,brother,l-right red
class c-left,c-right,l-left,r-left,r-right white
class nil1,nil2,nil3,nil4 nil

1.2.4.2.3.8 parent黑色，brother红色，brother左黑子节点有红色左子节点，操作同1.2.4.2.2.3。ll换色，left右旋，brother右旋，parent左旋。

graph TB
linkStyle default fill:none,stroke:#333,stroke-width:2px;
classDef red fill:red,color:#fff,stroke:none;
classDef black fill:#333,color:#fff,stroke:none;
classDef nil fill:#333,color:#fff,stroke:none;
classDef white fill:#fff,color:#333,stroke:none;

parent((p)) --- current((c))
parent --- brother((b))
current --- c-left((c-l-tree))
current --- c-right((c-r-tree))
brother --- b-left((l))
brother --- b-right((r))
b-left --- l-left((ll))
b-left --- l-right((l-r-tree))
b-right --- r-left((r-l-tree))
b-right --- r-right((r-r-tree))
l-left --- l-left-left-tree((ll-l-tree))
l-left --- l-left-right-tree((ll-r-tree))
class parent,current,b-right,b-left black
class brother,b-left,brother,l-left red
class c-left,c-right,l-right,r-left,r-right,l-left-left-tree,l-left-right-tree white
class nil1,nil2,nil3,nil4 nil

1.2.4.2.3.9 parent黑色，brother黑色，brother有红色右子节点，操作同1.2.4.2.3.1。right换色，parent左旋。

graph TB
linkStyle default fill:none,stroke:#333,stroke-width:2px;
classDef red fill:red,color:#fff,stroke:none;
classDef black fill:#333,color:#fff,stroke:none;
classDef nil fill:#333,color:#fff,stroke:none;
classDef white fill:#fff,color:#333,stroke:none;

parent((p)) --- current((c))
parent --- brother((b))
current --- c-left((c-l-tree))
current --- c-right((c-r-tree))
brother --- b-left((l))
brother --- b-right((r))
b-left --- l-left((l-l-tree))
b-left --- l-right((l-r-tree))
b-right --- r-left((r-l-tree))
b-right --- r-right((r-r-tree))
class parent,current,b-left,brother black
class b-right red
class c-left,c-right,l-left,l-right,r-left,r-right white
class nil1,nil2,nil3,nil4 nil

1.2.4.2.3.10 parent黑色，brother黑色，brother左子节点是红色，右子节点不是红色，操作同1.2.4.2.3.2。left换色，brother右旋，parent左旋。

graph TB
linkStyle default fill:none,stroke:#333,stroke-width:2px;
classDef red fill:red,color:#fff,stroke:none;
classDef black fill:#333,color:#fff,stroke:none;
classDef nil fill:#333,color:#fff,stroke:none;
classDef white fill:#fff,color:#333,stroke:none;

parent((p)) --- current((c))
parent --- brother((b))
current --- c-left((c-l-tree))
current --- c-right((c-r-tree))
brother --- b-left((l))
brother --- b-right((r))
b-left --- l-left((l-l-tree))
b-left --- l-right((l-r-tree))
b-right --- r-left((r-l-tree))
b-right --- r-right((r-r-tree))
class parent,current,b-right,brother black
class b-left red
class c-left,c-right,l-left,l-right,r-left,r-right white
class nil1,nil2,nil3,nil4 nil

1.2.4.2.3.11 parent黑色，brother黑色，brother没有红色子节点，操作同1.2.4.2.3.3。当前子树已经解决不了，brother换色，整个子树黑高 - 1，抛给上层去处理。

graph TB
linkStyle default fill:none,stroke:#333,stroke-width:2px;
classDef red fill:red,color:#fff,stroke:none;
classDef black fill:#333,color:#fff,stroke:none;
classDef nil fill:#333,color:#fff,stroke:none;
classDef white fill:#fff,color:#333,stroke:none;

parent((p)) --- current((c))
parent --- brother((b))
current --- c-left((c-l-tree))
current --- c-right((c-r-tree))
brother --- b-left((l))
brother --- b-right((r))
b-left --- l-left((l-l-tree))
b-left --- l-right((l-r-tree))
b-right --- r-left((r-l-tree))
b-right --- r-right((r-r-tree))
class parent,current,b-right,b-left,brother black
class brother red
class c-left,c-right,l-left,l-right,r-left,r-right white
class nil1,nil2,nil3,nil4 nil

1.2.4.3 总结

删除的红黑调整过程，只有1.2.4.2.3.11是无法在当前子树内解决的，需要递归向上遍历，交给上层来处理，处理的过程同样根据parent和brother的情况判断，这个过程需要把子节点当作子树来理解，原则是子树上面黑色节点的数量要保持不变，current子树上面的黑色节点数量 + 1。整体分为多种情况，第11种情况要重复前面的情况，而这几种情况中部分处理方式最终一致，所以整体看是用了6种处理方式。

anyw's notebook

Explorer

Algorithms

算法