TreeMap底层实现红黑树

作者: yeying12321 | 来源:发表于2018-04-06 22:18 被阅读20次

树-红黑树和AVL树的区别
Java基础(三)
4、TreeMap
TreeMap源码阅读
集合13-TreeMap使用场景简析
TreeMap底层实现红黑树
源码解析（JDK1.8）之——TreeMap
Java TreeMap 与 TreeSet
JDK源码-Map系列
HashMap、LinkedHashMap及缓存的实现

红黑树：自平衡的排序二叉树。
特性：它是一颗空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。即对于其中任意一个子节点，其左右子树的高度都相近。

一棵有效的红黑树规则有5点：
（1）每个节点都只能是红色或者黑色
（2）根节点是黑色
（3）每个叶节点（NIL节点，空节点）是黑色的
（4）如果一个结点是红的，则它两个子节点都是黑的。也就是说一条路径上不能出现相邻的两个红色结点
（5）从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。

红黑树主要三大操作：左旋、右旋、着色。
重点在于其节点的增删时旋转的选择问题，这也是最大的难点。（需要多研究）

TreeMap继承AbstractMap，实现NavigableMap、Cloneable、Serializable三个接口。其中AbstractMap表明TreeMap为一个Map即支持key-value的集合，
NavigableMap则意外着其支持一系列的导航方法，具备针对给定搜索目标返回最接近匹配项的导航方法。

TreeMap中几个重要的属性

//比较器，因为TreeMap是有序的，通过comparator接口我们可以对TreeMap的内部排序进行精密的控制
        private final Comparator<? super K> comparator;
        //TreeMap红-黑节点，为TreeMap的内部类
        private transient Entry<K,V> root = null;
        //容器大小
        private transient int size = 0;
        //TreeMap修改次数
        private transient int modCount = 0;
        //红黑树的节点颜色--红色
        private static final boolean RED = false;
        //红黑树的节点颜色--黑色
        private static final boolean BLACK = true;

链接：# Comparable和Comparator的区别
Comparable

Comparable可以认为是一个内比较器，实现了Comparable接口的类有一个特点，就是这些类是可以和自己比较的，至于具体和另一个实现了Comparable接口的类如何比较，则依赖compareTo方法的实现，compareTo方法也被称为自然比较方法。如果开发者add进入一个Collection的对象想要Collections的sort方法帮你自动进行排序的话，那么这个对象必须实现Comparable接口。compareTo方法的返回值是int，有三种情况：
1、比较者大于被比较者（也就是compareTo方法里面的对象），那么返回正整数
2、比较者等于被比较者，那么返回0
3、比较者小于被比较者，那么返回负整数

Comparator
Comparator可以认为是是一个外比较器，个人认为有两种情况可以使用实现Comparator接口的方式：
1、一个对象不支持自己和自己比较（没有实现Comparable接口），但是又想对两个对象进行比较
2、一个对象实现了Comparable接口，但是开发者认为compareTo方法中的比较方式并不是自己想要的那种比较方式
Comparator接口里面有一个compare方法，方法有两个参数T o1和T o2，是泛型的表示方式，分别表示待比较的两个对象，方法返回值和Comparable接口一样是int，有三种情况：
1、o1大于o2，返回正整数
2、o1等于o2，返回0
3、o1小于o3，返回负整数

对于叶子节点Entry是TreeMap的内部类，它有几个重要的属性：

//键
        K key;
        //值
        V value;
        //左孩子
        Entry<K,V> left = null;
        //右孩子
        Entry<K,V> right = null;
        //父亲
        Entry<K,V> parent;
        //颜色
        boolean color = BLACK;

红黑树插入新节点的三个关键地方：
1、插入新节点总是红色节点。
2、插入节点的父节点是黑色，能维持性质。
3、如果插入节点的父节点是红色，破坏了性质。故插入算法就是通过重新着色或旋转，来维持性质。

插入新节点的五种情况：
1、新节点N为根节点：
直接插入，将颜色设置为黑色。

2、父节点P为黑色：
新节点N同样直接插入，同时颜色为红色，由于根据规则四它会存在两个黑色的叶子节点，值为null。同时由于通过它的子节点的路径依然会保存着相同的黑色节点数，同样满足规则5.

1-2.png

3、若父节点P和P的兄弟节点U都为红色
对于这种情况若直接插入肯定出现不平衡现象，如何处理？
P、U节点变黑、G节点变红。这时由于经过节点P、U的路径都必须经过G。所以在这些路径上的黑色节点数目还是相同的。但是经过上面的处理，可能G节点的父节点也是红色，这个时候需要将G节点当做新增节点递归处理。

3.png

4、若父节点P为红色，父节点兄弟节点U为黑色或者缺少，则新增节点N为P节点的右孩子
对于这种情况，对新增节点N、P进行一次左旋转。这里所产生的结果其实并没有完成，还是不平衡的（违反了规则四），这时我们需要进行情况5的操作。

4.png

5、父节点P为红色，父节点兄弟节点U为黑色或者缺少，则新增节点N为P节点的左孩子
这种情况可能由于情况四产生，也有可能不是。对于这种情况，先以P为中心进行右旋转，在旋转后产生的树中，节点P是节点N、G的父节点。但是这棵树并不规范，它违反了规则4，所以将P、G节点的颜色进行交换，使之其满足规范。开始时所有的路径都需要经过G,其它的黑色节点数一样，但是现在所有的路径改为经过P，且P为整棵树的唯一黑色节点，所以调整后的树同样满足规范5。