TreeMap
属性
- TreeMap 实现了NavigableMap接口，意味着它**支持一系列的导航方法。**比如返回有序的key集合。
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 = null;
// 集合元素数量
private transient int size = 0;
// TreeMap结构改变次数，用于fail-fast机制的实现
private transient int modCount = 0;
/* 用于导航的Set与Map */
private transient EntrySet entrySet;
private transient KeySet<K> navigableKeySet;
private transient NavigableMap<K,V> descendingMap;
// 红黑树颜色枚举
private static final boolean RED = false;
private static final boolean BLACK = true;
}
Constructor
// 代表使用key的自然顺序来维持TreeMap的顺序，这里要求key必须实现Comparable接口
public TreeMap() {
comparator = null;
}
// 用指定的比较器构造一个TreeMap
public TreeMap(Comparator<? super K> comparator) {
this.comparator = comparator;
}
// 构造一个指定map的TreeMap，同样比较器comparator为空，使用key的自然顺序排序
public TreeMap(Map<? extends K, ? extends V> m) {
comparator = null;
putAll(m);
}
// 构造一个指定SortedMap的TreeMap，根据SortedMap的比较器来维持TreeMap的顺序
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) {
}
}
内部类 Entry
static final class Entry<K,V> implements Map.Entry<K,V> {
K key;
V value;
// 左子树
Entry<K,V> left;
// 右子树
Entry<K,V> right;
// 父节点
Entry<K,V> parent;
boolean color = BLACK;
//用key，value和父节点构造一个Entry，默认为黑色
Entry(K key, V value, Entry<K,V> parent) {
this.key = key;
this.value = value;
this.parent = parent;
}
}
经过以上可以看出TreeMap，key不可以为null，数据结构为红黑树；
put
- 如果没有根节点，直接创建为根节点
- 以比较器比较key，找到插入的位置
- 如果当前位置不为空，覆盖
- 为空，插入当前位置
- 重新平衡红黑树
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;
}
// 记录比较结果，如果cmp为负数，插入左子树
int cmp;
// 记录要插入的节点的父节点
Entry<K,V> parent;
// 获取当前使用的比较器
Comparator<? super K> cpr = comparator;
if (cpr != null) {//有指定的比较器
/* 如果新的key值小，往左子树查询；
* 如果新的key值大，往右子树查询；
* 如果key值相等，覆盖值
* 直到当前节点为空，则为插入的位置
*/
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);
}
else {
// key不可为空，并且必须实现了Comparable接口
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);
}
// 再找到的父节点下插入
Entry<K,V> e = new Entry<>(key, value, parent);
// 如果cmp为负数，插入左子树
if (cmp < 0)
parent.left = e;
else
parent.right = e;
// 保持红黑树平衡，对红黑树进行调整
fixAfterInsertion(e);
size++;
modCount++;
return null;
}
remove
public V remove(Object key) {
Entry<K,V> p = getEntry(key);
if (p == null)
return null;
V oldValue = p.value;
deleteEntry(p);
return oldValue;
}
/* 删除红黑树节点：
* 1) 当前节点是叶子节点，直接删除；
* 2) 当前节点只有一个子节点，删除节点，以子节点替代；
* 3) 当前节点有两个子节点，找到右子树中最小元素作为后继节点；将后继节点信息替换到
* 当前节点，因为后继节点至多只有右子树，以1.2.处理后继节点；
*/
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 = s;
// 后继节点至多只有右子树
}
// replacement为替代节点p的继承者
Entry<K,V> replacement = (p.left != null ? p.left : p.right);
if (replacement != null) {// 替代节点不是叶子节点
// 将替代节点的位置给予继承者
replacement.parent = p.parent;
if (p.parent == null)
root = replacement;
else if (p == p.parent.left)
p.parent.left = replacement;
else
p.parent.right = replacement;
// 删除替代节点
p.left = p.right = p.parent = null;
// 如果替代节点为黑色，修复红黑树性质
if (p.color == BLACK)
fixAfterDeletion(replacement);
} else if (p.parent == null) { // 替代节点是叶子节点，且没有父节点，即其为根节点
root = null;//删除根节点
} else { // 替代节点是叶子节点，且有父节点
if (p.color == BLACK)// 如果替代节点为黑色，修复红黑树性质
fixAfterDeletion(p);
// 删除替代节点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;
}
}
}
get
//以比较器结果左右查询子树
public V get(Object key) {
Entry<K,V> p = getEntry(key);
return (p==null ? null : p.value);
}
final Entry<K,V> getEntry(Object key) {
// Offload comparator-based version for sake of performance
if (comparator != null)
return getEntryUsingComparator(key);
if (key == null)
throw new NullPointerException();
@SuppressWarnings("unchecked")
Comparable<? super K> k = (Comparable<? super K>) key;
Entry<K,V> p = root;
while (p != null) {
int cmp = k.compareTo(p.key);
if (cmp < 0)
p = p.left;
else if (cmp > 0)
p = p.right;
else
return p;
}
return null;
}
final Entry<K,V> getEntryUsingComparator(Object key) {
@SuppressWarnings("unchecked")
K k = (K) key;
Comparator<? super K> cpr = comparator;
if (cpr != null) {
Entry<K,V> p = root;
while (p != null) {
int cmp = cpr.compare(k, p.key);
if (cmp < 0)
p = p.left;
else if (cmp > 0)
p = p.right;
else
return p;
}
}
return null;
}
红黑树平衡
新增后平衡
将新插入的节点设置为红色
如果当前为根节点，将其置为黑色；
如果当前的父节点是黑色，因为不会对路径上的黑色节点数量有影响，不再做处理
如果当前的父节点是红色，则祖父节点一定为黑
如果叔叔节点是红色
- 将父节点与叔节点置为黑色，祖父节点置为红色，然后将祖父节点作为插入节点，递归判断
如果叔叔节点是黑色或空节点（以下基于父节点为祖父节点的左子树）
- 如果插入位置为左子树
- 将祖父节点右旋
- 将父节点设置为黑色
- 将祖父节点设置为红色
- 如果插入位置为右子树
- 将父节点左旋
- 然后交换当前节点与父节点身份（形成上方情况）
- 如果插入位置为左子树
private void fixAfterInsertion(Entry<K,V> x) {
// 先将颜色改为红色
x.color = RED;
// 父节点是黑色，不再做处理
while (x != null && x != root && x.parent.color == RED) {
if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {// 父节点为祖父节点的左子树
Entry<K,V> y = rightOf(parentOf(parentOf(x)));//叔叔节点
if (colorOf(y) == RED) {// 叔叔节点是红色
// 将父与叔节点置为黑色，祖父节点置为红色
setColor(parentOf(x), BLACK);
setColor(y, BLACK);
setColor(parentOf(parentOf(x)), RED);
// 将祖父节点作为插入节点，递归判断
x = parentOf(parentOf(x));
} else {
if (x == rightOf(parentOf(x))) {// 插入位置为右子树
// 将x设置为父节点后左旋，左旋后x即为插入节点的左子树
x = parentOf(x);
rotateLeft(x);
}
setColor(parentOf(x), BLACK);// 父节点设置为黑色
setColor(parentOf(parentOf(x)), RED);// 祖父节点设置为红色
rotateRight(parentOf(parentOf(x)));// 将祖父节点右旋
}
} else {// 父节点为祖父节点的右子树
Entry<K,V> y = leftOf(parentOf(parentOf(x)));//叔叔节点
if (colorOf(y) == RED) {// 叔叔节点是红色
// 将父与叔节点置为黑色，祖父节点置为红色
setColor(parentOf(x), BLACK);
setColor(y, BLACK);
setColor(parentOf(parentOf(x)), RED);
// 将祖父节点作为插入节点，递归判断
x = parentOf(parentOf(x));
} else {
if (x == leftOf(parentOf(x))) {// 插入位置为左子树
// 将x设置为父节点后右旋，右旋后x即为插入节点的右子树
x = parentOf(x);
rotateRight(x);
}
setColor(parentOf(x), BLACK);// 父节点设置为黑色
setColor(parentOf(parentOf(x)), RED);// 祖父节点设置为红色
rotateLeft(parentOf(parentOf(x)));// 将祖父节点左旋
}
}
}
// 将根节点置为黑色
root.color = BLACK;
}
删除后平衡
以下均基于以当前节点的路径被删除了一个黑色节点
当前节点为红色，将当前节点置为黑色即可
当前节点为黑色（以下基于为父节点的左子树）
- 如果兄弟节点不存在，将父节点 P 看作新的当前节点 N处理
- 兄弟节点为红色，则父节点、兄弟节点的子树均为黑色
- 将父节点置为红色，兄弟节点置为黑色
- 左旋父节点
- 转向其他处理方式
兄弟节点 B 为黑色，P为任意颜色
- BR为黑色，BL为黑色
- 将兄弟节点B改为红色；此时经过P的路径都少了一个黑色
- 将P 看作新的 N 继续处理
- BR为黑色，BL为红色
- 交换B 和 BL的颜色
- 右旋节点B
- 转为下方的处理方式
- BR为红色，BL为任意颜色
- 将兄弟节点B 置为 父节点P 的颜色；
- 将父节点 置为 黑色；
- 将 BR 置为黑色；
- 左旋父节点 P
- BR为黑色，BL为黑色