欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

红黑树java代码实现

程序员文章站 2024-02-05 15:28:10
红黑树 思想源于:https://www.cnblogs.com/nananana/p/10434549.html有解释有图,很清晰(删除时需考虑根节点和兄弟节点的子节点是否存在) package tree; import jdk.nashorn.internal.ir.CallNode; impo... ......
红黑树 思想源于:https://www.cnblogs.com/nananana/p/10434549.html
有解释有图,很清晰(删除时需考虑根节点和兄弟节点的子节点是否存在)
package tree;

import jdk.nashorn.internal.ir.callnode;

import java.util.random;

/**
 * 红黑树
 * 思想源于:https://www.cnblogs.com/nananana/p/10434549.html
 */
public class rbtree {
    private rbtree.node root = null;

    private enum color {red, black}

    private enum child {left, right}

    private class node {
        private integer key;    //key
        private object data;    //value
        private node leftchild;   //左子节点
        private node rightchild;  //右子节点
        private node parent;  //父节点
        private color color;   //红黑标示

        private node() {
        }

        node(object key, object data, color color) {
            this.key = (integer) key;
            this.data = data;
            this.color = color;
        }

        public color getcolor() {
            return color;
        }

        public void setcolor(color color) {
            this.color = color;
        }

        boolean isred() {
            if (this.color.equals(color.red))
                return true;
            return false;
        }
    }

    /**
     * 插入数据
     *
     * @param value 插入数据
     * @return 数据重复返回false
     */
    boolean insertnode(integer key, object value) {
        return insertnode(root, key, value, null, child.left);
    }

    private boolean insertnode(node node, integer key, object value, node prenode, child child) {
        if (node == null) {
            node = new node(key, value, color.red);
            if (prenode == null) {  //父节点为空,将node设为根节点
                root = node;
            } else {
                if (child.equals(child.left)) {
                    prenode.leftchild = node;
                } else {
                    prenode.rightchild = node;
                }
                node.parent = prenode;
            }

            //通过rb_insert_fixup对红黑树的结点进行颜色修改以及旋转,让树仍然是一颗红黑树
            rb_insert_fixup(node);
            return true;
        } else {
            if (key.compareto(node.key) == 0) {
                //root = node;
                return false;
            } else if (key.compareto(node.key) < 0) {
                if (!insertnode(node.leftchild, key, value, node, child.left)) {
                    return false;
                }
            } else {
                if (!insertnode(node.rightchild, key, value, node, child.right)) {
                    return false;
                }
            }
            return true;
        }
    }

    /**
     * @param node 插入节点
     */
    private void rb_insert_fixup(node node) {
        node pnode = node.parent;
        if (node == root) { //插入结点为跟节点,直接改变颜色
            node.setcolor(color.black);
            return;
        }
        if (node == null || pnode.color.equals(color.black)) {    //插入结点的父结点为黑结点,由于插入的结点是红色的,并不会影响红黑树的平衡,直接插入即可,无需做自平衡。
            return;
        } else {    //情景4:插入结点的父结点为红结点
            node granode = node.parent.parent;
            if (pnode == granode.leftchild) {  //父节点是祖父节点的左子节点
                if (granode.rightchild != null && granode.rightchild.isred()) { //情景4.1:叔叔结点存在并且为红结点
                    /*将p和s设置为黑色(当前插入结点i)将gra设置为红色 把gra设置为当前插入结点*/
                    pnode.setcolor(color.black);
                    granode.rightchild.setcolor(color.black);
                    granode.setcolor(color.red);
                    rb_insert_fixup(granode);
                } else { //情景4.2:叔叔结点不存在或为黑结点,并且插入结点的父亲结点是祖父结点的左子结点
                    if (node == pnode.leftchild) {//情景4.2.1 插入结点是其父结点的左子结点
                        /*将p设为黑色 将gra设为红色 对gra进行右旋*/
                        pnode.setcolor(color.black);
                        granode.setcolor(color.red);
                        rrotate(granode);
                    } else {    //情景4.2.2 插入结点是其父结点的右子结点
                        /*对p进行左旋 把p设置为插入结点,得到情景4.2.1 进行情景4.2.1的处理*/
                        lrotate(pnode);
                        rb_insert_fixup(pnode);
                    }

                }
            } else { //4.3 父节点是祖父节点的右子节点
                if (granode.leftchild != null && granode.leftchild.isred()) { //情景4.3:叔叔结点存在并且为红结点+
                    /*将p和s设置为黑色(当前插入结点i)将gra设置为红色 把gra设置为当前插入结点*/
                    pnode.setcolor(color.black);
                    granode.leftchild.setcolor(color.black);
                    granode.setcolor(color.red);
                    rb_insert_fixup(granode);
                } else { //情景4.3.1:叔叔结点不存在或为黑结点,并且插入结点的父亲结点是祖父结点的左子结点
                    if (node == pnode.rightchild) {//情景4.3.1:插入结点是其父结点的右子结点
                        /*将p设为黑色 将gra设为红色 对pp进行左旋*/
                        pnode.setcolor(color.black);
                        granode.setcolor(color.red);
                        lrotate(granode);
                    } else {    //情景4.3.2 插入结点是其父结点的右子结点
                        /*对p进行右旋 把p设置为插入结点,得到情景4.3.1 进行情景4.3.1的处理*/
                        rrotate(pnode);
                        rb_insert_fixup(pnode);
                    }
                }
            }
        }
    }

