本文主要是介绍HashMap源码详解03-红黑树全部代码，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

文章目录

• 红黑树代码
• 红黑树打印代码
• 红黑树测试代码

• HashMap源码详解01-红黑树插入
• HashMap源码详解02-红黑树删除

红黑树代码只实现了插入和删除，查找与二叉查找树相同。直接运行RBTreeTest即可测试红黑树。

红黑树代码

public class RBTree<T extends Comparable<T>> {

    private static final boolean RED = true;
    private static final boolean BLACK = false;

    private Node<T> root;

    public Node<T> getRoot() {
        return root;
    }

    public void insert(T key) {
        // 根节点，直接插入
        if (root == null) {
            root = new Node<>(key);
        } else {
            // 当前循环节点
            Node<T> x = root;
            // 最后一个循环的节点
            Node<T> p = x;
            while (x != null) {
                p = x;
                int tmp = key.compareTo(x.key);
                // key比x大，插入到右子树
                if (tmp > 0) {
                    x = x.right;
                } else if (tmp < 0) {
                    // key比x小，插入到左子树
                    x = x.left;
                } else {
                    // 相等节点进行替换，只不过目前没有不需要设置值，直接返回
                    return;
                }
            }
            // p为待插入节点的父节点
            Node<T> node = new Node<>(key);
            if (key.compareTo(p.key) > 0) {
                p.right = node;
            } else {
                p.left = node;
            }
            node.parent = p;
            // 进行插入平衡
            insertBalance(node);
        }
        // 根节点染黑
        setBlack(root);
    }

    private void insertBalance(Node<T> x) {
        for (; ; ) {
            // 情景1：x节点为root，直接返回
            if (parentOf(x) == null) {
                root = x;
                return;
            }

            // 情景2：父节点是黑色 ==> 不用处理
            if (isBlack(parentOf(x))) {
                return;
            }
            // 情景3：父节点是红色，叔节点是红色 ==> 父节点和叔节点变成黑色，祖父节点变红，x指向祖父节点
            if (isRed(uncleOf(x))) {
                setBlack(parentOf(x));
                setBlack(uncleOf(x));
                setRed(gParentOf(x));
                x = gParentOf(x);
            }
            // 情景4：父节点红色，叔节点黑色
            else {
                // p是祖父节点的左子节点
                if (parentOf(x) == gParentOf(x).left) {
                    // 情景4.1：x是p的右子节点
                    if (x == parentOf(x).right) {
                        // 以p为节点进行左旋，并且x指向p
                        rotateLeft(x = parentOf(x));
                    }
                    // 情景4.2：x是p的左子节点 => p变黑，x祖父变红，祖父右旋
                    setBlack(parentOf(x));
                    setRed(gParentOf(x));
                    rotateRight(gParentOf(x));
                } else {
                    // p是祖父节点的右子节点
                    // 情景4.1：x是p的左子节点
                    if (x == parentOf(x).left) {
                        // 以p为节点进行右旋，并且x指向p
                        rotateRight(x = parentOf(x));
                    }
                    // 情景4.2：x是p的右子节点 => p变黑，x祖父变红，祖父左旋
                    setBlack(parentOf(x));
                    setRed(gParentOf(x));
                    rotateLeft(gParentOf(x));
                }
            }
        }
    }

    public void delete(T key) {
        // 指向待删除节点
        Node<T> x = root;
        while (x != null) {
            int tmp = key.compareTo(x.key);
            if (tmp > 0) {
                // 继续寻找右子树
                x = x.right;
            }
            // 继续寻找左子树
            else if (tmp < 0) {
                x = x.left;
            }
            // 寻找到节点
            else {
                // 如果x节点存在2个节点，则寻找前驱节点替换x节点，并且删除前驱节点
                if (x.left != null && x.right != null) {
                    Node<T> predecessor = predecessor(x.left);
                    // 前驱节点替换x节点
                    x.key = predecessor.key;
                    // 删除前驱节点
                    x = predecessor;
                }
                break;
            }
        }
        // 如果未找到删除节点，返回
        if (x == null) {
            return;
        }

        // 待删除节点只会存在3中情景：
        // 1、x存在一个子节点，此时肯定是x黑色，子节点红，此时只需要用子节点替换x并且染黑即可，不需要再平衡
        // 2、x不存在子节点，并且是红色，此时直接删除x节点，不需要再平衡
        // 3、x不存在节点，并且是黑色，此时删除x节点会影响黑高，需要进行再平衡
        // 执行到这一步，x最多存在一个子节点
        // 如果x存在一个子节点，使用子节点替换x
        if (x.left != null || x.right != null) {
            Node<T> p = x.left == null ? x.right : x.left;
            // 使用子节点替换x，p颜色染成x颜色
            p.parent = x.parent;
            p.color = x.color;
            if (parentOf(x) == null) {
                root = p;
            } else if (x == parentOf(x).left) {
                parentOf(x).left = p;
            } else {
                parentOf(x).right = p;
            }
            // 释放x
            x.left = x.right = x.parent = null;
        } else {
            // 如果x是黑色，先进行平衡，再删除x节点
            if (isBlack(x)) {
                deleteBalance(x);
            }
            // 删除x节点
            if (parentOf(x) == null) {
                root = null;
            } else if (x == parentOf(x).left) {
                parentOf(x).left = null;
            } else {
                parentOf(x).right = null;
            }
            x.left = x.right = x.parent = null;
        }
        // 根节点染黑
        setBlack(root);
    }

