[数据结构与算法]手撕红黑树-java版

手撕红黑树-java版

红黑树的五个平衡条件

1. 每个节点非黑即红
2. 根节点是黑色
3. 叶节点（即虚拟叶节点，红黑树中的叶节点指的是看不见的虚拟空节点）是黑色
4. 如果一个节点是红色，则它的两个子节点都是黑色的
5. 从根节点出发到所有叶节点路径上，黑色节点数量相同

红黑树最长路径是最短路径的2倍

相比于AVL树，红黑树的控制条件更加松散，为了降低在插入和删除节点后的调整次数

红黑树自平衡的三种依据

1. 变色：节点的颜色由黑变红或者由红变黑
2. 左旋：已某一节点作为支点（旋转节点），其右子节点变为旋转节点的父节点，右子节点的左节点变为旋转节点的右子节点，左子节点保存不变
3. 右旋：已某一节点作为支点（旋转节点），其左子节点变为旋转节点的父节点，左子节点的右节点变为旋转节点的左子节点，右 子节点保存不变

调整策略

1. 插入调整从祖父节点向下观察，若父节点与子节点出现问题才需要调整
2. 删除节点从父节点向下观察

插入的情况

插入黑色节点，必然会调整，插入红色节点，可能会调整

所以红黑树在插入时为红色节点

情况一

当回溯到15节点时发现20节点与子节点发送冲突，这时需要调整

使用红黑黑结构代替当前的黑红红结构

这部分调整之前每条路径上黑色节点的数量，应该等于调整之后黑色节点的数量 这时调整之后对红黑树整体不受影响

处理办法：将1和20修改为黑色，15修改为红色

情况二

从20节点向下看发现20的左子节点（15）为红色，15的左子节点（10）也为红色

处理方法：将20调整为红色，15调整为黑色，从20进行右旋

或者将10改为黑色 两种方案

插入代码实现

定义的树中，为了方便实现直接使用了compareTo比较key大小，建议使用"a,b,c,d…"来排序

红黑树结构和方法定义

package RBTree;

//红黑树
public class RBTree<K extends Comparable<K>,V> {
    private static final boolean RED = true;
    private static final boolean BLACK = false;

    private RBNode root;//树根

    public RBNode getRoot() {
        return root;
    }

    public void setRoot(RBNode root) {
        this.root = root;
    }

    /**
     * 获取当前节点的父节点
     * @param node
     * @return
     */
    private RBNode parentOf(RBNode node) {
        if (node != null) {
            return node.parent;
        }
        return null;
    }

    /**
     * 节点是否为红色
     * @param node
     * @return
     */
    private boolean isRed(RBNode node) {
        if (node != null) {
            return node.color == RED;
        }
        return false;
    }

    /**
     * 设置节点为红色
     * @param node
     */
    private void setRed(RBNode node) {
        if (node != null) {
            node.color = RED;
        }
    }

    /**
     * 节点是否为黑色
     * @param node
     * @return
     */
    private boolean isBlack(RBNode node) {
        if (node != null) {
            return node.color == BLACK;
        }
        return false;
    }

    /**
     * 设置节点为黑色
     * @param node
     */
    private void setBlack(RBNode node) {
        if (node != null) {
            node.color = BLACK;
        }
    }

    /**
     * 中序打印
     */
    public void inOrderPrint() {
        inOrderPrint(this.root);
    }

    public void inOrderPrint(RBNode node) {
        if (node != null) {
            inOrderPrint(node.left);
            System.out.println("key: " + node.key + "value: " + node.value);
            inOrderPrint(node.right);
        }
    }

    /**
     * 对外公开的插入方法
     * @param key
     * @param value
     */
    public void insert(K key, V value) {
        RBNode node = new RBNode();
        node.setKey(key);
        node.setValue(value);
        //新节点一定是红色
        node.setColor(RED);
        insert(node);
    }

    /**
     * 实际的插入方法
     * @param node
     */
    private void insert(RBNode node) {
        //1、查找当前node的父节点
        RBNode parent = null;
        RBNode x = this.root;

        while (x != null) {
            parent = x;

            //compareTo > 0 说明node.key 大于 x.key 需要到x的右子树查找
            //compareTo = 0 说明node.key 等于 x.key 需要进行替换操作
            //compareTo < 0 说明node.key 小于 x.key 需要到x的左子树查找
            int compareTo = node.key.compareTo(x.key);
            if (compareTo > 0) {
                x = x.right;
            } else if (compareTo == 0) {
                x.setValue(node.getValue());
                return;
            } else {
                x = x.left;
            }
        }
        //得到node的parent节点
        node.parent = parent;
        //判断node与parent的key大小
        if (parent != null) {
            int compareTo = node.key.compareTo(parent.key);
            if (compareTo > 0) {
                parent.right = node;
            } else {
                parent.left = node;
            }
        } else{
            this.root = node;
        }

        //调用红黑树平衡的方法
        insertFixUp(node);
    }