    /**
     * 右旋
     *
     * @param t
     */
    private void rrotate(node t) {
        node lc = t.leftchild;
        t.leftchild = lc.rightchild;
        if (t.leftchild != null) {
            t.leftchild.parent = t;
        }
        lc.rightchild = t;
        returnpnode(t, lc);
    }

    private node returnpnode(node t, node node) {
        if (t == root) {
            root = node;
        } else if (t.parent.leftchild == t) {
            t.parent.leftchild = node;
        } else {
            t.parent.rightchild = node;
        }
        node.parent = t.parent;
        t.parent = node;
        return node;
    }

    /**
     * 左旋
     *
     * @param t
     */
    private void lrotate(node t) {
        node rc = t.rightchild;
        t.rightchild = rc.leftchild;
        if (t.rightchild != null) {

            t.rightchild.parent = t;
        }
        rc.leftchild = t;
        returnpnode(t, rc);
    }

    /**
     * 中序
     */
    public void ldrtraversal() {
        ldrtraversal(root);
    }

    /**
     * 中序
     */
    private void ldrtraversal(node node) {
        if (node != null) {
            ldrtraversal(node.leftchild);
            system.out.print(node.key + ":" + node.color + ";");
            //system.out.print("key:" + node.key + "-value" + node.data + ":" + node.color + ";");
            ldrtraversal(node.rightchild);
        }

    }

    /**
     * 先序
     */
    public void dlrtraversal() {
        dlrtraversal(root);
    }

    /**
     * 先序
     */
    private void dlrtraversal(node node) {
        if (node != null) {
            system.out.print(node.key + ":" + node.color + ";");
            dlrtraversal(node.leftchild);
            dlrtraversal(node.rightchild);
        }

    }

    /**
     * 后序
     */
    public void lrdtraversal() {
        lrdtraversal(root);
    }

    /**
     * 后序
     */
    private void lrdtraversal(node node) {
        if (node != null) {
            lrdtraversal(node.leftchild);
            lrdtraversal(node.rightchild);
            system.out.print("key:" + node.key + "-value" + node.data + ":" + node.color + ";");
        }

    }

    /**
     * 搜索
     *
     * @param key 传入key
     * @return 返回value
     */
    public object search(integer key) {
        if (this.root != null) {
            return searchnode(key, root).data;
        }
        return null;
    }

    /**
     * @param key 删除key对应的node
     */
    public boolean removen(integer key) {
        if (this.root != null) {
            node node = searchnode(key, root);
            if (node == null) {
                return false;
            }
            removennode(node);
            return true;
        }
        return false;
    }

