红黑树的删除操作

灰太狼 2022-01-14 04:19 1008阅读 0赞

原文：[https://segmentfault.com/a/1190000012115424][https_segmentfault.com_a_1190000012115424]

**可能出现的情形讨论**

删除红黑树中一个结点，删除的结点是其子结点状态和颜色的组合。子结点的状态有三种：无子结点、只有一个子结点、有两个子结点。颜色有红色和黑色两种。所以共会有6种组合。

**组合1：被删结点无子结点，且被删结点为红色**

此时直接将结点删除即可，不破坏任何红黑树的性质。

**组合2：被删结点无子结点，且被删结点为黑色**

处理方法略微复杂，稍后再议。

**组合3：被删结点有一个子结点，且被删结点为红色**

![20190616114840873.png][]

这种组合是不存在的，如图假如被删结点node只有一个有值的子结点value，而以value为根结点的子树中，必然还存在null结点，如此不符合红黑树的性质5，对每个结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数目的黑色结点。

**组合4：被删结点有一个子结点，且被删结点为黑色**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2E5NDQ3NTA0NzE_size_16_color_FFFFFF_t_70][]

这种组合下，被删结点node的另一个子结点value必然为红色，此时直接将node删掉，用value代替node的位置，并将value着黑即可。

**组合5&6：被删结点有两个子结点，且被删结点为黑色或红色**

当被删结点node有两个子结点时，先要找到这个被删结点的后继结点successor，然后用successor代替node的位置，同时着成node的颜色，此时相当于successor被删。

因为node有两个子结点，所以successor必然在node的右子树中，必然是下图两种形态中的一种。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2E5NDQ3NTA0NzE_size_16_color_FFFFFF_t_70 1][]

若是(a)的情形，用successor代替node后，相当于successor被删，若successor为红色，则变成了组合1；若successor为黑色，则变成了组合2。

若是(b)的情形，用successor代替node后，相当于successor被删，若successor为红色，则变成了组合1；若successor为黑色，则变成了组合2或4。

**综上**

若被删结点是组合1或组合4的状态，很容易处理；被删结点不可能是组合3的状态；被删结点是组合5&6的状态，将变成组合1或组合2或组合4。

**再议组合2：被删结点无子结点，且被删结点为黑色**

因为删除黑色结点会破坏红黑树的性质5，所以为了不破坏性质5，在替代结点上额外增加一个黑色，这样不违背性质5而只违背性质1，每个结点或是黑色或是红色。此时将额外的黑色移除，则完成删除操作。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2E5NDQ3NTA0NzE_size_16_color_FFFFFF_t_70 2][]

然后再结合node原来的父结点father和其兄弟结点brother来分析。

**情形一**

**brother****为黑色，且brother有一个与其方向一致的红色子结点son**，所谓方向一致，是指brother为father的左子结点，son也为brother的左子结点；或者brother为father的右子结点，son也为brother的右子结点。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2E5NDQ3NTA0NzE_size_16_color_FFFFFF_t_70 3][]

图(c)中，白色代表随便是黑或是红，方形结点除了存储自身黑色外，还额外存储一个黑色。将brother和father旋转，并重新上色后，变成了图(d)，方形结点额外存储的黑色转移到了father，且不违背任何红黑树的性质，删除操作完成。

图(c)中的情形颠倒过来，也是一样的操作。

**情形二**

**brother****为黑色，且brother有一个与其方向不一致的红色子结点son**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2E5NDQ3NTA0NzE_size_16_color_FFFFFF_t_70 4][]

图(e)中，将son和brother旋转，重新上色后，变成了图(f)，情形一。

图(e)中的情形颠倒过来，也是一样的操作。

**情形三**

**brother****为黑色，且brother无红色子结点**

此时若father为红，则重新着色即可，删除操作完成。如图下图(g)和(h)。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2E5NDQ3NTA0NzE_size_16_color_FFFFFF_t_70 5][]

此时若father为黑，则重新着色，将额外的黑色存到father，将father作为新的结点进行情形判断(不删除)，遇到情形一、情形二，则进行相应的调整，完成删除操作；如果没有，则结点一直上移，直到根结点存储额外的黑色，此时将该额外的黑色移除，即完成了删除操作。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2E5NDQ3NTA0NzE_size_16_color_FFFFFF_t_70 6][]

**情形四**

**brother****为红色**，则father必为黑色。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2E5NDQ3NTA0NzE_size_16_color_FFFFFF_t_70 7][]

图(i)中，将brother和father旋转，重新上色后，变成了图(j)，新的brother变成了黑色，这样就成了情形一、二、三中的一种。如果将son和brother旋转，无论怎么重新上色，都会破坏红黑树的性质4或5，例如图(k)。  
图(i)中的情形颠倒过来，也是一样的操作。

[https_segmentfault.com_a_1190000012115424]: https://segmentfault.com/a/1190000012115424
[20190616114840873.png]: /images/20220113/7b086df8bf4b48349e18b8ed45c1a9b6.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2E5NDQ3NTA0NzE_size_16_color_FFFFFF_t_70]: /images/20220113/1dc7b6013cad4d27a750ad51a1b280b3.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2E5NDQ3NTA0NzE_size_16_color_FFFFFF_t_70 1]: /images/20220113/4a9fa8d673714d9696f5c27035700650.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2E5NDQ3NTA0NzE_size_16_color_FFFFFF_t_70 2]: /images/20220113/8e23fa3e96ea4c31beb2f5f708690079.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2E5NDQ3NTA0NzE_size_16_color_FFFFFF_t_70 3]: /images/20220113/96e84e808b974c47ba1d6f3416433301.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2E5NDQ3NTA0NzE_size_16_color_FFFFFF_t_70 4]: /images/20220113/b9912ab55cc148a5af360ba417604c75.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2E5NDQ3NTA0NzE_size_16_color_FFFFFF_t_70 5]: /images/20220113/ca28cdf507144338b68627295c9189fa.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2E5NDQ3NTA0NzE_size_16_color_FFFFFF_t_70 6]: /images/20220113/948a1feb108f4699a240b24990467c94.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2E5NDQ3NTA0NzE_size_16_color_FFFFFF_t_70 7]: /images/20220113/c76d2310f5a4448fb493fec4197a5fd4.png