    /**
     * 插入后修复红黑树的方法
     *
     * 情景1：红黑树为空树，将根节点变为黑色
     * 情景2：插入节点的key已经存在，在之前已经处理过，无需再处理
     * 情景3：插入节点的父节点为黑色，没有改变红黑树，不需要处理
     *
     * 情景4：插入节点父节点为红色
     *      1：叔叔节点存在，并且为红色（情景1）将爸爸节点和叔叔节点染色为黑色，爷爷节点染色为红色，并且已爷爷节点再次处理
     *      2：叔叔节点不存在，或者为黑色 父节点为爷爷节点的左子树 （情况2 调整为LL双红）
     *          若直接为LL将父节点改为黑色，爷爷节点改为红色 将爷爷节点作为旋转节点右旋
     *          若为LR情况 先已父节点为旋转节点左旋，并且已爸爸节点再次处理
     *      3：叔叔节点不存在，或者为黑色 父节点为爷爷节点的右子树 （参考情况2 RR双红）
     *          若直接为RR将父节点改为黑色，爷爷节点改为红色 将爷爷节点作为旋转节点左旋
     *          若为RL情况 先已父节点为旋转节点右旋，并且已爸爸节点再次处理
     *
     */
    private void insertFixUp(RBNode node) {
        this.root.setColor(BLACK);
        RBNode parent = parentOf(node);//父节点
        RBNode gParent = parentOf(parent);//爷爷节点

        //情景4
        if (parent != null && isRed(parent)) {
            RBNode uncle = null;//叔叔节点
            //若父节点为爷爷节点的左节点 则叔叔节点为右节点
            if (parent == gParent.left) {
                uncle = gParent.right;

                //4.1叔叔节点存在，并且为红色（情景1）将爸爸节点和叔叔节点染色为黑色，爷爷节点染色为红色，并且已爷爷节点再次处理
                if (uncle != null && isRed(uncle)) {
                    setBlack(parent);
                    setBlack(uncle);
                    setBlack(gParent);
                    insertFixUp(gParent);
                    return;
                }

                //4.2 叔叔节点不存在或者为黑色
                if (uncle == null || isBlack(uncle)) {

                    if (node == parent.left) {//LL双红  将父节点改为黑色，爷爷节点改为红色 将爷爷节点作为旋转节点右旋
                        setBlack(parent);
                        setRed(gParent);
                        rightRotate(gParent);
                        return;
                    }
                    if (node == parent.right) { //LR情况
                        leftRotate(parent);
                        insertFixUp(parent);
                        return;
                    }
                }
            } else { //父节点为爷爷节点的右子树
                uncle = gParent.left;
                if (uncle != null && isRed(uncle)) { //叔父双红
                    setBlack(parent);
                    setBlack(uncle);
                    setBlack(gParent);
                    insertFixUp(gParent);
                    return;
                }

                if (uncle == null || isBlack(uncle)) {
                    if (node == parent.right) { //RR
                        setBlack(parent);
                        setRed(gParent);
                        leftRotate(gParent);
                        return;
                    }
                    if (node == parent.left) { //RL
                        rightRotate(parent);
                        insertFixUp(parent);
                        return;
                    }
                }
            }
        }
    }


    /**
     * 左旋
     * 需要旋转的节点为x y为x的右节点
     * 1、将x的右子节点指向y的左子节点，将y的左子节点的父节点更新为x
     * 2、当x的父节点不为空时，将y的父节点更新为x的父节点，并将x的父节点指定的子树（当前x的子树位置）指定为y
     * 3、将x的父节点更新为y，将y的左子节点更新为x
     */
    private void leftRotate(RBNode x) {
        RBNode y = x.right;
        //1、将x的右子节点指向y的左子节点，将y的左子节点的父节点更新为x
        x.right = y.left;
        if (y.left != null) {
            y.left.parent = x;
        }
        //2、当x的父节点不为空时，将y的父节点更新为x的父节点，并将x的父节点指定的子树（当前x的子树位置）指定为y
        if (x.parent != null) {
            y.parent = x.parent;

            if (x == x.parent.left) {
                x.parent.left = y;
            } else {
                x.parent.right = y;
            }
        } else { //说明这时x为root
            this.root = y;
            this.root.parent = null;
        }

        //3、将x的父节点更新为y，将y的左子节点更新为x
        x.parent = y;
        y.left = x;
    }

