• 周一. 5月 27th, 2024

5G编程聚合网

5G时代下一个聚合的编程学习网

热门标签

JAVA实现红黑树的删除

admin

11月 28, 2021

背景:自学红黑树
开发语言:JAVA
本片内容:用java实现红黑树的删除

红黑树的由来(节选自百度百科)

   红黑树是在1972年由Rudolf Bayer发明的,当时被称为平衡二叉B树(symmetric binary B-trees)。后来,在1978年被 Leo J. Guibas 和 Robert Sedgewick 修改为如今的“红黑树”。
   红黑树是一种特化的AVL树(平衡二叉树),都是在进行插入和删除操作时通过特定操作保持二叉查找树的平衡,从而获得较高的查找性能。
   它虽然是复杂的,但它的最坏情况运行时间也是非常良好的,并且在实践中是高效的: 它可以在O(log n)时间内做查找,插入和删除,这里的n 是树中元素的数目。

红黑树与AVL树的使用区别

增加和删除,红黑树效率高;查询,AVL树效率高

红黑树的特性

1、每个节点的颜色是红色或者黑色
2、根节点是黑色
3、空叶子节点是黑色
4、红色节点的子节点一定是黑色
5、从任意节点开始到叶子节点结束,所经过的黑色节点个数一定是相同的

用代码实现红黑树的删除

红黑树节点代码

package com.blueice.hello.BRTree;

/**
 * @FileName: BRNode
 * @Description: TODO(红黑树节点)
 * @Author: shaoz
 * @Date: 2021/7/8 10:43
 * @Copyright: 2021 www.***.com.cn  All rights reserved.
 * 注意:本内容仅限于***内部传阅,禁止外泄以及用于其他的商业目的
 */

public class BRNode {

    BRNode parent;

    TreeColor treeColor;

    BRNode left;

    BRNode right;

    int value;

    public BRNode(int value) {
        this.value = value;
        this.parent = null;
        this.left = null;
        this.right = null;
        this.treeColor = TreeColor.RED;
    }
}

红黑树的颜色

package com.blueice.hello.BRTree;

/**
 * @FileName: TreeColor
 * @Description: TODO(红黑树的颜色)
 * @Author: shaoz
 * @Date: 2021/7/8 15:23
 * @Copyright: 2021 www.***.com.cn  All rights reserved.
 * 注意:本内容仅限于***内部传阅,禁止外泄以及用于其他的商业目的
 */

public enum TreeColor {
    /**
     * 红黑树的颜色
     */

    BLACK("黑色"),RED("红色");

    private String color;

    TreeColor(String color) {
        this.color = color;
    }

    public String getColor() {
        return color;
    }
}

红黑树的删除

package com.blueice.hello.BRTree;

/**
 * @FileName: BRTree
 * @Description: TODO(红黑树)
 * @Author: shaoz
 * @Date: 2021/7/8 11:14
 * @Copyright: 2021 www.***.com.cn  All rights reserved.
 * 注意:本内容仅限于***内部传阅,禁止外泄以及用于其他的商业目的
 */

public class BRTree {

    BRNode root;

    public BRTree(int value) {
        this.root = new BRNode(value);
        this.root.treeColor = TreeColor.BLACK;
    }
    /**
     * 删除红黑树中的值
     * @param value 要删除的值
     */

    public void remove(int value) {
        BRNode curNode = root;
        while (curNode != null) {
            if (value == curNode.value) {
                removeNode(curNode);
                break;
            } else if (value > curNode.value) {
                curNode = curNode.right;
            } else {
                curNode = curNode.left;
            }
        }
    }

    /**
     * 删除节点
     * @param curNode 要删除的节点
     */

