红黑树java代码记录

不念不忘少年蓝@ 2022-12-13 01:21 88阅读 0赞

2020-10-08目前代码只记录了插入过程和插入之后的恢复过程代码，删除过程代码还在整理.

package com.lsx.tree;
    
    public class RedBlackTree {
    
        //红色，默认用红色
        private final int R = 0;
        //黑色
        private final int B = 1;
    
        private Node root = null; // 红黑树的根节点
    
        class Node {
            //存储数据
            int data;
            //颜色
            int color = R;
            //左
            Node left;
            //右
            Node right;
            //父节点
            Node parent;
    
            public Node(int data) {
                this.data = data;
            }
        }
    
        /**
         * 插入数据
         *
         * @param newNode
         */
        public void inset(Node newNode) {
            Node r = this.root;
            //新节点的父节点
            Node py = null;
            //定位新节点要插入到那个位置
            while (r != null) {
                //存储找到了位置的父节点信息
                py = r;
                if (r.data < newNode.data) {
                    r = r.right;
                } else if (r.data > newNode.data) {
                    r = r.left;
                } else {
                    //节点值相等，替新出的节点替换掉老的节点，为啥：如果节点值是一个对象，
                    // 如果使用ID来判断对象是否是同一个的时候，可能对象某个数据发生了变化。
                    if (r.parent == null) {
                        this.root = newNode;
                    } else {
                        if (r.parent.left == r) {
                            r.parent.left = newNode;
                        } else {
                            r.parent.right = newNode;
                        }
                        r = null;
                        newNode.parent = r.parent;
                    }
                    return;
                }
            }
            newNode.parent = py;
            if (py != null) {
                if (py.data < newNode.data) {
                    py.right = newNode;
                } else {
                    py.left = newNode;
                }
            }
            //插入的新节点默认是红色。
            //修正为一颗二叉查找树
            insertFixUp(newNode);
    
    
        }
    
        /**
         * 修正为一颗红黑树，节点插入正确位置之后，需要把树进行整理
         * 1.变色
         * 2.看看要怎么旋转
         *
         * @param newNode
         */
        private void insertFixUp(Node newNode) {
            Node parent, gparent;
            //诺父节点存在，并且父节点的颜色都是红色.
            //如果父节点是黑色，则不用修正
            while ((parent = newNode.parent) != null && isRed(parent)) {
                //获取祖父结点
                gparent = parent.parent;
                //检查父节点是左子树还是右子树
                if (gparent.left == parent) {
                    //父节点是左子树
                    // Case 1条件：叔叔节点是红色
                    //        黑
                    //  红(p)     红（u）
                    //红
                    Node uncle = gparent.right;
                    //case 1
                    if (uncle != null && isRed(uncle)) {
                        setBlack(uncle);
                        setBlack(parent);
                        setRead(gparent);
                        newNode = gparent;
                        continue;
                    }
                    //case 2
                    // 此时uncle是null或者颜色是黑色（null也是黑色），且当前插入节点是右孩子，
                    //旋转成插入节点在父节点的左边，形成pg ->p->newnode都是在左边
                    if (parent.right == newNode) {
                        leftRotate2(parent);
                        Node tmp;
                        //旋转完成之后，把newNode的引用改成parent
                        tmp = parent;
                        parent = newNode;
                        newNode = tmp;
                    }
                    //case 2.1
                    //叔叔全是黑色，当前节点是左孩子，进行一下右旋
                    setRead(gparent);
                    setBlack(parent);
                    rightRotate2(gparent);
                    //处理完这个之后，while会在isRed(parent)不成立而结束循环
                } else {
                    //右子树
                    // Case 1条件：叔叔节点是红色
                    //        黑
                    //  红(u)     红（p）
                    //红
                    Node uncle = gparent.left;
                    //caes 1
                    if (uncle != null && isRed(uncle)) {
                        //变色
                        setBlack(uncle);
                        setBlack(parent);
                        setRead(gparent);
                        newNode = gparent;
                        continue;
                    }
                    //case 2
                    //此时uncle是null或者颜色是黑色（null也是黑色）
                    //线程pg -p->newNode都是在右边
                    if (parent.left == newNode) {
                        //旋转成插入节点在父节点的左边
                        rightRotate2(parent);
                        Node tmp;
                        //旋转完成之后，把newNode的引用改成parent
                        tmp = parent;
                        parent = newNode;
                        newNode = tmp;
                    }
                    //case 2.1
                    setRead(gparent);
                    setBlack(parent);
                    rightRotate2(gparent);
                    //处理完这个之后，while会在isRed(parent)不成立而结束循环
                }
            }
            //这行代码处理的是树为空的时候，插入的第一个节点
            setBlack(this.root);
    
        }
    
        /**
         * 单独写出来是方便后期如果01表示的含义不是红黑，好方便修改
         *
         * @param node
         * @return
         */
        private boolean isRed(Node node) {
            return node.color == R;
        }
    
        private void setRead(Node node) {
            node.color = R;
        }
    
        private void setBlack(Node node) {
            node.color = B;
        }
    
        /*
         * 对红黑树的节点(x)进行左旋转
         *
         * 左旋示意图(对节点x进行左旋)：
         *      px                              px
         *     /                               /
         *    x                               y
         *   /  \      --(左旋)-.           / \                #
         *  lx   y                         x   ry
         *     /   \                       /   \
         *    ly   ry                     lx   ly
         *
         *
         */
        public void leftRotate2(Node node) {
            //获取它的右边节点
            Node y = node.right;
            //新数据，把y的左节点处理
            node.right = y.left;
            if (y.left != null) {
                y.left.parent = node;
            }
            //处理node节点的父节点
            if (node.parent.left == node) {
                //当前node节点是左边的
                node.parent.left = y;
            } else if (node.parent.right == node) {
                //右边的
                node.parent.right = y;
            } else {
                //如果父节点是空，就把新的根节点设置为树的根节点
                root = y;
            }
    
            //处理y节点
            y.left = node;
            node.parent = y;
        }
    
        /*
         * 对红黑树的节点(y)进行右旋转
         *
         * 右旋示意图(对节点y进行左旋)：
         *            py                               py
         *           /                                /
         *           y                               x
         *         /  \      --(右旋)-.            /   \
         *        x   ry                          lx    y
         *       / \                                   / \
         *      lx  rx                                rx  ry
         *
         */
        public void rightRotate2(Node node) {
            Node x = node.left;
            node.left = x.right;
            if (x.right != null) {
                node.left.parent = node;
            }
            if (node.parent.left != null) {
                node.parent.left = x;
            } else if (node.parent.right != null) {
                node.parent.right = x;
            } else {
                root = x;
            }
            x.right = node;
            node.parent = x;
        }
    
    
    }