    /**
     * @param node 删除的节点
     */
    private void removennode(node node) {
        if (node == null) {
            return;
        }
        if (node.leftchild == null && node.rightchild == null) {    //情景1:若删除结点无子结点,直接删除。
            changenode(node, null);
        } else if (node.leftchild != null && node.rightchild != null) { //情景3:若删除结点有两个子结点,用后继结点(大于删除结点的最小结点)替换删除结点。
            node rnode = node.rightchild;
            while (rnode.leftchild != null) {   //找到后继结点
                rnode = rnode.leftchild;
            }
            //  交换位子
            /*if (rnode == node.rightchild) {
                node.rightchild = null;
                rnode.leftchild = node.leftchild;
            } else {
                if (rnode.rightchild != null) {    //后继节点如果有右节点
                    rnode.parent.leftchild = rnode.rightchild;
                    rnode.rightchild.parent = rnode.parent;
                }
                rnode.leftchild = node.leftchild;
                rnode.rightchild = node.rightchild;
            }*/
            changenode(node, rnode);    //用后继节点替换要删除节点
        } else { //情景2:若删除结点只有一个子结点,用子结点替换删除结点。
            if (node.leftchild != null) {
                changenode(node, node.leftchild);
            } else {
                changenode(node, node.rightchild);
            }
        }
    }

    /**
     * 两节点位置交换
     * 交换后删除替换节点fixupnode
     * @param delnode   要删除节点
     * @param fixupnode 替换节点
     */
    private void changenode(node delnode, node fixupnode) {
        rb_delete_fixup(fixupnode);

        if (fixupnode == null) {
            if (delnode.parent.leftchild == delnode) {
                delnode.parent.leftchild = null;
            } else {
                delnode.parent.rightchild = null;
            }
            return;
        }

        object data = delnode.data;
        color color = delnode.color;
        integer key = delnode.key;
        if (delnode == root) {  // 交换时如果删除节点是根节点,颜色直接改成黑色
            delnode.setcolor(color.black);
        } else {
            delnode.color = fixupnode.color;
        }
        delnode.key = fixupnode.key;
        delnode.data = fixupnode.data;
        fixupnode.key = key;
        fixupnode.data = data;
        fixupnode.color = color;

        removennode(fixupnode);
    }

    public node searchnode(integer key, node node) {
        if (node == null)
            return null;
        if (node.key.compareto(key) == 0) {
            return node;
        } else if (key.compareto(node.key) < 0) {
            if (node.leftchild != null) {
                return searchnode(key, node.leftchild);
            }
            return null;
        } else {
            if (node.rightchild != null) {
                return searchnode(key, node.rightchild);
            }
            return null;
        }
    }