    private void removeNode(BRNode curNode) {
        /* 删除节点后的替换节点 */
        BRNode replaceNode = null;

        /* 有2个子节点:找到后继节点,继续递归(只会递归一次,因为后继节点肯定没有两个非空子节点) */
        if (null != curNode.left && null != curNode.right) {
            for (replaceNode = curNode.right; null != replaceNode.left; replaceNode = replaceNode.left){};        
            curNode.value = replaceNode.value;
            removeNode(replaceNode);
        /* 没有子节点 */
        } else if (null == curNode.left && null == curNode.right) {
            /* 当前节点是根节点,直接把红黑树置空 */
            if (null == curNode.parent) {
                this.root = null;
                return;
            }
            /* 当前节点颜色为红色:直接删除 */
            if (TreeColor.RED == curNode.treeColor) {
                if (curNode == curNode.parent.left) {
                    curNode.parent.left = null;
                } else {
                    curNode.parent.right = null;
                }
            /* 当前节点为黑色,进行删除平衡操作 */
            } else {
                /* 删掉当前节点 */
                BRNode parNode = curNode.parent;
                BRNode broNode;
                if (curNode == parNode.left) {
                    parNode.left = null;
                    broNode = parNode.right;
                } else {
                    parNode.right = null;
                    broNode = parNode.left;
                }
                /* 进行删除平衡操作 */
                removeFixUp(parNode, broNode);
            }
        /* 有1个子节点:一定是黑-红,删掉当前节点,把红色子节点放到当前位置,并染为黑色 */
        } else {
            BRNode curParent = curNode.parent;
            BRNode sonNode;
            if (null != curNode.left) {
                sonNode = curNode.left;
            } else {
                sonNode = curNode.right;
            }
            sonNode.parent = curParent;
            if (null != curParent) {
                if (curNode == curParent.left) {
                    curParent.left = sonNode;
                } else {
                    curParent.right = sonNode;
                }
            } else {
                sonNode.treeColor = TreeColor.BLACK;
                this.root = sonNode;
            }
            sonNode.treeColor = TreeColor.BLACK;        
        }
    }

    /**
     * 红黑树删除平衡操作(被删除节点为黑色,并且子节点全为NIL)
     * @param parNode 父节点
     * @param broNode 兄弟节点
     */

