TreeMap继承自AbstractMap，并实现了NavigableMap接口(NavigableMap继承自SortedMap接口)。底层的数据结构是红黑树，按照键的自然排序或者自定义实现的规则排序，实现元素的有序性。
特点
- 元素是有序的：按照key的自然排序或者是自定义的比较器进行排序(并不是按照插入顺序排序)
- 键不能重复，值可以重复：key不能重复，value可以重复
- 键不能为null，值可以为null
- 红黑树是一种自平衡的二叉树，通过规则维持树的高度近似平衡，保证查询的时间复杂度为O(log n)
红黑树底层原理
- TreeMap是基于红黑树实现的键值对集合
- 树的根节点为黑色
- 树里面的节点不是黑色的就是红色的
- 相邻的两个节点不能都是红色
- 从任意一个节点到其叶子节点的路径上黑色节点数相同
- 红黑树的所有叶子节点都是黑色(叶子节点是Nil节点)
参考博主：
https://www.cnblogs.com/GNLin0820/p/9120337.html添加节点
第一种情况
添加的节点(500)和它的父节点(400)也是红色，并且它的叔叔节点(Nil1)是黑色(Nil是不存在的叶子节点)
添加的节点(500)是叔叔节点(Nil1)的远亲(是父节点的右节点)
就以父节点(400)为中心点，左旋。旋转后：
- 父节点变成黑色，祖父节点变成红色
- 祖父节点(300)的父节点变成400，祖父节点(300)的左子节点是Nil1，右子节点是Nil2
- 父节点(400)的左子节点变成了300，右子节点是500
- 祖父节点(300)有父节点的话，父节点(400)的父节点 变成 祖父节点(300)的父节点
第二种情况
添加的节点(350)是父节点(400)的左子节点，父节点是红色；它的叔叔节点(Nil1)是黑色
添加的节点(350)是叔叔节点(Nil1)的近亲(父节点的左子节点)
就以父节点(400)为中心，先右旋。旋转后：
- 父节点(400)变成了插入节点(350)的右节点，400的父节点变成了350，400的左节点变成了Nil4
- 插入节点(350)的右节点变成了400，它的父节点变成了300
再左旋：以350作为中心点，左旋
第三种情况
添加节点(100)是父节点的左子节点，父节点(200)是红色，它的叔叔节点(Nil4)是黑色
添加的节点(100)是叔叔节点的远亲(挨的远)
则以父节点(200)为中心点，右旋，旋转后：
- 父节点(200)变成黑色，祖父节点(300)变成红色
- 300的父节点变成了200，左子节点变成了Nil3，右子节点变成了Nil4
- 200的右子节点变成了300，左子节点变成了100
- 如果祖父节点(300)不是根节点，父节点(200)的父节点 变成 祖父节点(300)的父节点
第四种情况
插入节点(250)是父节点的右子节点，父节点为祖父节点(300)的左子节点，父节点(200)是红色
插入节点(250)的叔叔节点(Nil4)是黑色
250与Nil4是近亲(挨的近)
以父节点(200)为中心点，先左旋：
- 200的父节点变成250，200的左子节点是Nil1，右子节点是Nil2
- 250的父节点变成300，250的左子节点变成200
再按照第三种情况，以250为中心点右旋
第五种情况
插入节点为红色，它的父节点也为红色，它的叔叔节点也是红色
直接将父节点和叔叔节点变成黑色，祖父节点变成红色
如果祖父节点是根节点，则祖父节点最后要变成黑色
首先确认插入节点位置，定位好插入节点的父节点，祖父节点，叔叔节点
看自己和父节点颜色，都是红色就需要修复树平衡(相邻节点不能都是红色)
确认要修复平衡后，看叔叔节点颜色
叔叔是红色，直接改变叔叔和父亲的颜色(变成黑色)，再改变祖父节点颜色(变为红色)
叔叔是黑色，就要左旋或者右旋
自己是左节点，父亲也是左节点：自己是红色，父节点变成黑色，祖父节点变成红色。以父亲为中心右旋
自己是左节点，父亲是右节点：以父亲为中心，先右旋再左旋，旋转完之后变换颜色，自己变成黑色，父亲节点和祖父节点变成红色
自己是右节点，父亲也是右节点：自己是红色，父节点变成黑色，祖父节点变成红色。以父亲为中心左旋
自己是右节点，父亲是左节点：以父亲为中心，先左旋再右旋，旋转完之后变换颜色，自己变成黑色，父亲节点和祖父节点变成红色
完成当次平衡后，如果叔叔是红色节点：把祖父节点作为下一次平衡的插入点；如果叔叔是黑色节点：把父亲节点作为下一次平衡的插入点
直到遍历到根节点或者是当前插入点的父节点是黑色，结束平衡操作
删除节点(部分)
首先要确认删除节点时不存在的情况
第二，四种：不满足条件：相邻的两个节点不能为红色
第一，三，五，六种：不满足条件：从任意节点到叶子节点路径上的黑色节点数要相同
也就是说：
在第一五种情况下：父节点是红色，只有一个子节点且是黑色，这时候必然会有另一个子节点也是黑色
在第二六种情况下：父节点是黑色，只有一个子节点且是黑色，这时候必然会有另一个子节点也是黑色
以下是会发生的删除情况
第一种情况
被删除的节点是黑色，并且只有一个子节点是红色
- 100这个节点作为修复树的起点(代码中设置为replacement)
- 100的父节点改为400
- 200的所有指针都置为空
- 100作为平衡树的起点去做平衡修复：100的颜色是红色，没有其他操作，直接将100这个节点的颜色变为黑色
第二种情况
要删除的节点p有左右子节点
- 找到500的后继节点：就是600，被确认为要删除的节点
- 将600节点里面的key-value复制到500节点
- p指针变成指向600节点
- 600节点没有子节点，所以没有replacement作为作为修复平衡树的起点
- 600节点有父节点：600节点自己作为修复平衡树的起点
- 600节点是红色，不需要修复平衡，直接将600节点中的指针清空
第三种情况
要删除的节点为450，有左右节点。
- 确认其后继节点为600，将600节点的key-value复制给450节点，600被确认为要删除的节点
- 600(p指针指向的节点，以下皆为p指向)没有子节点，则600作为修复树的起点
- 600节点的颜色为黑色(被删除的节点是黑色，破坏了树的平衡)，修复树
- 600的兄弟节点只有一个子节点，并且和600是近亲,420和440节点颜色互换
- 以420为中心左旋
- 以440为中心右旋
- 清空p指针指向的节点
第四种情况
方法
构造方法
public class TreeMap<K,V>
extends AbstractMap<K,V>
implements NavigableMap<K,V>, Cloneable, java.io.Serializable
{
//比较器
private final Comparator<? super K> comparator;
//根节点
private transient Entry<K,V> root;
//树中节点个数
private transient int size = 0;
//树的修改次数
private transient int modCount = 0;
public TreeMap() {
comparator = null;
}
//创建一个TreeMap，自定义比较器
public TreeMap(Comparator<? super K> comparator) {
this.comparator = comparator;
}
//创建一个TreeMap，将传入集合中的元素复制到TreeMap中
public TreeMap(Map<? extends K, ? extends V> m) {
comparator = null;
putAll(m);
}
//创建一个TreeMap，将传入的集合复制到TreeMap中，使用传入集合中的比较器
public TreeMap(SortedMap<K, ? extends V> m) {
comparator = m.comparator();
try {
buildFromSorted(m.size(), m.entrySet().iterator(), null, null);
} catch (java.io.IOException | ClassNotFoundException cannotHappen) {
}
}
}查找当前节点的后继节点
//查找当前节点的后继节点(比当前节点大的最小节点)
static <K,V> TreeMap.Entry<K,V> successor(Entry<K,V> t) {
if (t == null)
return null;
//如果t节点的右节点不为空，则查找该右节点的最小左节点
else if (t.right != null) {
Entry<K,V> p = t.right;
while (p.left != null)
p = p.left;
return p;
}
//如果t节点的右节点为空，则查找该节点的父节点，若t是父节点的左节点，则返回该父节点
else {
Entry<K,V> p = t.parent;
Entry<K,V> ch = t;
//若t是p(父节点)的右节点，则继续向上查找，直到查找到p，其中t是p的左节点，返回p
while (p != null && ch == p.right) {
ch = p;
p = p.parent;
}
return p;
}
}删除节点后自平衡
x节点是修复平衡的起点
//x为删除方法中计算出的后继者节点的子节点或者是后继者节点本身
//如果x节点不是根节点且它的颜色是黑色，则需要左旋或者右旋
//否则直接将x节点的颜色变为黑色
private void fixAfterDeletion(Entry<K,V> x) {
//如果x节点不是根节点且它的颜色是黑色
while (x != root && colorOf(x) == BLACK) {
//如果x节点是左节点
if (x == leftOf(parentOf(x))) {
Entry<K,V> sib = rightOf(parentOf(x));
//同一个父节点，x作为左节点是黑色，sib作为右节点是红色
//将sib设置为黑色，父节点设置为红色
//以x的父节点为中心点左旋
if (colorOf(sib) == RED) {
setColor(sib, BLACK);
setColor(parentOf(x), RED);
rotateLeft(parentOf(x));
sib = rightOf(parentOf(x));
}
//sib的左节点是黑色，sib的右节点也是黑色，设置sib为红色
//设置完成后将x的父节点赋值给x
if (colorOf(leftOf(sib)) == BLACK &&
colorOf(rightOf(sib)) == BLACK) {
setColor(sib, RED);
x = parentOf(x);
}
//如果sib的左右节点其中一个是红色
else {
//如果sib的右节点是黑色，设置sib的左节点为黑色，sib为红色，以sib为中心右旋
//将x节点的父节点的右节点赋值给sib
if (colorOf(rightOf(sib)) == BLACK) {
setColor(leftOf(sib), BLACK);
setColor(sib, RED);
rotateRight(sib);
sib = rightOf(parentOf(x));
}
//上面if条件执行与否都会执行下面的代码
//将sib的颜色设置为x父节点的颜色
//将x父节点的颜色设置为黑色
//将sib的右节点颜色设置为黑色
//以x的父节点为中心左旋
setColor(sib, colorOf(parentOf(x)));
setColor(parentOf(x), BLACK);
setColor(rightOf(sib), BLACK);
rotateLeft(parentOf(x));
//将x设置为根节点，跳出循环
x = root;
}
}
//如果x是右节点，与是左节点的情况是对称的
else {
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);
}添加单个元素
public V put(K key, V value) {
Entry<K,V> t = root;
if (t == null) {
compare(key, key); // type (and possibly null) check
root = new Entry<>(key, value, null);
size = 1;
modCount++;
return null;
}
int cmp;
Entry<K,V> parent;
Comparator<? super K> cpr = comparator;
//比较器不为空，根据比较器规则查找元素，若key已存在，更新key对应的value值
if (cpr != null) {
do {
parent = t;
cmp = cpr.compare(key, t.key);
if (cmp < 0)
t = t.left;
else if (cmp > 0)
t = t.right;
else
return t.setValue(value);
} while (t != null);
}
//比较器为空，则按照自然顺序排序比较，查找key，若key存在，则更新key对应的value值
else {
if (key == null)
throw new NullPointerException();
@SuppressWarnings("unchecked")
Comparable<? super K> k = (Comparable<? super K>) key;
do {
parent = t;
cmp = k.compareTo(t.key);
if (cmp < 0)
t = t.left;
else if (cmp > 0)
t = t.right;
else
return t.setValue(value);
} while (t != null);
}
//key不存在，新建一个节点存放键值对，放入红黑树中
Entry<K,V> e = new Entry<>(key, value, parent);
if (cmp < 0)
parent.left = e;
else
parent.right = e;
//添加完成后，调用函数保证红黑树的自平衡
fixAfterInsertion(e);
size++;
modCount++;
return null;
}添加多个元素
//按照map的比较器添加元素或者是按照默认自然排序规则添加元素
public void putAll(Map<? extends K, ? extends V> map) {
int mapSize = map.size();
if (size==0 && mapSize!=0 && map instanceof SortedMap) {
Comparator<?> c = ((SortedMap<?,?>)map).comparator();
if (c == comparator || (c != null && c.equals(comparator))) {
++modCount;
try {
buildFromSorted(mapSize, map.entrySet().iterator(),
null, null);
} catch (java.io.IOException | ClassNotFoundException cannotHappen) {
}
return;
}
}
super.putAll(map);
}删除单个元素
private void deleteEntry(Entry<K,V> p) {
modCount++;
size--;
//如果要删除的节点，左右节点都不为空，查找到当前节点的后继节点
//将后继节点的键值对数据拷贝到要删除的节点中，并且将后继者节点作为被删除的节点
if (p.left != null && p.right != null) {
Entry<K,V> s = successor(p);
p.key = s.key;
p.value = s.value;
//将后继者节点赋值给p，后续操作的p其实是此处查找到的后继者节点
p = s;
} // p has 2 children
//指定从replacement开始修复树的平衡
//从后继者节点的左节点或者右节点开始
Entry<K,V> replacement = (p.left != null ? p.left : p.right);
//如果replacement节点不为空，后继者节点的父节点与成为replacement节点的父节点
if (replacement != null) {
replacement.parent = p.parent;
//如果后继者节点的父节点为空，则replacement作为根节点
if (p.parent == null)
root = replacement;
//如果后继者节点是其父节点的左节点，则replacement成为父节点的左节点
else if (p == p.parent.left)
p.parent.left = replacement;
//如果后继者节点是其父节点的右节点，则replacement成为父节点的右节点
else
p.parent.right = replacement;
//将后继者节点的指针都清空
p.left = p.right = p.parent = null;
// 修复树的平衡，从replacement节点开始
//如果删除的后继者节点是黑色，调用修复
if (p.color == BLACK)
fixAfterDeletion(replacement);
}
//如果后继者节点没有父节点，并且也没有子节点(左右节点)，那么清空根节点
else if (p.parent == null) {
root = null;
}
//如果后继者节点没有子节点但是有父节点，那么后继者节点自己作为树平衡的开始节点
else {
//修复树平衡
if (p.color == BLACK)
fixAfterDeletion(p);
//删除后继者节点(清除后继者节点的指针，以及后继者节点的父节点指向它的指针)
if (p.parent != null) {
if (p == p.parent.left)
p.parent.left = null;
else if (p == p.parent.right)
p.parent.right = null;
p.parent = null;
}
}
}