【144期】考考基础部分，你能说出 TreeMap 原理实现及常用方法吗？

点击上方“Java面试题精选”，关注公众号

面试刷图，查缺补漏

>>号外：往期面试题，10篇为一个单位归置到本公众号菜单栏->面试题，有需要的欢迎翻阅

阶段汇总集合：一百期面试题汇总

一. TreeMap概述

TreeMap存储K-V键值对，通过红黑树（R-B tree）实现；
TreeMap继承了NavigableMap接口，NavigableMap接口继承了SortedMap接口，可支持一系列的导航定位以及导航操作的方法，当然只是提供了接口，需要TreeMap自己去实现；
TreeMap实现了Cloneable接口，可被克隆，实现了Serializable接口，可序列化；
TreeMap因为是通过红黑树实现，红黑树结构天然支持排序，默认情况下通过Key值的自然顺序进行排序；

二. 红黑树回顾

因为TreeMap的存储结构是红黑树，我们回顾一下红黑树的特点以及基本操作，红黑树的原理可参考关于红黑树(R-B tree)原理:

https://www.cnblogs.com/LiaHon/p/11203229.html

下图为典型的红黑树：

红黑树规则特点：

节点分为红色或者黑色；
根节点必为黑色；
叶子节点都为黑色，且为null；
连接红色节点的两个子节点都为黑色（红黑树不会出现相邻的红色节点）；
从任意节点出发，到其每个叶子节点的路径中包含相同数量的黑色节点；
新加入到红黑树的节点为红色节点；

红黑树自平衡基本操作：

变色：在不违反上述红黑树规则特点情况下，将红黑树某个node节点颜色由红变黑，或者由黑变红；
左旋：逆时针旋转两个节点，让一个节点被其右子节点取代，而该节点成为右子节点的左子节点
右旋：顺时针旋转两个节点，让一个节点被其左子节点取代，而该节点成为左子节点的右子节点

三. TreeMap构造

我们先看一下TreeMap中主要的成员变量

private void fixAfterDeletion(Entry<K,V> x) {
    /**
     * 当x不是root节点且颜色为黑色时
     */
    while (x != root && colorOf(x) == BLACK) {
        /**
         * 首先分为两种情况，当前节点x是左节点或者当前节点x是右节点，这两种情况下面都是四种场景,这里通过
         * 代码分析一下x为左节点的情况，右节点可参考左节点理解，因为它们非常类似
         */
        if (x == leftOf(parentOf(x))) {
            Entry<K,V> sib = rightOf(parentOf(x));

            /**
             * 场景1：当x是左黑色节点，兄弟节点sib是红色节点
             * 兄弟节点由红转黑，父节点由黑转红，按父节点左旋，
             * 左旋后树的结构变化了，这时重新赋值sib，这个时候sib指向了x的兄弟节点
             */
            if (colorOf(sib) == RED) {
                setColor(sib, BLACK);
                setColor(parentOf(x), RED);
                rotateLeft(parentOf(x));
                sib = rightOf(parentOf(x));
            }

            /**
             * 场景2：节点x、x的兄弟节点sib、sib的左子节点和右子节点都为黑色时，需要将该节点sib由黑变
             * 红，同时将x指向当前x的父节点
             */
            if (colorOf(leftOf(sib))  == BLACK &&
                colorOf(rightOf(sib)) == BLACK) {
                setColor(sib, RED);
                x = parentOf(x);
            } else {
                /**
                 * 场景3：节点x、x的兄弟节点sib、sib的右子节点都为黑色，sib的左子节点为红色时，
                 * 需要将sib左子节点设置为黑色，sib节点设置为红色，同时按sib右旋，再将sib指向x的
                 * 兄弟节点
                 */
                if (colorOf(rightOf(sib)) == BLACK) {
                    setColor(leftOf(sib), BLACK);
                    setColor(sib, RED);
                    rotateRight(sib);
                    sib = rightOf(parentOf(x));
                }
                /**
                 * 场景4：节点x、x的兄弟节点sib都为黑色，而sib的左右子节点都为红色或者右子节点为红色、
                 * 左子节点为黑色，此时需要将sib节点的颜色设置成和x的父节点p相同的颜色，
                 * 设置x的父节点为黑色，设置sib右子节点为黑色，左旋x的父节点p，然后将x赋值为root
                 */
                setColor(sib, colorOf(parentOf(x)));
                setColor(parentOf(x), BLACK);
                setColor(rightOf(sib), BLACK);
                rotateLeft(parentOf(x));
                x = root;
            }
        } else {//x是右节点的情况
            Entry<K,V> sib = leftOf(parentOf(x));

            if (colorOf(sib) == RED) {
                setColor(sib, BLACK);
                setColor(parentOf(x), RED);
                rotateRight(parentOf(x));
                sib = leftOf(parentOf(x));
            }

            if (colorOf(rightOf(sib)) == BLACK &&
                colorOf(leftOf(sib)) == BLACK) {
                setColor(sib, RED);
                x = parentOf(x);
            } else {
                if (colorOf(leftOf(sib)) == BLACK) {
                    setColor(rightOf(sib), BLACK);
                    setColor(sib, RED);
                    rotateLeft(sib);
                    sib = leftOf(parentOf(x));
                }
                setColor(sib, colorOf(parentOf(x)));
                setColor(parentOf(x), BLACK);
                setColor(leftOf(sib), BLACK);
                rotateRight(parentOf(x));
                x = root;
            }
        }
    }

    setColor(x, BLACK);
}