本篇要讲的就是红黑树的删除操作
红黑树插入操作请参考 数据结构 - 红黑树 (Red Black Tree) 插入详解与实现(Java)
红黑树的删除是红黑树操作中比较麻烦且比较有意思的一部分.
在此之前, 重申一遍红黑树的五个定义:
1. 红黑树的节点不是黑色的就是红色的
2. 红黑树的根节点一定是黑色的
3. 红黑树的所有叶子节点都是黑色的(注意: 红黑树的叶子节点指 Nil 节点)
4. 红黑树任何路径上不允许出现相邻两个红色节点
5. 从红黑树的任一节点开始向下到任意叶子节点所经过的黑色节点数目相同
接着, 请大家谨记你操作的对象都是一颗标准的红黑树, 所以不要脑补过多不能存在的情况, 如果你考虑的情况不在本文的讨论范围之内, 可以往上看看是不是你的情况违反了五条规则其中某一条, 若还有疑问, 欢迎留言讨论.
D(Delete)表示待删除节点
P(Parent)表示待删除节点的父节点
S(Sibling)表示待删除节点的兄弟节点
U(Uncle)表示带删除节点的叔叔节点
GP(Grandparent)表示待删除节点的祖父节点
XL(Left child of X)表示节点 X 的左子树节点
XR(Right child of X)表示节点 X 的右子树节点
删除一个新的节点有以下四种情况:
1. 删除的节点是叶子节点(非 Nil)
2. 删除的节点只有左子树
3. 删除的节点只有右子树
*4. 删除的节点同时拥有左子树和右子树
其实只有上面前三种情况, 对于第四种情况, 可以找到待删除节点的直接后继节点, 用这个节点的值代替待删除节点, 接着情况转变为删除这个直接后继节点, 情况也变为前三种之一.
因为有很多情况是不存在, 待删除节点是叶子节点 (非 Nil) 的情况稍微复杂一些,
我们下面先考虑待删除的节点只有左子树或只有右子树的情况.
不存在的情况包括
1
2
(san)
4
5
6
请读者分析一下上面不可能情况的原因, 不复杂但一定要知道为什么. 两个节点的颜色红黑情况加上左右子树情况, 总共八种情况, 上面已经排除了六种, 剩下以下两种可能的的情况.
1
DL 表示 DL 节点原本的值
2
DR 表示 DR 节点原本的值
这两种情况的调整操作比较简单, 直接用 DL/DR 的元素值代替 D 的元素, 再把 DL/DR 直接删去就好, 操作过后不违反红黑树定义, 删除结束.
删除节点的四种情况已经解决了三种, 剩下最后一种了.
待删除的节点是叶子节点的情况:
因为待删除的节点有可能是红色也可能是黑色.
如果待删除节点是红色的, 那直接删去这个节点, 删除结束.
如果待删除节点是黑色的, 根据父节点 P 和兄弟节点 S 的情况, 可分为以下五种情况.
情况 1: 父节点 P 是红色节点
或者
这两种情况是一样的, 我们讨论第一个图就好, 当把 D 删去后, 从 P 的左子树下来的黑色节点数目少了一, 对应的调整做法为, 把 P 染成黑色, 此时 P 左子树的黑色结点数目恢复, 但此时右子树黑色结点数目多了一, 再把 S 对应染成红色即可.
图例:
情况 2: 兄弟节点 S 是红色节点
或者
只能是这两种情形, 做法是把 P 染成红色, S 染成黑色, 然后以 P 为轴做相应的旋转操作(如果 D 为 P 的左子树节点则以 P 为轴做左旋操作, 如果 D 为 P 的右子树节点则以 P 为轴做右旋操作)
图例(以第一种情形为例):
到这里就把情况二变成了情况一 (父节点为红色) 的情况, 接着按照情况一的处理方式进行操作.
情况 3: 结点 D 的远亲侄子为红色节点的情况
此时父节点 P 的颜色可红可黑, 这种情况的调整做法是, 交换 P 和 S 的颜色, 然后把远侄子节点 SR/SL 设置为黑色, 再以 P 为轴做相应的旋转操作(如果 D 为 P 的左子树则左旋, 如果 D 为 P 的右子树则右旋)
图例(以第一种情形为例):
调整前后从 P 点下来的所有路径黑色节点数目没有发生变化, 删除节点 D 后结束.(注意此处 S 的左子树 SL 可以为 Nil 节点或者红色节点, 但依然是按照上面的规则进行调整, 对结果没有影响)
情况 4: 节点 D 的近亲侄子为红色节点的情况
注意此处节点 D 的远侄子节点必须为 Nil 节点, 否则就变成情况 3 了. 这种情况的调整方式是, 把 S 染成红色, 把近侄子节点 SR/SL 染成黑色, 然后以节点 S 为轴做相应的旋转操作(如果 D 为 P 的左子树则以 S 为轴做右旋操作, 如果 D 为 P 的右子树则以 S 为轴做左旋操作).
图例(以第一种情形为例)
然后就真的变成情况 3 了...... 接着按照情况 3 的处理方式进行处理.
情况 5: 节点 D,P,S 均为黑色节点
以第一种情形为例, 这种情况删除 D 之后, 从 P 的左子树下来的黑色节点数目少了一, 且没有周围也没有红节点来补全这个黑节点, 做法就是把 D 删去, 然后把节点 S 染成红色, 这样一来节点 P 的左右子树路径的黑色节点路径就一样了, 但导致节点 P 整棵子树的任意路径的黑色节点数比其他路径少了一, 此时我们再从 P 开始 (即把 P 当成 D), 但不再删除 P, 向上继续调整, 直到根节点(一直是情况 5) 或者遇到情况 1~4 并调整后结束.
我看过几篇文章, 最后一种情况基本讲到我这里就已经结束了, 所以我在这种情况上也因此多话了一点时间去理解. 若此处有更详细的例子, 会更能帮助理解, 所以我决定举两个例子, 来说明什么叫从 P 节点开始向上调整, 哪种情况就是要直到根节点, 哪种情况就是遇到情况 1~4, 然后调整后结束.
从节点 P 往上依然是全黑的情况(父节点, 兄弟节点均为黑色)
从节点 P 往上是其他情况
这里只是举个例子, 无论是变成情况 1~4 的哪种, 经过调整之后都无需再继续上溯, 因为此时黑色节点数目已经恢复, 且例子里面 GP 不是根节点, 因为根节点不可能为红色.
下面倒序总结一下
待删除的节点是黑色叶子 (非 Nil) 节点的情况
待删除的节点是红色叶子节点的情况
情况 6 直接删除该节点
待删除的节点只拥有左子树或只拥有右子树的情况
待删除的节点同时拥有左子树和右子树的情况
情况 9 找出直接后继节点并转变为情况 1~8
至此, 关于红黑树删除的所有情况均讨论完毕, 以上的每个字以及每个图都是自己写自己画的, 花了不少时间, 希望大家多看看, 结合图理解比较形象, 彻底搞懂红黑树的操作, 代码却是次要的, 因为同一种思路也有不同的代码风格和实现方式. 同时也希望这篇文章能对大家有帮助.
下面是删除的代码:
总的公共方法是这样的, 找到该元素对应的节点, 然后删除该节点:
- public boolean delete(int elem) {
- if (null == this.root) {
- return false;
- } else {
- TreeNode node = this.root;
- // find out the node need to be deleted
- while (null != node) {
- if (node.getElem() == elem) {
- deleteNode(node);
- return true;
- } else if (node.getElem()> elem) {
- node = node.getLeft();
- } else {
- node = node.getRight();
- }
- }
- return false;
- }
- }
- delete(int elem)
删除节点的方法为私有方法, 包含了同时拥有左右子树, 只拥有左子树以及只拥有右子树的操作
- private void deleteNode(TreeNode node) {
- if(null == node.getLeft() && null == node.getRight()) {
- if (node.getColor() == NodeColor.RED) {
- delete_red_leaf(node, true);
- } else {
- delete_black_leaf(node, true);
- }
- } else if (null == node.getLeft()) {
- // the node color must be black and the right child must be red node
- // replace the element of node with its right child's
- // cut off the the link between node and its right child
- node.setElem(node.getRight().getElem());
- node.setRight(null);
- } else if (null == node.getRight()) {
- node.setElem(node.getLeft().getElem());
- node.setLeft(null);
- } else {
- // both children are not null
- TreeNode next = node.getRight();
- while (null != next.getLeft()) {
- next = next.getLeft();
- }
- TreeUtils.swapTreeElem(node, next);
- deleteNode(next);
- }
- }
- private void deleteNode(TreeNode node)
由大及小, 删除的节点是红色叶子节点的情况, 注意此处待删除的节点肯定不是根节点, 所以不需要考虑该节点为根节点的情况
- private void delete_red_leaf(TreeNode node, boolean needDel) {
- TreeNode parent = node.getParent();
- if (node == parent.getLeft()) {
- parent.setLeft(null);
- } else {
- parent.setRight(null);
- }
- }
- private void delete_red_leaf(TreeNode node, boolean needDel)
最后就是最麻烦的删除的删除黑色叶子 (非 Nil) 节点的情况, 找出兄弟节点, 找出远侄子节点, 找出近侄子节点.
- private void delete_black_leaf(TreeNode node, boolean needDel) {
- TreeNode parent = node.getParent();
- if (null != parent) {
- boolean nodeInLeft = parent.getLeft() == node;
- TreeNode sibling = nodeInLeft ? parent.getRight() : parent.getLeft();
- TreeNode remoteNephew = null == sibling ? null : (nodeInLeft ? sibling.getRight() : sibling.getLeft());
- TreeNode nearNephew = null == sibling ? null : (nodeInLeft ? sibling.getLeft() : sibling.getRight());
- if (sibling.getColor() == NodeColor.RED) {
- delete_sibling_red(node);
- } else if (null != remoteNephew && remoteNephew.getColor() == NodeColor.RED) {
- delete_remote_nephew_red(node);
- } else if (null != nearNephew && remoteNephew.getColor() == NodeColor.RED) {
- delete_near_nephew_red(node);
- } else {
- // the sibling is also a leaf
- if (parent.getColor() == NodeColor.RED) {
- delete_parent_red(node);
- } else {
- sibling.setColor(NodeColor.RED);
- delete_black_leaf(parent, false);
- }
- }
- }
- if (needDel) {
- if (null == parent) {
- this.root = null;
- } else if (node.getParent().getLeft() == node) {
- parent.setLeft(null);
- } else {
- parent.setRight(null);
- }
- }
- }
- private void delete_black_leaf(TreeNode node, boolean needDel)
删除叶子节点包含了另外一个参数 boolean needDel , 因为上面提到的有些情况需要继续上溯, 所以有些节点不能被删除.
来源: https://www.cnblogs.com/GNLin0820/p/9668378.html