红黑树之左右旋转

/**
 * @author klr
 * @create 2020-08-29-21:58
 */
public class RedBlackTree {
    //定义红黑色
    private static final boolean RED = false;
    private static final boolean BLACK = true;

    //定义根节点
    private RBNode root;

    public RBNode getRoot() {
        return root;
    }

    /**
     * 围绕p点左旋
     *              pf                  pf
     *            /                   /
     *          p                   pr(r)
     *        /  \                 /  \
     *      pl    pr(r)           p     rr
     *          /   \           /  \
     *         rl   rr         pl   rl
     *
     * @param p
     */
    public void leftRotate(RBNode p) {
        if (p != null) {
            RBNode r = p.right;//先记录r的信息

            p.right = r.left;//r.left为不为null无所谓
            if (r.left != null) {
                r.left.parent = p;//rl的父节点指向p了
            }

            r.parent = p.parent;
            if (p.parent == null) {
                //此时表明p为根节点，旋转后，r称为根节点}
                root = r;
            } else if (p.parent.left == p) {
                //说明p为pf的左节点
                p.parent.left = r;//把pf指向r
            } else {
                p.parent.right = r;
            }
            r.left = p;
            p.parent = r;
        }
    }

    /**
     * 右旋为左旋的镜像
     * @param p
     */
    public void rightRotate(RBNode p) {
        if (p != null) {
            RBNode l = p.left;//先记录r的信息

            p.left = l.right;//r.left为不为null无所谓
            if (l.right != null) {
                l.right.parent = p;//rl的父节点指向p了
            }

            l.parent = p.parent;
            if (p.parent == null) {
                //此时表明p为根节点，旋转后，r称为根节点}
                root = l;
            } else if (p.parent.right == p) {
                //说明p为pf的左节点
                p.parent.right = l;//把pf指向r
            } else {
                p.parent.left = l;
            }
            l.right = p;
            p.parent = l;
        }
    }
    

    static class RBNode<K extends Comparable<K>, V>{
        private RBNode parent;
        private RBNode left;
        private RBNode right;
        private boolean color;
        private K key;
        private V value;

        public RBNode() {
        }

        public RBNode(RBNode parent, RBNode left, RBNode right, boolean color, K key, V value) {
            this.parent = parent;
            this.left = left;
            this.right = right;
            this.color = color;
            this.key = key;
            this.value = value;
        }

        public RBNode getParent() {
            return parent;
        }

        public void setParent(RBNode parent) {
            this.parent = parent;
        }

        public RBNode getLeft() {
            return left;
        }

        public void setLeft(RBNode left) {
            this.left = left;
        }

        public RBNode getRight() {
            return right;
        }

        public void setRight(RBNode right) {
            this.right = right;
        }

        public boolean isColor() {
            return color;
        }

        public void setColor(boolean color) {
            this.color = color;
        }

        public K getKey() {
            return key;
        }

        public void setKey(K key) {
            this.key = key;
        }

        public V getValue() {
            return value;
        }

        public void setValue(V value) {
            this.value = value;
        }
    }

}