一、TreeMap概述
1.TreeMap继承了AbstractMap，是一个key-value集合；
2.TreeMap实现了NavigableMap接口（可以针对给定搜索目标返回最接近匹配项的导航方法），比如按照key升序或者降序返回；
3.TreeMap是一个有序的key-value，是通过红黑树来实现的；
二、红黑树介绍
1.红黑树概念
红黑树是一种自平衡二叉查找树，是在插入和删除操作时通过特定的操作保持二叉查找树的平衡，从而获得较高的查找性能，可以在O(log n)时间内做查找、插入和删除。
红黑树是每个节点都带有颜色属性的二叉查找树，颜色为红色或者黑色。在二叉查找树强制一般要求以外，还增加了以下额外要求：（1）节点是红色或黑色，（2）根节点是黑色，（3）每个叶节点（NIL节点，空节点）是黑色的，（4）每个红色节点的两个子节点都是黑色的（从每个叶子节点到根的所有路径上不能有两个连续的红色节点），（5）从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。
树中的每个节点包含5个域：color、key、left、right和p，如果某个节点没有子节点或者父节点，则该节点相应的指针（p）包含值NIL。
2.红黑树的旋转操作
红黑树也是二叉查找树，在进行插入的时候与二叉树的操作相同，但是在插入和删除操作过程中由于节点数目的变化导致二叉树不再符合红黑树的性质，因此在结点发生变化的时候需要对树中的结点的颜色进行变更和树进行旋转变化。
红黑树中对树的平衡是通过旋转操作来完成的，其中旋转分为左旋转和右旋转，下面是在《算法导论》中对左旋转和右旋转的伪代码，以及左旋转的一个调整的过程。
在伪代码中可以看到旋转过程主要有三个步骤，以左旋转为例，对节点x进行旋转：
（1）将节点x的右子节点赋值为y，将y的左子节点修改为x的右子节点
（2）将x在其父节点的子节点中的位置由y来代替
（3）将x设置为y的左子节点，完成左旋转操作。
下面的图就是一个左旋转的一个简单的处理过程，至于右旋转与其操作相似，这里就不讲了。
二、TreeMap源码解析
1.TreeMap中的重要变量
TreeMap中的数据是有序的，他是根据Entry中的key进行排序的，而key比较大小是根据比较器comparator来进行判断的，在使用中也可以自定义comparator，未定义时使用的是默认的比较器，按照自然顺序进行排序。
//比较器：可以通过这个对TreeMap的内部排序进行控制
private final Comparator<? super K> comparator;
//TreeMap的红黑结点，内部类
private transient Entry<K,V> root = null;
//map中元素的个数
private transient int size = 0;
//map中结构变动 的次数
private transient int modCount = 0;
//TreeMap的红黑树结点对应的集合
private transient EntrySet entrySet = null;
//keyset的导航类
private transient KeySet<K> navigableKeySet = null;
//键值对的倒序映射
private transient NavigableMap<K,V> descendingMap = null;
2.TreeMap的构造函数
TreeMap有四种构造方法：
（1）使用默认构造函数构造TreeMap的时候，使用的是java的默认的比较器来进行key的比较，对TreeMap进行排序；
（2）带比较器的构造函数，用户可以自定义比较器，按照自己的需要对TreeMap进行排序；
（3）带Map的构造函数，map是TreeMap的子集，使用默认比较器，map不是有序的，所以需要对map中的元素逐个的操作添加到TreeMap中；
（4）带SortedMap的构造函数，SortedMap是TreeMap的子集，这时候SortedMap是一个有序的map，是通过buildFromSorted()来创建对应的TreeMap。
//使用默认构造函数，按照自然顺序进行排序
public TreeMap() {
comparator = null;
}
//创建指定排序的比较器
public TreeMap(Comparator<? super K> comparator) {
this.comparator = comparator;
}
//创建包含指定map的treeMap，按照自然顺序进行排序
public TreeMap(Map<? extends K, ? extends V> m) {
comparator = null;
putAll(m);
}
//将一个指定map中的所有元素复制到新的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 cannotHappen) {
} catch (ClassNotFoundException cannotHappen) {
}
return;
}
}
super.putAll(map);
}
//创建一个map包含指定的比较器
public TreeMap(SortedMap<K, ? extends V> m) {
comparator = m.comparator();
try {
buildFromSorted(m.size(), m.entrySet().iterator(), null, null);
} catch (java.io.IOException cannotHappen) {
} catch (ClassNotFoundException cannotHappen) {
}
}
private void buildFromSorted(int size, Iterator it,
java.io.ObjectInputStream str,
V defaultVal)
throws java.io.IOException, ClassNotFoundException {
this.size = size;
root = buildFromSorted(0, 0, size-1, computeRedLevel(size),
it, str, defaultVal);
}
//根据一个已经排好序的map创建一个TreeMap，将map中的元素逐个添加到TreeMap中，并返回map的中间元素作为根节点
private final Entry<K,V> buildFromSorted(int level, int lo, int hi,
int redLevel,
Iterator it,
java.io.ObjectInputStream str,
V defaultVal)
throws java.io.IOException, ClassNotFoundException {
if (hi < lo) return null;
//获取中间元素
int mid = (lo + hi) >>> 1;
Entry<K,V> left = null;
//如果lo小于mid，则地柜调用获取mid的左孩子
if (lo < mid)
left = buildFromSorted(level+1, lo, mid - 1, redLevel,
it, str, defaultVal);
//获取mid结点对应的key和value
K key;
V value;
if (it != null) {
if (defaultVal==null) {
Map.Entry<K,V> entry = (Map.Entry<K,V>)it.next();
key = entry.getKey();
value = entry.getValue();
} else {
key = (K)it.next();
value = defaultVal;
}
} else { // use stream
key = (K) str.readObject();
value = (defaultVal != null ? defaultVal : (V) str.readObject());
}
//创建middle结点
Entry<K,V> middle = new Entry<>(key, value, null);
//如果当前节点的深度是红色节点的深度，则将结点设置为红色
if (level == redLevel)
middle.color = RED;
//设置middle为left的父节点，left为middle的左子节点
if (left != null) {
middle.left = left;
left.parent = middle;
}
//递归调用获取mid的右子节点
if (mid < hi) {
Entry<K,V> right = buildFromSorted(level+1, mid+1, hi, redLevel,
it, str, defaultVal);
middle.right = right;
right.parent = middle;
}
return middle;
}
在buildFromSorted中主要要理解到：他是通过递归的方法来讲每个元素进行关联的，为了保证是一颗红黑树，他是将中间结点作为TreeMap的根节点。
3.TreeMap的put操作
TreeMap在进行put操作时，主要有以下步骤：
（1）判断树是否是空的，如果是空的，直接将当前插入的k-v当做是根节点，完成了插入操作；
（2）如果树不是空的，获取比较器（不管是自定义的比较器还是默认的比较器），对树从根节点开始遍历，
（3）如果k小于结点的key，那么开始遍历左子节点，如果大于结点的key，开始遍历右子节点，如果相等，说明k已经在TreeMap中存在了，就用新的value值覆盖旧的value值，完成了插入操作；
（4）如果k在TreeMap中不存在，将k插入到其相应的位置，此时由于树的结构进行了变化，需要检验其是否满足红黑性的元素，调用fixAfterInsertion方法。
//将k-v插入到TreeMap中
public V put(K key, V value) {
Entry<K,V> t = root;
//如果红黑树为空，则插入根节点
if (t == null) {
compare(key, key);
root = new Entry<>(key, value, null);
size = 1;
modCount++;
return null;
}
int cmp;
Entry<K,V> parent;
Comparator<? super K> cpr = comparator;
//比较器不为空
if (cpr != null) {
//循环查找k-v在TreeMap中的位置
do {
parent = t;
cmp = cpr.compare(key, t.key);
//比较结果小于0，在左子树中查找
if (cmp < 0)
t = t.left;
else if (cmp > 0)
//比较结果大于0，在右子树中查找
t = t.right;
else
//比较结果相等，则说明结点已经存在，用新的value值替换旧的value值
return t.setValue(value);
} while (t != null);
}
else {
if (key == null)
throw new NullPointerException();
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);
//判断k是在其父节点的左子节点还是右子节点
if (cmp < 0)
parent.left = e;
else
parent.right = e;
//插入节点之后，开始进行红黑树调整，来恢复红黑树的特性
fixAfterInsertion(e);
size++;
modCount++;
return null;
}
fixAfterInsertion(e)方法主要就是对二叉树进行左旋转、右旋转和着色的操作，使其保持是一颗红黑树，下面看一下该方法主要操作过程：
//插入结点之后对红黑树进行调整，是为了使其保持红黑树的特性
private void fixAfterInsertion(Entry<K,V> x) {
x.color = RED; //插入的节点的颜色置为红色
//开始循环处理树：x结点不为空，并且不是根节点，x的父节点的颜色为红色
while (x != null && x != root && x.parent.color == RED) {
//x节点的父节点是其祖父节点的左节点
if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {
//y为x的祖父节点的右子节点，也就是x的右叔父结点
Entry<K,V> y = rightOf(parentOf(parentOf(x)));
//y的颜色是红色，及x的叔父结点是红色
if (colorOf(y) == RED) {
//将x的父节点的颜色置为黑色
setColor(parentOf(x), BLACK);
//y的颜色置为黑色
setColor(y, BLACK);
//x的祖父节点置为红色
setColor(parentOf(parentOf(x)), RED);
//x取值为x的祖父节点，继续往上处理
x = parentOf(parentOf(x));
} else { //y的颜色是黑色，及x的叔父结点是黑色
//x是其父节点的右子节点，那么将x赋值为x的父节点，同时进行左旋转操作
if (x == rightOf(parentOf(x))) {
x = parentOf(x);
rotateLeft(x);
}
//x的父节点置为黑色
setColor(parentOf(x), BLACK);
//x的祖父节点置为红色
setColor(parentOf(parentOf(x)), RED);
//开始右旋转x的祖父节点
rotateRight(parentOf(parentOf(x)));
}
} else { //x是其祖父节点的右子节点
//y为x的祖父节点的左子节点，也就是x的左叔父结点
Entry<K,V> y = leftOf(parentOf(parentOf(x)));
//如果y为红色，将x的父节点设置为黑色，y设置为黑色，x的祖父节点设置为红色，x赋值为x的祖父节点，继续处理
if (colorOf(y) == RED) {
setColor(parentOf(x), BLACK);
setColor(y, BLACK);
setColor(parentOf(parentOf(x)), RED);
x = parentOf(parentOf(x));
} else { //如果y为黑色
//x是其父节点的左子节点，x赋值为x的父节点，开始进行右旋转
if (x == leftOf(parentOf(x))) {
x = parentOf(x);
rotateRight(x);
}
//x的父节点设置为黑色，x的祖父节点设置为红色，对x的祖父节点开始进行旋转
setColor(parentOf(x), BLACK);
setColor(parentOf(parentOf(x)), RED);
rotateLeft(parentOf(parentOf(x)));
}
}
}
//将跟节点设置为黑色
root.color = BLACK;
}
（1）对于新增的几点，都是直接设置其颜色为红色，然后判断其父节点是否也是红色，如果不是红色，则不违反红黑树的原则，调整处理完成，根绝点设置为黑色；
（2）如果是违反规则的树，则需要根据其父节点、祖父节点、叔父节点共同来确定后续的操作，主要是hi设置颜色、左旋转还是右旋转。
所谓左旋转就是将新增结点（N）当做其父节点（P），将其父节点P当做新增结点（N)的左子节点；同样右旋转就是将新增节点（N）当做其父节点（P），将其父节点P当做新增加点（N）的右子节点。
//左旋转
private void rotateLeft(Entry<K,V> p) {
if (p != null) {
//r为p的右子树，将r的左子树改为p的右子树
Entry<K,V> r = p.right;
p.right = r.left;
//将r的父节点改为p的父节点
if (r.left != null)
r.left.parent = p;
r.parent = p.parent;
if (p.parent == null)
root = r;
else if (p.parent.left == p)
p.parent.left = r;
else
p.parent.right = r;
//将p设置为r的左子节点
r.left = p;
p.parent = r;
}
}
//右旋转
private void rotateRight(Entry<K,V> p) {
if (p != null) {
Entry<K,V> l = p.left;
p.left = l.right;
if (l.right != null) l.right.parent = p;
l.parent = p.parent;
if (p.parent == null)
root = l;
else if (p.parent.right == p)
p.parent.right = l;
else p.parent.left = l;
l.right = p;
p.parent = l;
}
}
下面举个例子，假如按照下面的顺序往TreeMap中添加元素，其处理的过程如下图：
由上面的过程可以总结出TreeMap插入节点时需要进行变色和旋转的情况有：
（1）插入的节点的父节点和叔节点均为红色时，表示一条路径上存在连续的红色，需要调整；
（2）插入的结点的父节点是红色的，叔节点是黑色的，且插入节点是其父节点的右子节点；
（3）插入的结点的父节点是红色的，叔节点是黑色的，且插入节点是其父节点的左子节点；
4.TreeMap的remove操作
在对TreeMap进行删除操作的时候，由于节点结构的变化也可能使得树不满足红黑树的结构，这时候也需要对树进行调整，同样是删除结点之后，调整红黑树，而在这里删除一个节点并不是真正的删除，而是在树中根据一定的规则找到一个节点来替代删除结果，然后在删除替代结点，例如删除结点A，找到A的替代结点B，这时候将B的k、v值覆盖A的k、v值，然后删除B节点。而替代节点的规则是：右分支的最左边，或者左分支的最右边（也就是大于当前k的最小值的节点）。
删除结点存在情况主要有三种：
（1）如果待删除的节点没有子节点，那么直接删除掉即可；
（2）如果待删除结点只有一个子节点，那么直接删除掉，用其子节点去替代它，可能需要进行颜色调整；
（3）如果删除节点有两个子节点，需要先找出他的后继节点，处理后继节点与被删除结点的父节点之间的关系，然后处理后继节点的子节点与被删除结点的子节点之间的关系，其主要操作见下面的代码：
//根据key值删除一个节点，并返回删除的节点
public V remove(Object key) {
Entry<K,V> p = getEntry(key);
if (p == null)
return null;
V oldValue = p.value;
deleteEntry(p);
return oldValue;
}
//删除一个节点
private void deleteEntry(Entry<K,V> p) {
modCount++;
size--;
//如果该节点的左子节点和右子节点均不为空，找到p的后继节点，将后继节点的key和value替代p的key和value,然后将p赋值为s
//这一步就是将删除p结点的操作改为删除替代节点的操作
if (p.left != null && p.right != null) {
//返回p的对应的后继节点，将
Entry<K,V> s = successor(p);
p.key = s.key;
p.value = s.value;
p = s;
}
//如果p有左子节点，找到左子节点，否则用右子节点
Entry<K,V> replacement = (p.left != null ? p.left : p.right);
//replacement不为空的话
if (replacement != null) {
//将p的父节点设置为replacement的父节点
replacement.parent = p.parent;
//如果p就是根节点，那么replacement设置为根节点
if (p.parent == null)
root = replacement;
else if (p == p.parent.left) //如果p是其父节点的左子节点，将replacement设置为其父节点的左子节点
p.parent.left = replacement;
else
p.parent.right = replacement; //否则将replacemnet设置为p的父节点右子节点
//将p结点置为null，节点删除了
p.left = p.right = p.parent = null;
//如果p结点是黑色的，那么需要对树进行调整
if (p.color == BLACK)
fixAfterDeletion(replacement);
} else if (p.parent == null) {
root = null; //如果p是空节点，则树是空的
} else {
//如果p结点是黑色的，需要对树进行调整
if (p.color == BLACK)
fixAfterDeletion(p);
//如果p的父节点不为空，
if (p.parent != null) {
//p为其父节点的左子节点，将其父节点的左子节点置为空
if (p == p.parent.left)
p.parent.left = null;
else if (p == p.parent.right)
p.parent.right = null;
p.parent = null;
}
}
}
//返回结点t的后继节点，返回大于t的最小的节点
static <K,V> TreeMap.Entry<K,V> successor(Entry<K,V> t) {
//t为null，返回null
if (t == null)
return null;
else if (t.right != null) { //t的右子节点不为空
//设置p为t的右子节点
Entry<K,V> p = t.right;
//开始遍历p的左子树，返回左子树中最后一个结点
while (p.left != null)
p = p.left;
return p;
} else { //如果t的右子节点为空
//设置p的t的父节点
Entry<K,V> p = t.parent;
Entry<K,V> ch = t;
//循环，如果ch是p的右子节点，一直向上查找
while (p != null && ch == p.right) {
ch = p;
p = p.parent;
}
return p;
}
}
主要看一下在删除结点过程中，后面会调用fixAfterDeletion(e)方法，是因为在删除结点之后也可能导致树不平衡，该方法主要是在删除操作之后调整树的平衡。
在上面删除的代码中可以看到，删除某个节点会用他的后继节点来天上，并且后继节点会设置为何删除结点同样的颜色，所以删除
例如删除节点9的操作过程如下：
（1）找到9对应的替代几点11，将11值赋值给9，后续的操作就是处理结点11，如第二个图；
（2）对节点11进行操作，由于节点11是黑色的，需要根据节点11对树进行调整，调用fixAfterDeletion方法；
（3）节点11的颜色是黑色的，11是父节点12的左子节点，19是11的叔节点，叔节点的右子节点为空，是黑色的，将：叔节点19的左子节点15置为黑色，叔节点19置为红色，同时右旋转19结点，其处理结点未第四个图；
（4）此时调整叔节点为15，将叔节点按照11结点的父节点的颜色赋值，则为红色，11结点的父节点12结点置为黑色，15结点的右子节点置为黑色，左旋转12节点
（5）旋转12节点之后的结果为第五张图，此时调整树结构完成；
（6）将11节点清空，完成删除操作。
在红黑树中删除调整的方法主要是：
//删除节点树调整
private void fixAfterDeletion(Entry<K,V> x) {
//循环遍历树，x不是根节点，x的颜色是黑色的
while (x != root && colorOf(x) == BLACK) {
//x是其父节点的左子节点
if (x == leftOf(parentOf(x))) {
//sib为x的的兄弟结点
Entry<K,V> sib = rightOf(parentOf(x));
//sib为红色时，将sib设置为黑色、x的父节点设置为红色，左旋转x的父节点，sib设置为x的父节点的右子节点
if (colorOf(sib) == RED) {
setColor(sib, BLACK);
setColor(parentOf(x), RED);
rotateLeft(parentOf(x));
sib = rightOf(parentOf(x));
}
//如果sib的两子节点都是黑色的，将sib设置为红色，x设置为s的父节点
if (colorOf(leftOf(sib)) == BLACK &&
colorOf(rightOf(sib)) == BLACK) {
setColor(sib, RED);
x = parentOf(x);
} else {//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));
}
//sib节点的颜色设置为x的父节点的颜色
setColor(sib, colorOf(parentOf(x)));
//x的父节点的颜色设置为黑色
setColor(parentOf(x), BLACK);
//sib的右子节点的颜色设置为黑色
setColor(rightOf(sib), BLACK);
//左旋转x的父节点
rotateLeft(parentOf(x));
//根节点赋值为x
x = root;
}
} else { //x是其父节点的右子节点
//sib为x的兄弟结点
Entry<K,V> sib = leftOf(parentOf(x));
//sib为红色时，设置sib颜色为黑色，x的父节点为红色，右旋转x的父节点，sib设置为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);
}
5.TreeMap中的获取实体Entry的方法
在TreeMap中有多种获取Entry实体的方法
| 方法名 | 方法说明 |
|---|---|
| Entry firstEntry() | 返回TreeMap中的第一个节点 |
| Entry lastEntry() | 返回TreeMap中的最后一个节点 |
| Entry pollFirstEntry() | 返回TreeMap中的第一个结点，并将该节点从树中删除 |
| Entry pollLastEntry() | 返回TreeMap中的最后一个节点，并将该节点从树中删除 |
| Entry lowerEntry(K key) | 返回小于key的最大值的键值对 |
| Entry floorEntry(K key) | 返回不大于key的最小值的键值对 |
| Entry ceilingEntry(K key) | 返回不小于key的最小键值对 |
| Entry higherEntry(K key) | 返回大于key的最小键值对 |
6.TreeMap的遍历方法
（1）遍历TreeMap的键值对：
根据entrySet()获取TreeMap的键值对
通过Iterator迭代器遍历上一步得到的集合
String key = null;
Integer integ = null;
Iterator iter = map.entrySet().iterator();
while(iter.hasNext()) {
Map.Entry entry = (Map.Entry)iter.next();
// 获取key
key = (String)entry.getKey();
// 获取value
integ = (Integer)entry.getValue();
}
（2）遍历TreeMap的键：
根据keySet()获取TreeMap的键对应的set集合
通过Iterator迭代器遍历上一步得到的集合
// map中的key是String类型，value是Integer类型
String key = null;
Integer integ = null;
Iterator iter = map.keySet().iterator();
while (iter.hasNext()) {
// 获取key
key = (String)iter.next();
// 根据key，获取value
integ = (Integer)map.get(key);
}
（3）遍历TreeMap的值：
根据value()获取TreeMap的值的集合
通过Iterator迭代器遍历上一步得到的集合
// map中的key是String类型，value是Integer类型
Integer value = null;
Collection c = map.values();
Iterator iter= c.iterator();
while (iter.hasNext()) {
value = (Integer)iter.next();
}
三、TreeMap总结
1.TreeMap中的键值对是有序的，按照自然顺序或者自定义的顺序；
2.TreeMap中的如果是默认比较器，其key值不能为空；
3.TreeMap是基于红黑树实现的，每次对结构进行改变时，都需要进行检验是否仍然保持平衡；
4.TreeMap是非线程安全的。