    /**
     *
     * 右旋
     * 需要旋转的节点为y,x为y的左节点
     * 1、将y的左子节点指向x的右子节点，更新x的右子节点的父节点为y
     * 2、等y的父节点不为空时，更新x的父节点为y的父节点，并将y的父节点指定的子树（当前y的子树位置）指定为x
     * 3、将y的父节点更新为x，将x的右子节点更新为y
     */
    private void rightRotate(RBNode y){
        RBNode x = y.left;
        //1、将y的左子节点指向x的右子节点，更新x的右子节点的父节点为y
        y.left = x.right;
        if (x.right != null) {
            x.right.parent = y;
        }
        //2、等y的父节点不为空时，更新x的父节点为y的父节点，并将y的父节点指定的子树（当前y的子树位置）指定为x
        if (y.parent != null) {
            x.parent = y.parent;

            if (y == y.parent.left) {
                y.parent.left = x;
            } else {
                y.parent.right = x;
            }
        } else {
            this.root = x;
            this.root.parent = null;
        }
        //3、将y的父节点更新为x，将x的右子节点更新为y
        y.parent = x;
        x.right = y;
    }


    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;
        }
    }

}

打印红黑树

引用网上源码

package RBTree;

public class TreeOperation {

    // 用于获得树的层数
    public static int getTreeDepth(RBTree.RBNode root) {
        return root == null ? 0 : (1 + Math.max(getTreeDepth(root.getLeft()), getTreeDepth(root.getRight())));
    }


    private static void writeArray(RBTree.RBNode currNode, int rowIndex, int columnIndex, String[][] res, int treeDepth) {
        // 保证输入的树不为空
        if (currNode == null) return;
        // 先将当前节点保存到二维数组中
        res[rowIndex][columnIndex] = String.valueOf(currNode.getKey() + "-" + (currNode.isColor() ? "R" : "B") + "");

        // 计算当前位于树的第几层
        int currLevel = ((rowIndex + 1) / 2);
        // 若到了最后一层，则返回
        if (currLevel == treeDepth) return;
        // 计算当前行到下一行，每个元素之间的间隔（下一行的列索引与当前元素的列索引之间的间隔）
        int gap = treeDepth - currLevel - 1;

        // 对左儿子进行判断，若有左儿子，则记录相应的"/"与左儿子的值
        if (currNode.getLeft() != null) {
            res[rowIndex + 1][columnIndex - gap] = "/";
            writeArray(currNode.getLeft(), rowIndex + 2, columnIndex - gap * 2, res, treeDepth);
        }

        // 对右儿子进行判断，若有右儿子，则记录相应的"\"与右儿子的值
        if (currNode.getRight() != null) {
            res[rowIndex + 1][columnIndex + gap] = "\\";
            writeArray(currNode.getRight(), rowIndex + 2, columnIndex + gap * 2, res, treeDepth);
        }
    }


    public static void show(RBTree.RBNode root) {
        if (root == null) System.out.println("EMPTY!");
        // 得到树的深度
        int treeDepth = getTreeDepth(root);

        // 最后一行的宽度为2的（n - 1）次方乘3，再加1
        // 作为整个二维数组的宽度
        int arrayHeight = treeDepth * 2 - 1;
        int arrayWidth = (2 << (treeDepth - 2)) * 3 + 1;
        // 用一个字符串数组来存储每个位置应显示的元素
        String[][] res = new String[arrayHeight][arrayWidth];
        // 对数组进行初始化，默认为一个空格
        for (int i = 0; i < arrayHeight; i ++) {
            for (int j = 0; j < arrayWidth; j ++) {
                res[i][j] = " ";
            }
        }

        // 从根节点开始，递归处理整个树
        // res[0][(arrayWidth + 1)/ 2] = (char)(root.val + '0');
        writeArray(root, 0, arrayWidth/ 2, res, treeDepth);

        // 此时，已经将所有需要显示的元素储存到了二维数组中，将其拼接并打印即可
        for (String[] line: res) {
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < line.length; i ++) {
                sb.append(line[i]);
                if (line[i].length() > 1 && i <= line.length - 1) {
                    i += line[i].length() > 4 ? 2: line[i].length() - 1;
                }
            }
            System.out.println(sb.toString());
        }
    }
}

测试

package RBTree;

import java.util.Scanner;

/**
 * 红黑树方法测试
 */
public class RBTreeTest {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        RBTree<String, Object> rbTree = new RBTree<String, Object>();

        while (true) {
            System.out.println("请输入key：");
            String key = scanner.next();
            System.out.println();
            rbTree.insert(key, null);
            TreeOperation.show(rbTree.getRoot());
        }
    }
}