    private void deleteBalance(Node<T> x) {
        while (x != null) {
            // 情景1：x是根节点，直接返回
            if (parentOf(x) == null) {
                return;
            }
            Node<T> s, sl, sr, p;
            // 情景2：s是红色 ==> s黑，p红，p左旋或者右旋
            if (isRed(s = siblingOf(x))) {
                setBlack(s);
                setRed(p = parentOf(x));
                if (x == p.left) {
                    rotateLeft(p);
                } else {
                    rotateRight(p);
                }
            }
            // 执行到这一步，x和s肯定都是黑色
            // 情景3：s黑色，sl和sr黑色，p黑 ==> s染红，x指向p继续平衡
            if (isBlack(p = parentOf(x)) && isBlack(s = siblingOf(x)) &&
                    isBlack(leftOf(s)) && isBlack(rightOf(s))) {
                setRed(s);
                x = p;
            }
            // 情景4：s黑，sl黑sr黑色，p红 ==> s红，p黑
            else if (isRed(p = parentOf(x)) && isBlack(s = siblingOf(x)) &&
                    isBlack(leftOf(s)) && isBlack(rightOf(s))) {
                setRed(s);
                setBlack(p);
                return;
            } else {
                // 能执行到这一步，x和s肯定黑色，p可以是任意颜色，sl和sr不全是黑色
                // x是父节点的左节点
                if (x == parentOf(x).left) {
                    // 情景5：sl红，sr黑 ==> sl黑，s红，s右旋
                    s = siblingOf(x);
                    if (isRed(sl = leftOf(s)) && isBlack(rightOf(s))) {
                        setBlack(sl);
                        setRed(s);
                        rotateRight(s);
                    }
                    // 情景6：sr红 ==> s与p颜色互换，sr黑，p左旋
                    setColor(s = siblingOf(x), (p = parentOf(x)).color);
                    setBlack(p);
                    setBlack(rightOf(s));
                    rotateLeft(p);
                    return;
                } else {
                    // x是父节点的右节点
                    // 情景5：sr红，sl黑 ==> sr黑，s红，s左旋
                    s = siblingOf(x);
                    if (isRed(sr = rightOf(s)) && isBlack(leftOf(s))) {
                        setBlack(sr);
                        setRed(s);
                        rotateLeft(s);
                    }
                    // 情景6：sl红 ==> s与p颜色互换，sl黑，p右旋
                    setColor(s = siblingOf(x), (p = parentOf(x)).color);
                    setBlack(p);
                    setBlack(leftOf(s));
                    rotateRight(p);
                    return;
                }
            }
        }
    }

    /**
     * 为了方便与动画对比，使用前继节点
     *
     * @param x
     * @return
     */
    private Node<T> predecessor(Node<T> x) {
        if (x == null) {
            return null;
        }
        while (x.right != null) {
            x = x.right;
        }
        return x;
    }

    /**
     * 左旋
     *            x                           r
     *         /     \                      /    \
     *        a       r        =>          x      rr
     *      /   \                        /   \
     *    rl    rr                      a     rl
     *
     * @param x 待旋转节点
     */
    private void rotateLeft(Node<T> x) {
        Node<T> r = x.right;
        // 第1步：x与rl建立关联
        x.right = r.left;
        if (r.left != null) {
            r.left.parent = x;
        }
        // 第2步：r父节点与x父节点建立关联
        r.parent = x.parent;
        if (x.parent == null) {
            root = r;
        } else if (x == x.parent.left) {
            parentOf(x).left = r;
        } else {
            parentOf(x).right = r;
        }
        // 第3步：x与r建立关联
        x.parent = r;
        r.left = x;
    }

    /**
     * 右旋
     *           x                           l
     *        /     \                      /    \
     *       l       a        =>          ll      x
     *     /   \                                 /  \
     *   ll     lr                             lr     a
     *
     * @param x 待旋转节点
     */
    private void rotateRight(Node<T> x) {
        Node<T> l = x.left;
        // 第1步：x与lr建立关联
        x.left = l.right;
        if (l.right != null) {
            l.right.parent = x;
        }
        // 第2步：l父节点与x父节点建立关联
        l.parent = x.parent;
        if (x.parent == null) {
            root = l;
        } else if (x == x.parent.left) {
            parentOf(x).left = l;
        } else {
            parentOf(x).right = l;
        }
        // 第3步：x与l建立关联
        x.parent = l;
        l.right = x;
    }