    private void removeFixUp(BRNode parNode, BRNode broNode) {
        /*   <1> 当前节点为根节点
        //   <2> 兄弟节点是黑色
        //     [1] 兄子节点全为NIL(全黑)
        //       {1} 父红
        //       {2} 父黑
        //     [2] 兄子节点不全黑
        //       {1} 兄在左,兄左子节点红色
        //       {2} 兄在右,兄右子节点红色
        //       {3} 兄在左,兄左子节点黑色
        //       {4} 兄在右,兄右子节点黑色
        //   <3> 兄弟节点是红色
        //     [1] 兄在左
        //     [2] 兄在右 */


        /* <1>当前节点是根节点 */
        if (null == parNode) {
            return;
        /* <2>兄弟节点是黑色 */
        } else if (TreeColor.BLACK == broNode.treeColor) {
            /* <2.1>兄弟节点的子节点全为NIL或者全为黑色 */
            if ((null == broNode.left && null == broNode.right) 
                    || (broNode.left != null && TreeColor.BLACK ==broNode.left.treeColor && broNode.right != null && TreeColor.BLACK ==broNode.right.treeColor)) {
                /* <2.1.1>父节点是红色节点 */
                if (TreeColor.RED == parNode.treeColor) {
                    /* 交换父亲节点与兄弟节点颜色,平衡结束。 */
                    broNode.treeColor = TreeColor.RED;
                    parNode.treeColor = TreeColor.BLACK;
                /* <2.1.2>父节点是黑色节点 */    
                } else {
                    /* 把兄弟节点涂红 */
                    broNode.treeColor = TreeColor.RED;
                    /* 把父节点作为平衡节点继续递归处理 */ 
                    BRNode tempParNode = parNode;
                    parNode = parNode.parent;
                    broNode = parNode==tempParNode.left ? tempParNode.right : tempParNode.left;
                    removeFixUp(parNode, broNode);
                }
            /* <2.2>兄弟节点的子节点不全为黑色节点 */
            } else {
                /* <2.2.1>(1)兄弟节点为左子节点,兄弟节点的左子节点为红色 
                if (broNode == parNode.left && null != broNode.left && TreeColor.RED == broNode.left.treeColor) {
                    /* 以P为支点右旋;交换P和B颜色,BL涂黑;平衡结束。 */

                    TreeColor curColor = parNode.treeColor;
                    parNode.treeColor = broNode.treeColor;
                    broNode.treeColor = curColor;
                    broNode.left.treeColor = TreeColor.BLACK;
                    rightHand(parNode, broNode);
                /* <2.2.1>(2)兄弟节点为右子节点,兄弟节点的右子节点为红色 */
                } else if(broNode == parNode.right && null != broNode.right && TreeColor.RED == broNode.right.treeColor) {
                    /* 以P为支点左旋,交换P和B颜色,BR涂黑,平衡结束。 */
                    TreeColor curColor = parNode.treeColor;
                    parNode.treeColor = broNode.treeColor;
                    broNode.treeColor = curColor;
                    broNode.right.treeColor = TreeColor.BLACK;
                    leftHand(parNode, broNode);
                /* <2.2.2>(1)兄弟节点为左子节点,兄弟节点的左子节点为黑色 */
                } else if (broNode == parNode.left && null != broNode.left && TreeColor.BLACK == broNode.left.treeColor) {
                    /* 以B为支点左旋,交换B和BR颜色 */
                    TreeColor broColor = broNode.treeColor;
                    broNode.treeColor = broNode.right.treeColor;
                    broNode.right.treeColor = broColor;
                    leftHand(broNode, broNode.right);

                    /* 转至2.2.1-(1) */
                    removeFixUp(parNode, broNode.right);
                /* <2.2.2>(2)兄弟节点为右子节点,兄弟节点的右子节点为黑色 */        
                } else if (broNode == parNode.right && null != broNode.right && TreeColor.BLACK == broNode.right.treeColor) {
                    /* 以B为支点右旋,交换B和BL颜色 */
                    TreeColor broColor = broNode.treeColor;
                    broNode.treeColor = broNode.left.treeColor;
                    broNode.left.treeColor = broColor;
                    rightHand(broNode, broNode.left);

                    /* 转至2.2.1-(2) */
                    removeFixUp(parNode, broNode.left);
                }
            }
        /* <3>兄弟节点为红色 */
        } else if (TreeColor.RED == broNode.treeColor) {
            /* <3.1>兄弟节点为左子节点 */
            if (broNode == parNode.left) {
                /* 以P为支点右旋,交换P和B颜色,转向情形<2>兄黑 */
                TreeColor broColor = parNode.treeColor;
                parNode.treeColor = broNode.treeColor;
                broNode.treeColor = broColor;
                rightHand(parNode, broNode);
                removeFixUp(parNode, broNode.right);
            /* <3.2>兄弟节点为右子节点 */
            } else if (broNode == parNode.right) {
                /* 以P为支点左旋,交换P和B颜色,转向情形<2>兄黑 */
                TreeColor broColor = parNode.treeColor;
                parNode.treeColor = broNode.treeColor;
                broNode.treeColor = broColor;
                leftHand(parNode, broNode);
                removeFixUp(parNode, broNode.left);
            }
        }
    }
    /**
     * 左旋
     * @param parent 父节点
     * @param current 中间节点
     */

    private void leftHand(BRNode parent, BRNode current) {
        BRNode grandPa = parent.parent;
        if (grandPa != null) {
            if (grandPa.left == parent) {
                grandPa.left = current;
            } else {
                grandPa.right = current;
            }
        }
        parent.parent = current;
        parent.right = current.left;
        current.left.parent = parent;

        current.parent = grandPa;
        current.left = parent;
    }

    /**
     * 右旋
     * @param parent 父节点
     * @param current 中间节点
     */

    private void rightHand(BRNode parent, BRNode current) {
        BRNode grandPa = parent.parent;
        if (grandPa != null) {
            if (grandPa.left == parent) {
                grandPa.left = current;
            } else {
                grandPa.right = current;
            }
        }
        parent.parent = current;
        parent.left = current.right;
        current.right.parent = parent;

        current.parent = grandPa;
        current.right = parent;
    }

}

图例还在写,添加的代码下次上传,因为是先学的添加,后学的删除,现在添加方法已经模糊了。。。

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注