数据结构与算法（十三）中红黑树2的原理是什么？

本文共计3785个文字，预计阅读时间需要16分钟。

三、删除类类似于排序的二叉树，排序二叉树主要分为三种情况： （1）删除没有左右子节点的节点，即度为0的节点。 （2）删除只有一个子节点的节点，即度为1的节点。 （3）删除有两个子节点的节点。

三、删除 1、介绍

　　红黑树的删除类似于排序二叉树，排序二叉树主要分为三种情况：
　　（1）删除没有左孩子且没有右孩子的结点。即：度为0。
　　（2）删除只有左（右）孩子的结点。即：度为1。
　　（3）删除有左孩子且有右孩子的结点。即：度为2。
　　由于红黑树还有颜色的区分，所以在上述三种情况的基础上加上颜色，就是六种情况。以{15,7,45,3,10,25,55,1,5,75}为例：

　　红黑树有六种情况：
　　（1）删除度为0的黑色结点。比如：10、25。
　　（2）删除度为0的红色结点。比如：1、5、75。
　　（3）删除度为1的黑色结点。比如：55。
　　（4）删除度为1的红色结点。这种情况不存在。
　　（5）删除度为2的黑色结点。比如：3、15。
　　（6）删除度为2的红色结点。比如：7、45。

2、说明

　　论证：度为1的红色结点，在红黑树中，是不存在的！
　　所有度为1的情况只有以下4种，这里都画的右孩子，左孩子也是同理。

　　其中：
　　"黑-黑"和"红-黑"，这两种情况，都不符合红黑树的性质（4）从任意一个结点到其所有叶子结点，所经过的黑色结点数目必须相等。
　　"红-红"，不符合红黑树的性质（5）所有红色结点的两个孩子结点必须是黑色（即，红色结点不能连续）。
　　只有"黑-红"这种情况存在。所以，度为1的结点，也必然是"黑-红"这种情况。