作为一种数据结构，在红黑树中，最重要的当然就是增删改查啦，下面我们就来了解一下红黑树如何删除吧。

红黑树时间复杂度证明

首先我们得先了解红黑树的时间复杂度，红黑树的时间复杂度为: O(logn)

下面通过“数学归纳法”对红黑树的时间复杂度进行证明。

定理：一棵含有n个节点的红黑树的高度至多为2log(n+1).

证明：

"一棵含有n个节点的红黑树的高度至多为2log(n+1)" 转换一下就是 "高度为h的红黑树，它的包含的内节点个数至少为 2^(h/2)-1个"。

我们只需要证明后面那个命题，即可证明原命题为真;即只需证明 "高度为h的红黑树，它的包含的内节点个数至少为 2^(h/2)-1个"。

从某个节点x出发(不包括该节点)到达一个它子孙外部节点的任意一条路径上，黑色节点的个数称为该节点的黑高度(x's black height)，记为bh(x)。关于bh(x)有两点需要说明：

第1点：根据红黑树的"特性(5) ，即从一个节点到该节点的子孙外部节点的所有路径上包含相同数目的黑节点"可知，从节点x出发到达的所有的叶节点具有相同数目的黑节点。这也就意味着，bh(x)的值是唯一的!

第2点：根据红黑色的"特性(4)，即如果一个节点是红色的，则它的子节点必须是黑色的"可知，从节点x出发达到叶节点"所经历的黑节点数目">= "所经历的红节点的数目"。假设x是根节点，则可以得出结论"bh(x) >= h/2"。进而，我们只需证明 "高度为h的红黑树，它的包含的内节点个数至少为 2^bh(x)-1个"即可。

到这里，我们将需要证明的定理已经由

"一棵含有n个节点的红黑树的高度至多为2log(n+1)"

转变成只需要证明

"高度为h以x为根的红黑树，它的包含的内节点个数至少为 2^bh(x)-1个"。

红黑树删除情节

一、从树中删除节点X(以寻找后继节点的方式进行删除)

情况①：如果X没有孩子，且如果X是红色，直接删除X;如果X是黑色，则以X为当前节点进行旋转调色，最后删掉X

情况②：如果X只有一个孩子C，交换X和C的数值，再对新X进行删除。根据红黑树特性，此时X不可能为红色，因为红色节点要么没有孩子，要么有两个黑孩子。此时以新X为当前节点进行情况①的判断

情况③：如果X有两个孩子，则从后继中找到最小节点D，交换X和D的数值，再对新X进行删除。此时以新X为当前节点进行情况①或②的判断

二、旋转调色(N=旋转调色的当前节点[等于情况①中的X]，P=N的父亲，W=N的兄弟，Nf=N的远侄子，Nn=N的近侄子)

情况1：N是根或者N是红色，则：直接将N设为黑色。

情况2：N不是根且N是黑色，且W为红色，则：将W设为黑色，P设为红色，对P进行旋转(N为P的左子时进行左旋，N为P的右子时进行右旋)，将情况转化为情况1、2、3、4、5。

情况3：N不是根且N是黑色，且W为黑色，且W的左右子均为黑色，则：将W设为红色，将P设为当前节点进行旋转调色，将情况转化为情况1、2、3、4、5。

情况4：N不是根且N是黑色，且W为黑色，且Nf为黑色，Nn为红色，则：交换W与Nn的颜色，并对W进行旋转(N为P的左子进行右旋，N为P的右子进行左旋)，旋转后N的新兄弟W有一个红色WR，则转换为情况5。

情况5：N不是根且N是黑色，且W为黑色，且Nf为红色，Nn为黑色，则：将W设为P的颜色，P和Nf设为黑色，并对P进行旋转(N为P的左子进行左旋，N为P的右子进行右旋)，N设为根。

以上就是今天的所有内容了，更多有关Java一些知识问答的内容请持续关注本站吧。