红黑树：自平衡的排序二叉树。
特性：它是一颗空树或它的左右两个子树的高度差的绝对值不超过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。
5.png
上面展示了红黑树新增节点的五种情况，这五种情况覆盖了所有的新增可能，不管这棵红黑树多么复杂，都可以根据这五种情况进行生成。
来源：https://blog.csdn.net/chenssy/article/details/26668941
详情看连接，博主写的挺好
网友评论