2021-11-06 14:50:07
TreeMap
简介
TreeMap是由红黑树直接实现的结构。通过对键值进行比较和排序，很明显：
1.1.key的类必须实现comparable方法，并且不能抛出ClassCastException异常，或者必须指定comprartor。
2.因为TreeMap实现了Serializable接口，所以默认或自定义比较器也应该实现这个接口。
最重要的是实现导航地图，我理解为导航地图，并提供各种操作来操作地图视图。
公共类TreeMapK，V
扩展抽象映射
实现NavigableMapK，V，Cloneable，java.io.Serializable{}
复制代码
构造方法
四种构造方法，其实就是要不要用默认的兼容器。
对于无序映射，直接调用putAll，有序SortedMap递归调用buildFromSorted来提高效率。
public TreeMap(){ 0
比较器=null
}
公共树形图(比较器？超级K比较器){ 0
this.comparator=比较器；
}
公共树形图(地图？延伸K，扩展V(m){ 0
比较器=null
putAll(m)；
}
公共树图(SortedMapK，扩展V(m){ 0
比较器=m.comparator()；
尝试{
buildfromssorted(m . size()、m.entrySet()。迭代器()，null，null)；
} catch(Java . io . ioexception canothappen){ 0
} catch(class notfoundexception cannotHappen){ 0
}
}
复制代码
但是普塔尔还是判断了SortedMap的地图实例。
红黑树的具体操作在此不再赘述。
remove()和put()最基本的操作是红黑树的操作，get()也是二叉查找树的直观实现。
方法详解
树运算的方法其实就是代码分支很多，需要考虑各种情况再转换成代码。
为了比较，如果有比较器，就用它；如果没有比较器，使用键默认比较。
successor() 查找下个节点
后继遍历从containsValue()处的第一个节点开始
后继遍历从forEach()中的第一个节点开始
ReplaceAll()从第一个节点开始，后续节点遍历并分配一个新值。
移除()遍历以找出对象删除
静态K，V树图。EntryK，V后继者(EntryK，V t){ 0
//首先明确下一个节点比当前节点大，是当前节点右节点的左叶节点。
if (t==null)
返回null
else if (t.right！=null){ 0
EntryK，V p=t.right
while (p.left！=null)
p=p . left；
返回p；
} else {
EntryK，V p=t.parent
EntryK，V ch=t；
//当右节点为空且为父节点的右节点时，下一个节点为当前分支树的父节点。
while (p！=null ch==p . right){ 0
ch=p；
p=p.parent
}
//当右节点为空，是父节点的左节点时，下一个节点就是当前节点的父节点。
返回p；
}
}
复制代码
getCeilingEntry()/getFloorEntry 获取[low,key]/[key,high]的最大/小
值，没有返回null// 这个跟successor是相似的，其实如果根据搜索树没找到，就是找的下一个节点
final Entry<K,V> getCeilingEntry(K key) {
Entry<K,V> p = root;
while (p != null) {
int cmp = compare(key, p.key);
//比当前节点小，再跟左子节点比较
if (cmp < 0) {
if (p.left != null)
p = p.left;
else
return p;
} else if (cmp > 0) {
//比当前节点大，再跟右子节点比较
if (p.right != null) {
p = p.right;
} else {
//这里跟successor相同，比最右叶子大，下一个为当前子树的父节点
Entry<K,V> parent = p.parent;
Entry<K,V> ch = p;
while (parent != null && ch == parent.right) {
ch = parent;
parent = parent.parent;
}
return parent;
}
} else
//相等的话返回当前节点
return p;
}
return null;
}
//跟上面是镜像的过程
final Entry<K,V> getFloorEntry(K key) {
Entry<K,V> p = root;
while (p != null) {
int cmp = compare(key, p.key);
//比当前节点大，跟右子节点比较
if (cmp > 0) {
if (p.right != null)
p = p.right;
else
return p;
} else if (cmp < 0) {
//比当前节点小，再跟左子节点比较
if (p.left != null) {
p = p.left;
} else {
Entry<K,V> parent = p.parent;
Entry<K,V> ch = p;
//比最左叶子小，下一个为当前子树的父节点
while (parent != null && ch == parent.left) {
ch = parent;
parent = parent.parent;
}
return parent;
}
} else
//相等的话返回当前节点
return p;
?
}
return null;
}
复制代码getHigherEntry()/getLowerEntry获取[low,key)/(key,high]的最大/小值，没有返回null
跟getCeilingEntry一样的只不过对于相等的情况，不考虑相等的情况
final Entry<K,V> getHigherEntry(K key) {
Entry<K,V> p = root;
while (p != null) {
int cmp = compare(key, p.key);
if (cmp < 0) {
if (p.left != null)
p = p.left;
else
return p;
} else {
if (p.right != null) {
p = p.right;
} else {
Entry<K,V> parent = p.parent;
Entry<K,V> ch = p;
while (parent != null && ch == parent.right) {
ch = parent;
parent = parent.parent;
}
return parent;
}
}
}
return null;
}
复制代码DescendingMap()翻转map
底层由DescendingSubMap()实现，其实还是这个map，只不过对于所有的操作，比如getfist()，会将其转换为getLast()来执行,所以对于DescendingMap()的操作依然会影响原Map
同样的，subMap()的操作也会影响原Map
static final class DescendingSubMap<K,V> extends NavigableSubMap<K,V> {
private static final long serialVersionUID = 912986545866120460L;
// m是当前Map,fromStart是否从头开始为ture则lo为null，lo开始位置，loInclusive是否包含开始位置
DescendingSubMap(TreeMap<K,V> m,
boolean fromStart, K lo, boolean loInclusive,
boolean toEnd, K hi, boolean hiInclusive) {
super(m, fromStart, lo, loInclusive, toEnd, hi, hiInclusive);
}
复制代码//DescendingSubMap一些方法的实现
TreeMap.Entry<K,V> subLowest() { return absHighest(); }
TreeMap.Entry<K,V> subHighest() { return absLowest(); }
TreeMap.Entry<K,V> subCeiling(K key) { return absFloor(key); }
TreeMap.Entry<K,V> subHigher(K key) { return absLower(key); }
TreeMap.Entry<K,V> subFloor(K key) { return absCeiling(key); }
TreeMap.Entry<K,V> subLower(K key) { return absHigher(key); }
复制代码subMap()+headMap()+tailMap()
正常map调用的是AscendingSubMap，跟DescendingMap相同，只是相反的实现