    private boolean isRed(Node<T> x) {
        return x != null && RED == x.color;
    }

    /**
     * 判断节点是否为黑色，注意：空节点也算作是黑色
     *
     * @param x 节点
     * @return 是否黑色
     */
    private boolean isBlack(Node<T> x) {
        return x == null || BLACK == x.color;
    }

    private void setColor(Node<T> x, boolean color) {
        if (x != null) {
            x.color = color;
        }
    }

    private void setRed(Node<T> x) {
        if (x != null) {
            x.color = RED;
        }
    }

    private void setBlack(Node<T> x) {
        if (x != null) {
            x.color = BLACK;
        }
    }

    private Node<T> leftOf(Node<T> x) {
        return x == null ? null : x.left;
    }

    private Node<T> rightOf(Node<T> x) {
        return x == null ? null : x.right;
    }

    private Node<T> siblingOf(Node<T> x) {
        if (parentOf(x) == null) {
            return null;
        }
        if (x == parentOf(x).left) {
            return parentOf(x).right;
        } else {
            return parentOf(x).left;
        }
    }

    private Node<T> uncleOf(Node<T> x) {
        if (gParentOf(x) == null) {
            return null;
        }
        if (parentOf(x) == gParentOf(x).left) {
            return gParentOf(x).right;
        } else {
            return gParentOf(x).left;
        }
    }

    private Node<T> gParentOf(Node<T> x) {
        return parentOf(parentOf(x));
    }

    private Node<T> parentOf(Node<T> x) {
        return x == null ? null : x.parent;
    }

    static class Node<T extends Comparable<T>> {
        T key;
        boolean color;
        Node<T> parent;
        Node<T> left;
        Node<T> right;

        public Node(T key) {
            this.key = key;
            color = RED;
        }
    }
}

红黑树打印代码

public class TreeOperation {
    /*
    树的结构示例：
              1
            /   \
          2       3
         / \     / \
        4   5   6   7
    */

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


    private static void writeArray(RBTree.Node currNode, int rowIndex, int columnIndex, String[][] res, int treeDepth) {
        // 保证输入的树不为空
        if (currNode == null) return;
        // 0、默认无色
//       res[rowIndex][columnIndex] = String.valueOf(currNode.getValue());
        //1、颜色表示
        if (!currNode.color) {//黑色，加色后错位比较明显
            res[rowIndex][columnIndex] = ("\033[30;3m" + currNode.key + "\033[0m");
        } else {
            res[rowIndex][columnIndex] = ("\033[31;3m" + currNode.key + "\033[0m");
        }
        //2、R,B表示
//        res[rowIndex][columnIndex] = String.valueOf(currNode.getValue()+"-"+(currNode.isColor()?"B":"R")+"");

        // 计算当前位于树的第几层
        int currLevel = ((rowIndex + 1) / 2);
        // 若到了最后一层，则返回
        if (currLevel == treeDepth) return;
        // 计算当前行到下一行，每个元素之间的间隔（下一行的列索引与当前元素的列索引之间的间隔）
        int gap = treeDepth - currLevel - 1;
        // 对左儿子进行判断，若有左儿子，则记录相应的"/"与左儿子的值
        if (currNode.left != null) {
            res[rowIndex + 1][columnIndex - gap] = "/";
            writeArray(currNode.left, rowIndex + 2, columnIndex - gap * 2, res, treeDepth);
        }

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


    public static void show(RBTree.Node 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());
        }
    }
}

红黑树测试代码

public class RBTreeTest {
    public static void main(String[] args) {
        //新增节点
        // insertOpt();
        //删除节点
        deleteOpt();
    }

    /**
     * 插入操作
     */
    public static void insertOpt() {
        Scanner scanner = new Scanner(System.in);
        RBTree<Integer> rbt = new RBTree<>();
        while (true) {
            System.out.println("请输入你要插入的节点:");
            String key = scanner.next();
            System.out.println();
            rbt.insert(Integer.parseInt(key));
            TreeOperation.show(rbt.getRoot());
        }
    }

    /**
     * 删除操作
     */
    public static void deleteOpt() {
        RBTree<Integer> rbt = new RBTree<>();
        //预先造10个节点（1-10）
        for (int i = 1; i <= 15; i++) {
            rbt.insert(i);
        }
        TreeOperation.show(rbt.getRoot());
        //以下开始删除
        Scanner scanner = new Scanner(System.in);
        while (true) {
            System.out.println("请输入你要删除的节点:");
            String key = scanner.next();
            System.out.println();
            rbt.delete(Integer.parseInt(key));
            TreeOperation.show(rbt.getRoot());
        }
    }
}

这篇关于HashMap源码详解03-红黑树全部代码的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！