红黑树原理1? ? 记录了红黑树的新增元素操作。
一、红黑树删除节点
删除节点分为如下几种情况。
1、没有叶子结点
? ? ? ? 1.1、节点本身是红，无需修复，直接删掉即可。
? ? ? ? 1.2、节点本身是黑色，会破坏红黑树规则，需要修复。
2、有一个叶子结点。例：父节点叫做 p ，子节点叫做 s ，p 和 s 的值进行交换，就变为1.1,1.2情况。（父节点和子节点不能同为红色节点，红黑树规则）
? ? ? ? 2.1、父节点 p 是黑色，子节点 s 是红色，删除p，p 节点的值和 s 节点的值进行交换，就变为删除 s 节点，也就是节点本身是红，无叶子结点，1.1 情况。
? ? ? ? 2.2、父节点 p 可能是红，也可能是黑，子节点 s 是黑色。p 节点的值和 s 节点的值进行交换，就变为删除 s 节点，也就是节点本身是黑，无叶子结点，1.2 情况。
3、有两个叶子结点，父节点叫做 p，子节点叫做 N，父节点和任意子节点交换。
? ? ? ? 3.1、子节点 N 是叶子结点，无后继节点，交换后就对应 1.1,1.2 情况。
? ? ? ? 3.2、若N节点还有一个子节点，交换值后就对应情况2。
综上所述：所有问题都可简化，汇总到 1.1,1.2 情况，1.1情况不需要解决，也就是需要解决1.2问题。
如下图所示，1.2问题细化分支；下面针对每一种情况画图解析。
?情况1：被删除节点在左侧，兄弟节点是红的节点
????????1、将兄弟节点设为黑色。
????????2、将兄弟节点的左孩子节点设为红色。
????????3、对父节点进行左旋。
?情况2：被删除节点在左侧，兄弟节点是黑色的节点，无叶子结点
? ? ? ? 将兄弟节点变为红色节点，若父节点也是红色节点，需要向上递归，达到平衡。
情况3：被删除节点在左侧，兄弟节点是黑色的节点，有左侧叶子结点。
????????1、将左侧叶子结点变为黑色
????????2、将兄弟节点设为红色
????????3、对兄弟节点进行右旋，到情况4
?
情况4：被删除节点在左侧，兄弟节点是黑色的节点，有右侧叶子结点。
????????1、将父节点的颜色给兄弟节点。
????????2、将父节点和兄弟节点的右孩子都设为黑色节点。
????????3、将父节点左旋。父节点可向上递归修改颜色。
情况5：被删除节点在左侧，兄弟节点是黑色的节点，有两侧叶子结点。
????????1、将父节点的颜色给兄弟节点。
????????2、将兄弟节点的右孩子设为黑色。
????????3、将父节点设为黑色。
????????4、对父节点进行左旋。
?情况6：被删除节点在右侧，兄弟节点是黑色的节点，无叶子结点。
? ? ? ? 将兄弟节点变为红色节点，若父节点也是红色节点，需要向上递归，达到平衡。
情况7：被删除节点在右侧，兄弟节点是黑色的节点，有左侧叶子结点。
????????1、将父节点的颜色给兄弟节点。
????????2、将父节点和左侧叶子节点的颜色都设为黑色。
????????3、对父节点进行右旋。
情况8：被删除节点在右侧，兄弟节点是黑色的节点，有右侧叶子结点
????????1、将父节点的右孩子设为黑色。
????????2、将兄弟节点设为红色。
????????3、将兄弟节点左旋。
????????回到情况7
情况10：被删除节点在右侧，兄弟节点是黑色节点，兄弟节点右两个子节点
????????1、将父节点的颜色给兄弟节点
????????2、将兄弟节点的左孩子设为黑色
????????3、将父节点设为黑色
????????4、对父节点进行右旋
情况10：被删除节点在右侧，兄弟节点是红的节点
????????1、将兄弟节点设为黑色。
????????2、将兄弟节点的右孩子节点设为红色。
????????3、对父节点进行右旋。
?以上就是红黑树删除节点操作详解。
?
?
?
?