树形图
简介
Trep是由红黑树直接实现的结构。对于关键,值得比较和排序,显而易见的是:
1.1.key的类必须实现comparable方法,并且不能引发ClassCastException异常,否则必须指定comprartor。
2.因为TreeMap实现了Serializable接口,所以默认的或自定义的比较器也应该实现这个接口。
最重要的是实现了navigate ***p,我理解为导航地图,它提供了操纵地图视图的各种操作。
public class TreeMap<K,V> extends AbstractMap<K,V> implements NavigableMap<K,V>, Cloneable, java.io.Serializable{}***代码
施工方法
这四种构造方法实际上就是是否使用默认的兼容器。
对于无序映射,直接调用putAll,对于有序映射递归调用buildFromSorted,提高效率。
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);}?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) { }}***代码
但是putAll还是判断了SortedMap的地图实例。
红黑树的具体操作这里就不赘述了。
remove()和put()最根本的操作是红黑树的操作,get()也是二叉查找树的直观实现。
方法的详细说明
有关树的操作的方法,其实就是代码分支比较多,需要考虑各种情况然后转换为代码就好了比较的话看如果有comparator就用,没有就用key默认的comparable
Successor()查找下一个节点
在containsValue()从第一个节点开始successor遍历在forEach()从第一个节点开始successor遍历replaceAll()从第一个节点开始successor遍历赋值新的valueremove()遍历找出Object删除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; }}***代码
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;}***代码
gethightentry()/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()翻转地图
底层的DescendingSubMap()其实是同一个Map,但是所有的操作,比如getfist(),都会转换成getLast()来执行,所以DescendingMap()的操作还是会影响到原Map。
同样,subMap()的操作也会影响原图。
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()
***p的正常调用是AscendingSubMap,和DescendingMap一样,只是实现相反。
本文来自扎女孩的小辫子投稿,不代表舒华文档立场,如若转载,请注明出处:https://www.chinashuhua.cn/24/481583.html