    private void rb_delete_fixup(node fixupnode) {
        if (fixupnode == null || fixupnode.isred()) {    //情景1:替换结点是红色结点
            /*颜色变为删除结点的颜色*/
            return;
        } else {  //情景2:替换结点是黑结点
            node bnode = fixupnode.parent.rightchild;
            if (fixupnode == fixupnode.parent.leftchild) { //情景2.1:替换结点是其父结点的左子结点
                //情景2.1.1:替换结点的兄弟结点是红结点
                if (bnode.isred()) {
                    bnode.setcolor(color.black);
                    fixupnode.parent.setcolor(color.red);
                    rrotate(fixupnode.parent);
                    rb_delete_fixup(fixupnode);
                } else {  //情景2.1.2: 替换结点的兄弟结点是黑结点
                    //情景2.1.2.1:替换结点的兄弟结点的右子结点是红结点,左子结点任意颜色
                    if (bnode.rightchild != null && bnode.rightchild.isred()) {
                        /*将s的颜色设为p的颜色 将p设为黑色 将sr设为黑色 对p进行左旋*/
                        bnode.color = fixupnode.parent.color;
                        fixupnode.parent.setcolor(color.black);
                        bnode.rightchild.setcolor(color.red);
                        lrotate(fixupnode.parent);
                    } else if (bnode.leftchild != null && bnode.leftchild.isred()) {
                        //情景2.1.2.2:替换结点的兄弟结点的右子结点为黑结点,左子结点为红结点
                        /*将s设为红色 将sl设为黑色 对s进行右旋,得到情景2.1.2.1 进行情景2.1.2.1的处理*/
                        bnode.setcolor(color.red);
                        bnode.leftchild.setcolor(color.black);
                        rrotate(bnode);
                        rb_delete_fixup(fixupnode);
                    } else {//删除情景2.1.2.3: 替换结点的兄弟结点的子结点都为黑结点
                        /*将s设为红色 把p作为新的替换结点 重新进行删除结点情景处理*/
                        bnode.setcolor(color.red);
                        rb_delete_fixup(fixupnode.parent);
                    }

                }
            } else {
                //删除情景2.2: 替换结点是其父结点的右子结点
                //删除情景2.2.1: 替换结点的兄弟结点是红结点
                if (bnode.isred()) {
                    /*将s设为黑色 将p设为红色 对p进行右旋,得到情景2.2.2.3 进行情景2.2.2.3的处理*/
                    bnode.setcolor(color.black);
                    fixupnode.parent.setcolor(color.red);
                    lrotate(fixupnode.parent);
                    rb_delete_fixup(fixupnode);
                } else { //删除情景2.2.2: 替换结点的兄弟结点是黑结点
                    //删除情景2.2.2.1: 替换结点的兄弟结点的左子结点是红结点,右子结点任意颜色
                    if (bnode.leftchild != null && bnode.leftchild.isred()) {
                        /*将s的颜色设为p的颜色 将p设为黑色 将sl设为黑色 对p进行右旋*/
                        bnode.color = fixupnode.parent.color;
                        fixupnode.parent.setcolor(color.black);
                        bnode.leftchild.setcolor(color.black);
                        rrotate(fixupnode.parent);
                    } else if (bnode.rightchild != null && bnode.rightchild.isred()) {//删除情景2.2.2.2: 替换结点的兄弟结点的左子结点为黑结点,右子结点为红结点
                        /*将s设为红色 将sr设为黑色 对s进行左旋,得到情景2.2.2.1 进行情景2.2.2.1的处理*/
                        bnode.setcolor(color.red);
                        bnode.rightchild.setcolor(color.black);
                        lrotate(bnode);
                        rb_delete_fixup(fixupnode);
                    } else {//删除情景2.2.2.3:替换结点的兄弟结点的子结点都为黑结点
                        /*将s设为红色 把p作为新的替换结点 重新进行删除结点情景处理*/
                        bnode.setcolor(color.red);
                        rb_delete_fixup(fixupnode.parent);
                    }
                }
            }
        }
    }

    public static void main(string[] args) {
        //int[] data={8,6,4};
        //int[] data={8,6,9,5,7,3};
        //int[] data={8,6,7};
        //int[] data={8,5,9,4,6,7};
        //int[] data={8,5,9,4,7,6};
        //int[] data = {8, 5, 9, 7, 6};
        //object[] data = new object[100];
        //object[] data = {2, 4, 15, 11, 19, 3, "f", "g", "b", "a", "d", "c", "e", new person("小王", 22)};
        /*for (int i = 0; i < 100; i++) {
            random r = new random();
            int n = r.nextint(100);
            data[i] = "数据" + n;
            //system.out.println(n);
        }*/
        rbtree rbt = new rbtree();
        int[] data = {2, 4, 15, 11, 19, 3, 12, 14, 16, 9, 13, 17, 7, 8, 5, 1, 18, 6};
        for (int i = 0; i < data.length; i++) {
            if (data[i] == 9) {
                system.out.println();
            }
            system.out.println(data[i]);
            rbt.insertnode(data[i], data[i]);
            rbt.dlrtraversal();
            system.out.println("\n" + rbt.root.data);
        }
        rbt.removen(6);
        /*for (int i = 0; i < data.length; i++) {
            rbt.insertnode(string.valueof(i), data[i]);
        }*/
        rbt.ldrtraversal();
        system.out.println("\n" + rbt.root.data);
        rbt.dlrtraversal();
        //system.out.println("\n" + rbt.search("0"));
    }
}