红黑树的插入与删除

一、红黑树的删除

情况一：删除的结点D（黑色）不存在左右孩子

被删除的结点分为其父结点的左孩子和右孩子，然后再分为下面这5种情况：

1.1.兄弟结点为红色(一定存在两个黑侄子)：

1.2兄弟结点为黑色，近侄子为红色：

1.3兄弟结点为黑色，远侄子为红色：

1.4兄弟结点为黑色，两个红色侄子：

1.5兄弟结点为黑色，没有侄子：

情况二：删除的结点D（红色）不存在左右孩子：直接删除（最简单的情况）

情况三：删除的结点D只有一个左孩子（结点一定是黑色，孩子一定是红色）：左孩子替换掉D,删除左孩子。

情况四：删除的结点D只有一个右孩子（结点一定是黑色，孩子一定是红色）：右孩子替换掉D，删除右孩子。

情况五：删除的结点D有左右孩子（红黑都可以，一样分析）：找到左子树的最大值，用该值替换要被删除的值，然后删除这个找到的最大值，这个最大值要么有一个左孩子，要么没有子结点，所以可以转换成上面的四种情况。

写代码的时候这样分：左右孩子都存在（情况五），只有一个孩子（情况三和情况四），左右孩子都不存在（2*10+1种情况，见上面的情况一和情况二）

插入比删除的情况少很多。

插入位置的父结点如果为红色，就需要进行修复。

先分颜色，然后在判断父亲，叔叔，自己的位置。

叔叔为红。叔叔为黑（或者不存在)。

父左，自己左。父左，自己右。父右，自己左。父右，自己右。

其实插入和删除最主要的是在插入和删除之后对红黑树的修复，因为在插入和删除操作之后，有可能会破坏红黑树的特性，找到需要修复的那几种情况，其他的正常删除和插入就好了。

最后

以上就是酷炫小笼包为你收集整理的红黑树的插入与删除的全部内容，希望文章能够帮你解决红黑树的插入与删除所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。