一、概要
- TreeMap是一个存储键值对对象的集合，键值对对象表现为<Key,Value>，所有的Map集合保存的数据都是键值对集合。其中Key是关键字，不能重复。可以为null，但是null需要有比较器，并且比较器内部需要对null值进行处理，否则会报空指针异常，key自带比较功能都不行。
- TreeMap必须有比较器，或者key自身自带有比较功能，否则会报java.lang.ClassCastException
- 底层数据结构：Java中的底层数据结构是红黑树，Android中的java代码使用的底层数据结构是平衡二叉查找树，都可以成为数据结构是二叉树。
- 添加、删除、查找的时间复杂度是O(logn)，就是单位时间的操作是的时间成本减少了一半。即2º = n ，那么o=logn。
- 实现了接口：NavigableMap，Cloneable，Serializable，其中NavigableMap又实现了接口SortedMap，在Android中TreeMap又直接实现了SortedMap。继承了类AbstractMap。
- 源码参考的Android-23和Java 1.8
二、构造函数
Java
一共三个构造函数
- 默认构造函数：将比较器设为空
- 参数是比较器子类的构造函数：将比较器声明为参数中的比较器
- 参数是Map的构造函数：将比较器设为空，将参数map中的数据加入到该类中。
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;
}
public TreeMap(Comparator<? super K> comparator) {
this.comparator = comparator;
}
public TreeMap(Map<? extends K, ? extends V> m) {
comparator = null;
putAll(m);
}
// Red-black mechanics，红黑机械师手套？？？？
private static final boolean RED = false;
private static final boolean BLACK = true;
//键值对对象：继承自Map的键值对对象
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;//颜色，黑色为true
/**
* Make a new cell with given key, value, and parent, and with
* {@code null} child links, and BLACK color.
*/
Entry(K key, V value, Entry<K,V> parent) {//创建一个键值对对象
this.key = key;
this.value = value;
this.parent = parent;
}
/**
* Returns the key.
* 获取该对象的键
* @return the key
*/
public K getKey() {
return key;
}
/**
* Returns the value associated with the key.
* 获取该对象的值
* @return the value associated with the key
*/
public V getValue() {
return value;
}
/**
* Replaces the value currently associated with the key with the given
* value.
* 设置该对象的值
* @return the value associated with the key before this method was
* called
*/
public V setValue(V value) {
V oldValue = this.value;
this.value = value;
return oldValue;
}
//判断键值对是否相等
public boolean equals(Object o) {
if (!(o instanceof Map.Entry))
return false;
Map.Entry<?,?> e = (Map.Entry<?,?>)o;
//判断键相等和值相等
return valEquals(key,e.getKey()) && valEquals(value,e.getValue());
}
//获取键值对的哈希值
public int hashCode() {
int keyHash = (key==null ? 0 : key.hashCode());
int valueHash = (value==null ? 0 : value.hashCode());
return keyHash ^ valueHash;
}
//转换成string
public String toString() {
return key + "=" + value;
}
}
//相等方法
static final boolean valEquals(Object o1, Object o2) {
return (o1==null ? o2==null : o1.equals(o2));
}
Android
一共四个构造函数
- 默认构造函数：将比较器设为自定义的默认比较器
- 参数是Map的构造函数：调用默认构造函数，循环将map中的数据循环插入到该对象中
- 参数是Compartor的构造函数：如果参数不为null，就将比较器设为参数中比较器，如果为null就将比较器设为默认的比较器
- 参数是SortedMap的构造函数：将比较器设为SortedMap的比较器(不为空)，为空仍然设为默认的比较器。将SortedMap中的数据循环插入到该对象中
@SuppressWarnings("unchecked") // to avoid //Comparable<Comparable<Comparable<...>>>，
//自定义默认比较器，用于比较，该比较器限定比较的两个对象都是Comparable的
private static final Comparator<Comparable> NATURAL_ORDER = new Comparator<Comparable>() {
public int compare(Comparable a, Comparable b) {
return a.compareTo(b);
}
};
Comparator<? super K> comparator;//比较器
Node<K, V> root;//根节点
int size = 0;//大小
int modCount = 0;//修改次数
public TreeMap() {
//默认比较器的泛型是Comparable，所以需要限定k是Comparable的子类
this.comparator = (Comparator<? super K>) NATURAL_ORDER;
}
public TreeMap(Map<? extends K, ? extends V> copyFrom) {
this();
for (Map.Entry<? extends K, ? extends V> entry : copyFrom.entrySet()) {
putInternal(entry.getKey(), entry.getValue());
}
}
@SuppressWarnings("unchecked") // unsafe! if comparator is null, this assumes K is comparable
public TreeMap(Comparator<? super K> comparator) {
if (comparator != null) {
this.comparator = comparator;
} else {
this.comparator = (Comparator<? super K>) NATURAL_ORDER;
}
}
@SuppressWarnings("unchecked") // if copyFrom's keys are comparable this map's keys must be also
public TreeMap(SortedMap<K, ? extends V> copyFrom) {
Comparator<? super K> sourceComparator = copyFrom.comparator();
if (sourceComparator != null) {
this.comparator = sourceComparator;
} else {
this.comparator = (Comparator<? super K>) NATURAL_ORDER;
}
for (Map.Entry<K, ? extends V> entry : copyFrom.entrySet()) {
putInternal(entry.getKey(), entry.getValue());//具体解析参考增加数据
}
}
static class Node<K, V> implements Map.Entry<K, V> {
Node<K, V> parent;//父节点
Node<K, V> left;//左子节点
Node<K, V> right;//右子节点
final K key;//KEY
V value;//值
int height;//高度，判断平衡的标识
Node(Node<K, V> parent, K key) {
this.parent = parent;
this.key = key;
this.height = 1;
}
//node的copy，重新copy一个新的树，主要用于TreeMap的Clone
Node<K, V> copy(Node<K, V> parent) {
//创建一个新节点
Node<K, V> result = new Node<K, V>(parent, key);
if (left != null) {
result.left = left.copy(result);//copy左子树
}
if (right != null) {
result.right = right.copy(result);//copy右子树
}
result.value = value;//值赋值
result.height = height;//高度赋值
return result;
}
public K getKey() {
return key;
}
public V getValue() {
return value;
}
public V setValue(V value) {
V oldValue = this.value;
this.value = value;
return oldValue;
}
@Override//判断节点是否相等
public boolean equals(Object o) {
if (o instanceof Map.Entry) {
Map.Entry other = (Map.Entry) o;
//相等的判断是键相等和值相等
return (key == null ? other.getKey() == null : key.equals(other.getKey()))
&& (value == null ? other.getValue() == null : value.equals(other.getValue()));
}
return false;
}
@Override
public int hashCode() {//返回节点的哈希值
return (key == null ? 0 : key.hashCode())
^ (value == null ? 0 : value.hashCode());
}
@Override
public String toString() {//转换成String
return key + "=" + value;
}
/**
* Returns the next node in an inorder traversal, or null if this is the
* last node in the tree.
* 在序列中该节点后面的一个节点，该序列按照比较器给定顺序排序
* 如果树的根节点左子树上节点比根小，那么就返回序列中该节点后面的第一个节点。该序列指的是树中所有节点按照从小到大顺序排列。
*/
Node<K, V> next() {
if (right != null) {
return right.first();
}
Node<K, V> node = this;
Node<K, V> parent = node.parent;
while (parent != null) {
if (parent.left == node) {
return parent;
}
node = parent;
parent = node.parent;
}
return null;
}
/**
* Returns the previous node in an inorder traversal, or null if this is
* the first node in the tree.
* 在序列中该节点前面的一个节点，该序列按照比较器给定顺序排序
* 如果树的根节点左子树上节点比根小，那么就返回序列中该节点前面的一个节点。该序列指的是树中所有节点按照从小到大顺序排列。
*/
public Node<K, V> prev() {
if (left != null) {
return left.last();
}
Node<K, V> node = this;
Node<K, V> parent = node.parent;
while (parent != null) {
if (parent.right == node) {
return parent;
}
node = parent;
parent = node.parent;
}
return null;
}
/**
* Returns the first node in this subtree.
* 在序列中的第一个节点，该序列按照比较器给定顺序排序
* 如果树的根节点左子树上节点比根小，那么就返回序列中第一个节点，就是树中最小的节点。该序列指的是树中所有节点按照从小到大顺序排列。
*/
public Node<K, V> first() {
Node<K, V> node = this;
Node<K, V> child = node.left;
while (child != null) {
node = child;
child = node.left;
}
return node;
}
/**
* Returns the last node in this subtree.
* 在序列中的最后一个节点，该序列按照比较器给定顺序排序
* 如果树的根节点左子树上节点比根小，那么就返回序列中最后一个节点，就是树中最大的节点。该序列指的是树中所有节点按照从小到大顺序排列。
*/
public Node<K, V> last() {
Node<K, V> node = this;
Node<K, V> child = node.right;
while (child != null) {
node = child;
child = node.right;
}
return node;
}
}
三、增加元素
4.1 增加一个元素
Java
红黑树增加，增加完成一个元素，如果破坏了红黑树特性就需要修复红黑树
关于红黑树的处理可以参考：链接
红黑树的叶子节点全部是黑色NULL节点，新插入的节点在NULL的上一层，新插入的节点默认是红色。
增加的核心点在于红黑树破坏之后的修复，也就是重新维持平衡的过程。
维持平衡操作的核心是自底向上循环往复判断处理破坏平衡的点，直到根节点为止。
该方法既是增加也是修改。
public V put(K key, V value) {
Entry<K,V> t = root;//临时节点
if (t == null) {//根节点为空
compare(key, key); // type (and possibly null) check，key为空判断，需要在比较器中处理，如果没有比较器且key不是自己实现了比较器，那么就会报空指针异常。
root = new Entry<>(key, value, null);//创建根节点
size = 1;//将size设为1
modCount++;//修改次数增加1，迭代器使用
return null;
}
int cmp;//比较值
Entry<K,V> parent;//父节点
// split comparator and comparable paths
Comparator<? super K> cpr = comparator;//比较器
//查找父jie'dian
if (cpr != null) {//比较器不为空
do {
parent = t;//父节点指向临时节点
cmp = cpr.compare(key, t.key);//比较临时t节点
if (cmp < 0)//比临时节点小，就向临时节点的左子树查找
t = t.left;
else if (cmp > 0)//比临时节点大，就向临时节点的右子树查找
t = t.right;
else//和临时节点相等，就表示找到了节点，将节点内值修改掉
return t.setValue(value);
} while (t != null);
//如果临时节点不为空，就一直向下查找，直到找到一个空节点，此时父节点指向了上一个不为空的节点。
}else {//TreeMap不包含比较器，那么就是自己实现了比较功能
if (key == null)//如果key为空，抛出空指针异常
throw new NullPointerException();
@SuppressWarnings("unchecked")
Comparable<? super K> k = (Comparable<? super K>) key;//检查k是否实现了比较功能，如果没实现会报空指针异常。
do {
parent = t;//父节点指向临时节点k
cmp = k.compareTo(t.key);//key自己比较
//该方法解析同上，只是
if (cmp < 0)
t = t.left;
else if (cmp > 0)
t = t.right;
else
return t.setValue(value);//修改完成直接返回老的值
} while (t != null);
}
//创建key-value键值对节点，parent指向该节点的父节点
Entry<K,V> e = new Entry<>(key, value, parent);
if (cmp < 0)//小于0表示新节点是父节点的左子
parent.left = e;
else//大于0表示新节点是父节点的右子
parent.right = e;
fixAfterInsertion(e);//新增完成修复节点
size++;//大小增加
modCount++;//修改数量增加
return null;//返回null表示新增。
}
final int compare(Object k1, Object k2) {//比较key值
return comparator==null ? ((Comparable<? super K>)k1).compareTo((K)k2)
: comparator.compare((K)k1, (K)k2);
}
/** From CLR */
//CLR==Common Language Runtime？？？？
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 = 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 = parentOf(x);//将节点指向父节点，此时就是将福界定啊
rotateRight(x);//右旋转
}
//变成右外侧插入
setColor(parentOf(x), BLACK);//将父节点颜色设为黑色
setColor(parentOf(parentOf(x)), RED);//将祖父节点设为红
rotateLeft(parentOf(parentOf(x)));//祖父节点左旋
//此时这个子树的根节点变为了--父节点--，判断该子树是否影响了整个树的平衡
}
}
}
root.color = BLACK;
}
/**
* Balancing operations.//平衡相关操作
*
* Implementations of rebalancings during insertion and deletion are
* slightly different than the CLR version. Rather than using dummy
* nilnodes, we use a set of accessors that deal properly with null. They
* are used to avoid messiness surrounding nullness checks in the main
* algorithms.
*/
//获取节点的颜色，如果为空返回黑色
private static <K,V> boolean colorOf(Entry<K,V> p) {
return (p == null ? BLACK : p.color);
}
//获取当前节点的父节点
private static <K,V> Entry<K,V> parentOf(Entry<K,V> p) {
return (p == null ? null: p.parent);
}
//设置当前节点的颜色
private static <K,V> void setColor(Entry<K,V> p, boolean c) {
if (p != null)
p.color = c;
}
//获取当前节点的左子节点
private static <K,V> Entry<K,V> leftOf(Entry<K,V> p) {
return (p == null) ? null: p.left;
}
//获取当前节点的右子节点
private static <K,V> Entry<K,V> rightOf(Entry<K,V> p) {
return (p == null) ? null: p.right;
}
/** From CLR */
//左旋操作，具体参照图左旋，核心点先处理p的右子树，然后处理右子树的左子，后处理父节点，左节点不处理
private void rotateLeft(Entry<K,V> p) {
if (p != null) {//节点不为空，旋转才有意义
Entry<K,V> r = p.right;//记录右节点
p.right = r.left;//将p节点的右子，设为r的左子
if (r.left != null)//如果r的左子存在，就将r的左子父节点设为p
r.left.parent = p;
r.parent = p.parent;//r的父节点设为p的父节点
if (p.parent == null)//如果p的父节点为null，表示p为root节点
root = r;//将root节点设为r
else if (p.parent.left == p)//如果p是p的父节点的左子，将p的父的左子设为r
p.parent.left = r;
else//不是，那么p就是p的父节点的右子，将p的右子设为r
p.parent.right = r;
r.left = p;//r的左子设为p
p.parent = r;//p的父节点设为r
}
}
/** From CLR */
//左旋操作，具体参照图右旋，核心点先处理p的左子树，然后左子树的右子，后处理父节点，左子节点不处理
private void rotateRight(Entry<K,V> p) {
if (p != null) {
Entry<K,V> l = p.left;//记录左子树
p.left = l.right;//将p的左子设为左子树的左子
if (l.right != null) l.right.parent = p;//如果p的左子树的右子不为空，将左子树右子的父节点设为当前节点
l.parent = p.parent;//将左子树的父节点设为p的父节点
if (p.parent == null)//如果p的父节点为空，表示p是根节点
root = l;//旋转后的根节点就是L
else if (p.parent.right == p)//如果p是父节点的右子就将父节点的右子设为L
p.parent.right = l;
else p.parent.left = l;//如果p是父节点的左子就将父节点的做子设为L
l.right = p;//将l的右子设为p
p.parent = l;//将p的父节点设为l
}
}
左旋和右旋如下图所示
左旋
右旋
Android
底层的数据结构是平衡二叉树。在节点高度差超过1的时候表示破坏了平衡，此时需要处理破坏平衡的节点。
处理方法的核心就是循环向上查找，直到找到根节点或者平衡节点。
左右旋转可以参考上图，除了代码不太一致，核心点还是相同的。
@Override
public V put(K key, V value) {
return putInternal(key, value);
}
V putInternal(K key, V value) {
//查找，如果找不到就创建一个节点
Node<K, V> created = find(key, Relation.CREATE);
//找到节点的值，此时值有可能为null，如新创建的节点
V result = created.value;
created.value = value;//将节点值设为新值
return result;//将老值返回，
}
//根据关系查找节点
Node<K, V> find(K key, Relation relation) {
if (root == null) {//表示树中没有节点
//判断是否有比较器，获取key实现比较结构
if (comparator == NATURAL_ORDER && !(key instanceof Comparable)) {
throw new ClassCastException(key.getClass().getName() + " is not Comparable"); // NullPointerException ok
}
if (relation == Relation.CREATE) {//关系等于创建时
root = new Node<K, V>(null, key);//创建root节点
size = 1;
modCount++;
return root;//将root节点返回
} else {
return null;
}
}
/*
* Micro-optimization: avoid polymorphic calls to Comparator.compare().
* This is 10% faster for naturally ordered trees.
* 检查比较器是否存在，或者key自带比较功能
*/
@SuppressWarnings("unchecked") // will throw a ClassCastException below if there's trouble
Comparable<Object> comparableKey = (comparator == NATURAL_ORDER)
? (Comparable<Object>) key
: null;
Node<K, V> nearest = root;//将最近的值设为
while (true) {
int comparison = (comparableKey != null)
? comparableKey.compareTo(nearest.key)
: comparator.compare(key, nearest.key);
/*
* We found the requested key.，找到需要的节点
*/
if (comparison == 0) {
switch (relation) {
case LOWER://查找比当前节点低的节点，返回前一个小的节点
return nearest.prev();
case FLOOR://地板，或者叫向下取整，如果相等就是它自己
case EQUAL://相等关系的节点
case CREATE://创建的节点，如果是创建表示表示找到了，不用创建
case CEILING://天花板，或者叫向上取整，如果相等了，表示就是自己
return nearest;//返回找到的节点
case HIGHER://更大的节点，当前节点的下一个节点
return nearest.next();
}
}
//如果小于0，接着向左子树找，如果大于0接着向右子树找
Node<K, V> child = (comparison < 0) ? nearest.left : nearest.right;
if (child != null) {//如果child不为空表示没有找到叶子节点。
nearest = child;
continue;
}
/*
* We found a nearest node. Every key not in the tree has up to two
* nearest nodes, one lower and one higher.
* 找到了一个相近的节点，没有找到key值相等的节点
*/
//表示需要的节点更小，比找到的节点小。找到的节点稍大
if (comparison < 0) { // nearest.key is higher
switch (relation) {
case LOWER://更小的节点，
case FLOOR://地板上节点
return nearest.prev();//将小一点的节点返回即可
case CEILING://天花板上的节点
case HIGHER://更大一点的节点
return nearest;//将找到的节点返回即可
case EQUAL://没有相等的节点
return null;
case CREATE://创建一个节点
Node<K, V> created = new Node<K, V>(nearest, key);
nearest.left = created;//创建节点是比找到的节点小
size++;
modCount++;
rebalance(nearest, true);//平衡节点，判断新创建的节点是否破坏平衡
return created;//将创建节点返回
}
} else { // comparison > 0, nearest.key is lower
//找到的节点比要找的节点稍小，但是没有要找的节点
switch (relation) {
case LOWER://更小一点的节点
case FLOOR://地板上的的节点
return nearest;//将找到的节点返回
case CEILING://天花板上的节点
case HIGHER://更大一点的节点
return nearest.next();//返回找到的节点的后续节点
case EQUAL://没有相等的节点
return null;
case CREATE://如果创建，就创建一个节点
Node<K, V> created = new Node<K, V>(nearest, key);
nearest.right = created;//将创建的节点设为找到节点的右节点
size++;
modCount++;
rebalance(nearest, true);//平衡树
return created;//返回创建节点
}
}
}
}
//传入的是不平衡点，是否是插入状态，因为有可能是删除
private void rebalance(Node<K, V> unbalanced, boolean insert) {
//赋值不平衡点，判断不平衡点是否为空.
for (Node<K, V> node = unbalanced; node != null; node = node.parent) {
Node<K, V> left = node.left;//获取不平衡点的左子节点
Node<K, V> right = node.right;//获取不平衡点的右子节点
int leftHeight = left != null ? left.height : 0;//获取左子的高度
int rightHeight = right != null ? right.height : 0;//获取右子的高度
int delta = leftHeight - rightHeight;//计算两者的高度差
//如果是插入节点，那么高度差一般为0或者为+-1
//高度差为+-2的情况一般是第一层循环产生之后
if (delta == -2) {//右子树比左子树高
Node<K, V> rightLeft = right.left;//记录右子树的左子
Node<K, V> rightRight = right.right;//记录右子树的右子
int rightRightHeight = rightRight != null ? rightRight.height : 0;//右子树右子
int rightLeftHeight = rightLeft != null ? rightLeft.height : 0;//右子树左子
int rightDelta = rightLeftHeight - rightRightHeight;//左子高度-右子高度
//rightDelta==-1表示右右
//rightDelta == 0 && !insert，表示删除前右边高，还是右右，需要左旋
if (rightDelta == -1 || (rightDelta == 0 && !insert)) {
rotateLeft(node); // AVL right right
} else {//这种情况是右左，先右旋变成右右，然后左旋变成左右
// assert (rightDelta == 1);
rotateRight(right); // AVL right left
rotateLeft(node);
}
if (insert) {//如果是插入，旋转之后高度差已经减少了，可以直接跳出循环
break; // no further rotations will be necessary
}
} else if (delta == 2) {//与上面的完全相反
Node<K, V> leftLeft = left.left;
Node<K, V> leftRight = left.right;
int leftRightHeight = leftRight != null ? leftRight.height : 0;
int leftLeftHeight = leftLeft != null ? leftLeft.height : 0;
//计算左子-右子的高度差
int leftDelta = leftLeftHeight - leftRightHeight;
//左左需要右旋
if (leftDelta == 1 || (leftDelta == 0 && !insert)) {
rotateRight(node); // AVL left left
} else {//左右，先左旋后右旋
// assert (leftDelta == -1);
rotateLeft(left); // AVL left right
rotateRight(node);
}
if (insert) {
break; // no further rotations will be necessary
}
} else if (delta == 0) {
//左子树节点和右子树节点高度相等，其实这个节点的高度并没有变
node.height = leftHeight + 1; // leftHeight == rightHeight
if (insert) {//如果是插入的话，这个时候已经平衡了，如果是删除有可能导致父节点不平衡，极限循环
break; // the insert caused balance, so rebalancing is done!
}
} else {
// assert (delta == -1 || delta == 1);
//如果高度差为+-1，插入时表示插入在该节点下插入了一个节点，而这个节点原来均为空，那么需要判断这个节点的父节点是否平衡，因为父节点有可能只有一个子节点，导致高度差大于1
// 如果是删除的情况，那么删除一个子节点，那么删除后可能会导致父节点两个子树高度差变为2，所以删除后需要进行循环
node.height = Math.max(leftHeight, rightHeight) + 1;
if (!insert) {
break; // the height hasn't changed, so rebalancing is done!
}
}
}
}
/**
* Rotates the subtree so that its root's right child is the new root.
*/
private void rotateLeft(Node<K, V> root) {
Node<K, V> left = root.left;//树的左节点
Node<K, V> pivot = root.right;//树的右节点
Node<K, V> pivotLeft = pivot.left;//树的右节点的左节点，右左节点
Node<K, V> pivotRight = pivot.right;//树的右节点的有节点，记录为右右节点
// move the pivot's left child to the root's right
root.right = pivotLeft;//将根节点的右节点右左节点
if (pivotLeft != null) {//如果右左不为空
pivotLeft.parent = root;//右左节点的父节点改为跟节点
}
//将右节点的父节点修改root的父节点，然后将父节点的子节点修改右节点
replaceInParent(root, pivot);
// move the root to the pivot's left
pivot.left = root;//右节点的左节点指向原跟节点
root.parent = pivot;//原根节点的父节点指向右节点
// fix heights，重新修改两个节点的高度
root.height = Math.max(left != null ? left.height : 0,
pivotLeft != null ? pivotLeft.height : 0) + 1;
pivot.height = Math.max(root.height,
pivotRight != null ? pivotRight.height : 0) + 1;
}
/**
* Rotates the subtree so that its root's left child is the new root.
* 根节点也是旋转点
*/
private void rotateRight(Node<K, V> root) {
Node<K, V> pivot = root.left;//记录左节点
Node<K, V> right = root.right;//记录右节点
Node<K, V> pivotLeft = pivot.left;//左节点的左节点，记为左左节点
Node<K, V> pivotRight = pivot.right;//左节点的右节点，记为左右节点
// move the pivot's right child to the root's left
root.left = pivotRight;//将根的左节点修改为左右节点
if (pivotRight != null) {//如果左右节点不为空
pivotRight.parent = root;//将左右节点父节点指向根节点
}
//替换父节点，将左节点的父节点修改原根节点的父节点，将父节点的子节点修改左节点
replaceInParent(root, pivot);
// move the root to the pivot's right
pivot.right = root;//将左节点的右子节点修改为根节点(旋转节点)
root.parent = pivot;//将旋转节点的父节点修改为左节点，这样原左节点就变成了新的根节点
// fixup heights，修改变化的两个节点的高度
root.height = Math.max(right != null ? right.height : 0,
pivotRight != null ? pivotRight.height : 0) + 1;
pivot.height = Math.max(root.height,
pivotLeft != null ? pivotLeft.height : 0) + 1;
}
//替换与父节点的链接关系
private void replaceInParent(Node<K, V> node, Node<K, V> replacement) {
Node<K, V> parent = node.parent;//记录node节点的父节点
node.parent = null;//将node指向父节点的对象置空
if (replacement != null) {//如果替换节点不为空
replacement.parent = parent;//将替换节点的父节点设为新的节点
}
if (parent != null) {//如果父节点不为空
if (parent.left == node) {//node节点的左子是node，就将左子设为替换节点
parent.left = replacement;
} else {//node节点的右子是node，就将右子设为替换节点
// assert (parent.right == node);
parent.right = replacement;
}
} else {//父节点为空，直接将根节点指向替换节点
root = replacement;
}
}
4.2 批量增加集合中的元素
Java
如果说map是SortedMap，且当前的TreeMap为空，参数map的比较器和当前TreeMap的比较器相同，那么使用迭代器从小到大以折半的方式将树组装成一个新的红黑树，而且最下方的节点是红色，其他的都是黑色。
如果不满足上述条件，那么使用的一个个插入的方式。
因为一个插入需要修复红黑树，性能上比较差。
public void putAll(Map<? extends K, ? extends V> map) {
int mapSize = map.size();
//当前集合数据为空，并且插入的集合不为空，并且插入的集合是排序集合
if (size==0 && mapSize!=0 && map instanceof SortedMap) {
//获取map的比较器
Comparator<?> c = ((SortedMap<?,?>)map).comparator();
//比较器相等，==或者equals。地址相等表示就是一个，equals表示地址之外相等
if (c == comparator || (c != null && c.equals(comparator))) {
++modCount;
try {
//将size和Key迭代器传入，关于迭代器可以看本篇中的迭代器代码
buildFromSorted(mapSize, map.entrySet().iterator(),
null, null);
} catch (java.io.IOException cannotHappen) {
} catch (ClassNotFoundException cannotHappen) {
}
return;
}
}
super.putAll(map);
}
/**
* Linear time tree building algorithm from sorted data. Can accept keys
* and/or values from iterator or stream. This leads to too many
* parameters, but seems better than alternatives. The four formats
* that this method accepts are:
*
* 1) An iterator of Map.Entries. (it != null, defaultVal == null).
* 2) An iterator of keys. (it != null, defaultVal != null).
* 3) A stream of alternating serialized keys and values.
* (it == null, defaultVal == null).
* 4) A stream of serialized keys. (it == null, defaultVal != null).
*
* It is assumed that the comparator of the TreeMap is already set prior
* to calling this method.
*
* @param size the number of keys (or key-value pairs) to be read from
* the iterator or stream
* @param it If non-null, new entries are created from entries
* or keys read from this iterator.
* @param str If non-null, new entries are created from keys and
* possibly values read from this stream in serialized form.
* Exactly one of it and str should be non-null.
* @param defaultVal if non-null, this default value is used for
* each value in the map. If null, each value is read from
* iterator or stream, as described above.
* @throws java.io.IOException propagated from stream reads. This cannot
* occur if str is null.
* @throws ClassNotFoundException propagated from readObject.
* This cannot occur if str is null.
*/
private void buildFromSorted(int size, Iterator<?> it,
java.io.ObjectInputStream str,
V defaultVal)
throws java.io.IOException, ClassNotFoundException {
this.size = size;//修改当前的size为map的size
//折半查找，computeRedLevel计算红色的level，最下面一级非叶子就是level
//TreeMap中的叶子节点是空节点
root = buildFromSorted(0, 0, size-1, computeRedLevel(size),
it, str, defaultVal);
}
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 {
/*
* Strategy: The root is the middlemost element. To get to it, we
* have to first recursively construct the entire left subtree,
* so as to grab all of its elements. We can then proceed with right
* subtree.
*
* The lo and hi arguments are the minimum and maximum
* indices to pull out of the iterator or stream for current subtree.
* They are not actually indexed, we just proceed sequentially,
* ensuring that items are extracted in corresponding order.
*/
if (hi < lo) return null;
int mid = (lo + hi) >>> 1;
Entry<K,V> left = null;
if (lo < mid)//一直折半查找，记录最小的值，关于折半的原因是二叉树
left = buildFromSorted(level+1, lo, mid - 1, redLevel,
it, str, defaultVal);
// extract key and/or value from iterator or stream
//迭代器出来的值就排序上第一值
K key;
V value;
if (it != null) {
if (defaultVal==null) {
Map.Entry<?,?> entry = (Map.Entry<?,?>)it.next();//找到最小的节点
key = (K)entry.getKey();
value = (V)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);
// color nodes in non-full bottommost level red
if (level == redLevel)//如果level相等，将颜色设置为红色
middle.color = RED;
//除了最下层的非叶子节点，那么所有的节点都是黑色的。
if (left != null) {
middle.left = left;
left.parent = middle;
}
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;
}
/**
* Find the level down to which to assign all nodes BLACK. This is the
* last `full' level of the complete binary tree produced by
* buildTree. The remaining nodes are colored RED. (This makes a `nice'
* set of color assignments wrt future insertions.) This level number is
* computed by finding the number of splits needed to reach the zeroeth
* node. (The answer is ~lg(N), but in any case must be computed by same
* quick O(lg(N)) loop.)
* 找到非叶子的level，二叉树的最下面的叶子是红色的。
*/
private static int computeRedLevel(int sz) {
int level = 0;
for (int m = sz - 1; m >= 0; m = m / 2 - 1)
level++;
return level;
}
AbstractMap.java
public void putAll(Map<? extends K, ? extends V> m) {
//循环调用put方法。
for (Map.Entry<? extends K, ? extends V> e : m.entrySet())
put(e.getKey(), e.getValue());
}
Android
直接调用的就是一个个插入的方式，可能是AVL树的修复复杂度比较低，性能相对来说比较好.
AbstractMap.java
public void putAll(Map<? extends K, ? extends V> map) {
for (Map.Entry<? extends K, ? extends V> entry : map.entrySet()) {
put(entry.getKey(), entry.getValue());
}
}
四、删除元素
删除元素一般指的是删除一个元素
Java
找到一个元素，如果元素不为null，记录元素的值，将元素删除，返回记录的值
删除情况一共有6中情况，具体参考：红黑树
public V remove(Object key) {
Entry<K,V> p = getEntry(key);//获取一个节点信息
if (p == null)
return null;
V oldValue = p.value;
deleteEntry(p);
return oldValue;
}
final Entry<K,V> getEntry(Object key) {
// Offload comparator-based version for sake of performance
if (comparator != null)//如果比较器不为null，表示使用比较器的进行排序，需要另外的查找
return getEntryUsingComparator(key);
if (key == null)//在没有比较器的情况下，key不能为null
throw new NullPointerException();
@SuppressWarnings("unchecked")
Comparable<? super K> k = (Comparable<? super K>) key;//可比较的key
Entry<K,V> p = root;
while (p != null) {
int cmp = k.compareTo(p.key);//比较
if (cmp < 0)//如果小于0，表示key值比较小
p = p.left;//向左找
else if (cmp > 0)//如果大于0，表示key值比较大
p = p.right;//向右找
else//如果相等，表示找到了，返回即可
return p;
}
return null;//循环跳出，并且没有找到，表示没有相应的key
}
private void deleteEntry(Entry<K,V> p) {
modCount++;
size--;
// If strictly internal, copy successor's element to p and then make p
// point to successor.
// 如果删除的节点有两个子树，就找到右子树上的最小节点来替换掉该节点
// 并将删除节点设为找到的节点。
if (p.left != null && p.right != null) {
Entry<K,V> s = successor(p);
p.key = s.key;
p.value = s.value;
p = s;
} // p has 2 children
// Start fixup at replacement node, if it exists.
// 如果需要删除的节点，有左节点就用删除节点的左节点当做替换节点
// 如果需要删除的节点没有左节点，就用右节点当做替换节点
Entry<K,V> replacement = (p.left != null ? p.left : p.right);
if (replacement != null) {//如果有替换节点，将替换节点替换掉删除节点
// Link replacement to parent
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;
// Null out links so they are OK to use by fixAfterDeletion.
p.left = p.right = p.parent = null;//将删除节点删除
// Fix replacement，如果删除的节点是红色，就直接删掉即可，因为并没有破坏红黑树。如果删除的节点是黑色就需要修复红黑树，因为破坏了红黑树的性质
if (p.color == BLACK)
fixAfterDeletion(replacement);//将破坏平衡点传入，修复红黑树
} else if (p.parent == null) { // return if we are the only node.
root = null;//如果删除点没有子节点，并且没有父节点，那么删除点就是根节点，那么删除它
} else { // No children. Use self as phantom replacement and unlink.
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;
}
}
}
/** From CLR */
private void fixAfterDeletion(Entry<K,V> x) {
//如果破坏平衡的节点不是根，并且节点颜色为黑色，那么表示根节点经过这个节点到达叶子节点路径上黑色节点数和其他路径的黑色节点上不同
while (x != root && colorOf(x) == BLACK) {
if (x == leftOf(parentOf(x))) {//判断该节点是否是父节点的左子树
Entry<K,V> sib = rightOf(parentOf(x));//兄弟节点
if (colorOf(sib) == RED) {//兄弟节点为红色，表达的是删除情况3
setColor(sib, BLACK);//将兄弟节点涂成黑色
setColor(parentOf(x), RED);//将父节点涂成红色
rotateLeft(parentOf(x));//以父节点为旋转点，左旋
sib = rightOf(parentOf(x));//重新定位兄弟节点，新的兄弟节点肯定为黑色
}
if (colorOf(leftOf(sib)) == BLACK &&
colorOf(rightOf(sib)) == BLACK) {//兄弟节点及其子节点为黑色，删除情况4
setColor(sib, RED);//将兄弟节点涂成红色
x = parentOf(x);//此时需要判断父节点是否破坏平衡，依次向上递归
} else {//兄弟节点的子节点有一个是红色
if (colorOf(rightOf(sib)) == BLACK) {//兄弟节点的右子有黑色，左子为红色，删除情况65
setColor(leftOf(sib), BLACK);//将兄弟节点的左节点涂成黑色
setColor(sib, RED);//将兄弟节点涂成红
rotateRight(sib);//以兄弟节点为旋转点，右旋
sib = rightOf(parentOf(x));//兄弟节点重新定位，应该是原兄弟节点的左子
}//兄弟节点右子为红色，不考虑左子。删除情况6
setColor(sib, colorOf(parentOf(x)));//将兄弟节点颜色设为父节点颜色
setColor(parentOf(x), BLACK);//将父节点设为黑色
setColor(rightOf(sib), BLACK);//将兄弟节点的右子设为黑色
rotateLeft(parentOf(x));//以根节点为旋转点，左旋
x = root;//一般这种情况都平衡了，所以将x指向root，在情况4下跳出循环统一设置最后判断点颜色。
}
} else { // symmetric，为上半部分算法，反向对称
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);
}
static <K,V> TreeMap.Entry<K,V> successor(Entry<K,V> t) {
if (t == null)
return null;
else if (t.right != null) {//查找右子树上最小点
Entry<K,V> p = t.right;
while (p.left != null)
p = p.left;
return p;
} else {//在判断是否包含值时使用，用于遍历整个树，这个判断节点用于向根递归
Entry<K,V> p = t.parent;
Entry<K,V> ch = t;
while (p != null && ch == p.right) {
ch = p;
p = p.parent;
}
return p;
}
}
Android
是AVL树的删除算法，平衡算法比较简单，依次从破坏平衡点向根判断是否平衡
@Override
public V remove(Object key) {
Node<K, V> node = removeInternalByKey(key);//删除节点
return node != null ? node.value : null;//是否有删除值
}
Node<K, V> removeInternalByKey(Object key) {
Node<K, V> node = findByObject(key);//找到这个节点
if (node != null) {//如果节点存在
removeInternal(node);//删除它
}
return node;
}
Node<K, V> findByObject(Object key) {
return find((K) key, EQUAL);//在增加元素中，有该方法的具体说明
}
void removeInternal(Node<K, V> node) {
Node<K, V> left = node.left;//左子树
Node<K, V> right = node.right;//右子树
Node<K, V> originalParent = node.parent;//父节点
if (left != null && right != null) {//左右子树不为空
/*
* To remove a node with both left and right subtrees, move an
* adjacent node from one of those subtrees into this node's place.
*
* Removing the adjacent node may change this node's subtrees. This
* node may no longer have two subtrees once the adjacent node is
* gone!
*/
// 如果左子树高度比较高，那么选择左子树最大节点替换删除节点
// 如果右子树高度比较高或相等，那么选择右子树最小节点替换删除节点
Node<K, V> adjacent = (left.height > right.height) ? left.last() : right.first();
//判断替换节点是否破坏平衡，以及恢复平衡
removeInternal(adjacent); // takes care of rebalance and size--
int leftHeight = 0;
left = node.left;//重新定位left
if (left != null) {//如果左子不为空
leftHeight = left.height;//获取左子高度
adjacent.left = left;//将左子设为替换节点的左子
left.parent = adjacent;//将左子的父节点设为新节点
node.left = null;//将node的左子置空
}
//相同方法处理右子树
int rightHeight = 0;
right = node.right;
if (right != null) {
rightHeight = right.height;
adjacent.right = right;
right.parent = adjacent;
node.right = null;
}
//将替换节点的高度，重新设置
adjacent.height = Math.max(leftHeight, rightHeight) + 1;
//将node父节点指向的节点指向替换节点
replaceInParent(node, adjacent);
return;
} else if (left != null) {//左子树不为空
replaceInParent(node, left);//以左子树根节点替换删除节点
node.left = null;
} else if (right != null) {//右子树不为空
replaceInParent(node, right);//以右子树根节点替换删除节点
node.right = null;
} else {//两个子树均为空
replaceInParent(node, null);//以空节点替换节点，就是将该节点删除掉
}
//那么从父节点开始，平衡被破坏，那么从父节点开始向根恢复平衡
rebalance(originalParent, false);
size--;
modCount++;
}
五、修改元素
Java
调用put方法，因为TreeMap中不能使用两个相同的key。
也可以调用replace方法，来替换相同的元素，这个API是在1.8中增加的。
这个方法的原方法在Map中增加的。
@Override
public V replace(K key, V value) {
Entry<K,V> p = getEntry(key);//获取一个节点，具体方法在四中有介绍
if (p!=null) {//如果有元素
V oldValue = p.value;//老值
p.value = value;//将值设为新值
return oldValue;//返回老值
}
return null;
}
@Override
public boolean replace(K key, V oldValue, V newValue) {
Entry<K,V> p = getEntry(key);//找到节点
if (p!=null && Objects.equals(oldValue, p.value)) {//如果节点的值是原来的值
p.value = newValue;//替换它
return true;
}
return false;
}
@Override
public void replaceAll(BiFunction<? super K, ? super V, ? extends V> function) {
Objects.requireNonNull(function);
int expectedModCount = modCount;
//循环将节点传递给function处理
//successor找到当前节点后一个节点
for (Entry<K, V> e = getFirstEntry(); e != null; e = successor(e)) {
e.value = function.apply(e.key, e.value);
if (expectedModCount != modCount) {
throw new ConcurrentModificationException();
}
}
}
//取得最小Key值的节点。。。
final Entry<K,V> getFirstEntry() {
Entry<K,V> p = root;
if (p != null)
while (p.left != null)
p = p.left;
return p;
}
Android
Android中没有replace的API
六、查询元素
Java
public V get(Object key) {
Entry<K,V> p = getEntry(key);//查询节点
return (p==null ? null : p.value);//返回节点的值
}
Android
@Override public V get(Object key) {
Entry<K, V> entry = findByObject(key);//查询节点
return entry != null ? entry.getValue() : null;//返回节点的值
}
七、包含元素
Java
实现了包含Key，实现是否包含值
public boolean containsKey(Object key) {
return getEntry(key) != null;
}
public boolean containsValue(Object value) {
//从小到大遍历元素节点，判断是否有相等的值
for (Entry<K,V> e = getFirstEntry(); e != null; e = successor(e))
if (valEquals(value, e.value))
return true;
return false;
}
Android
实现了包含key
包含值采用的是父类的方法。
@Override public boolean containsKey(Object key) {
return findByObject(key) != null;//根据key找到的元素是否等于null
}
AbstractMap.java
public boolean containsValue(Object value) {
Iterator<Map.Entry<K, V>> it = entrySet().iterator();
if (value != null) {
while (it.hasNext()) {//使用迭代器查找相等的值
if (value.equals(it.next().getValue())) {
return true;
}
}
} else {
while (it.hasNext()) {//使用迭代器查找Null值
if (it.next().getValue() == null) {
return true;
}
}
}
return false;
}
8、其他常用方法
8.1 集合的大小
Java
public int size() {
return size;
}
Android
@Override public int size() {
return size;
}
8.2 集合是否为空
Java
AbstractMap.java
public boolean isEmpty() {
return size() == 0;
}
Android
@Override public boolean isEmpty() {
return size == 0;
}
8.3 清空
Java
将根节点指向空，数据等待GC
public void clear() {
modCount++;
size = 0;
root = null;
}
Android
将根节点指向空，数据等待GC
@Override public void clear() {
root = null;
size = 0;
modCount++;
}
其他文章
容器解析
ArrayList解析
LinkedList解析
TreeMap解析(上)
TreeMap解析(下)
HashMap解析
LinkedHasMap解析(下)
Set解析
