弄一个网站,商业网站是什么,上海造价信息网,外包 网站开发公司TreeMap详解 TreeMap是Map接口的一个实现类#xff0c;底层基于红黑树的实现#xff0c;按照key的顺序存储 TreeMap 从继承结构可以看到TreeMap除了继承了AbstractMap类#xff0c;还实现了NavigableMap接口#xff0c;而NavigableMap接口是继承自SortedMap接口的#xff… TreeMap详解 TreeMap是Map接口的一个实现类底层基于红黑树的实现按照key的顺序存储 TreeMap 从继承结构可以看到TreeMap除了继承了AbstractMap类还实现了NavigableMap接口而NavigableMap接口是继承自SortedMap接口的所以TreeMap是可以进行排序的 关键变量 // 比较器根据比较器来决定TreeMap的排序如果为空按照key做自然排序(最小的在根节点)private final Comparator? super K comparator;// 根节点private transient EntryK,V root;/** * The number of entries in the tree * 树的大小 */private transient int size 0;/** * The number of structural modifications to the tree. * 修改次数 */private transient int modCount 0;// Entry为TreeMap的内部类static final class EntryK,V implements Map.EntryK,V { K key; V value; EntryK,V left; EntryK,V right; EntryK,V parent; boolean color BLACK;} 构造函数 // 默认空参构造器比较器设置为空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(SortedMapK, ? extends V m) { comparator m.comparator(); try { buildFromSorted(m.size(), m.entrySet().iterator(), null, null); } catch (java.io.IOException cannotHappen) { } catch (ClassNotFoundException cannotHappen) { }} get方法 public V get(Object key) { EntryK,V p getEntry(key); return (pnull ? null : p.value);}final EntryK,V getEntry(Object key) { // Offload comparator-based version for sake of performance if (comparator ! null) return getEntryUsingComparator(key); // 从这里可以看出TreeMap的key不可以为null if (key null) throw new NullPointerException(); SuppressWarnings(unchecked) Comparable? super K k (Comparable? super K) key; // 获取根节点 EntryK,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;} put方法 public V put(K key, V value) { EntryK,V t root; // 根节点为null表示这是第一个元素 if (t null) { // 主要是为了确保key是可排序的类以及key不能为null compare(key, key); // type (and possibly null) check // 第三个参数为父节点的entry根节点没有父节点所以为null root new Entry(key, value, null); size 1; modCount; return null; } int cmp; EntryK,V parent; // split comparator and comparable paths Comparator? super K cpr comparator; // 存在比较器的情况 if (cpr ! null) { 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不能为null if (key null) throw new NullPointerException(); SuppressWarnings(unchecked) Comparable? super K k (Comparable? super K) key; // do...while是为了找到该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); } EntryK,V e new Entry(key, value, parent); // 比父节点小是左子树 if (cmp 0) parent.left e; else parent.right e; // 插入之后还要进行平衡操作 fixAfterInsertion(e); size; modCount; return null;}private void fixAfterInsertion(EntryK,V x) { x.color RED; while (x ! null x ! root x.parent.color RED) { if (parentOf(x) leftOf(parentOf(parentOf(x)))) { EntryK,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 { EntryK,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;} remove方法 public V remove(Object key) { // 获取到该key对应的节点 和get相同 EntryK,V p getEntry(key); if (p null) return null; V oldValue p.value; deleteEntry(p); return oldValue;}private void deleteEntry(EntryK,V p) { modCount; size--; // If strictly internal, copy successors element to p and then make p // point to successor. // 存在两个子树(左子树和右子树) if (p.left ! null p.right ! null) { // 找到与p数值最接近的节点(即右子树的最左叶子节点) EntryK,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. // 找到所要替代的节点 EntryK,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); } // 此时replacement为null(表明 p没有左子树也没有右子树)如果p没有父节点表明该树只有一个根节点 else if (p.parent null) { // return if we are the only node. root null; } // 此时replacement为null(表明 p没有左子树也没有右子树)表明该节点为叶子节点 else { // No children. Use self as phantom replacement and unlink. // 删除的节点为黑色节点需要进行平衡 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; } }}static K,V TreeMap.EntryK,V successor(EntryK,V t) { if (t null) return null; else if (t.right ! null) { // 右节点不为null找到后继节点(即右子树的左叶子节点) EntryK,V p t.right; while (p.left ! null) p p.left; return p; } else { EntryK,V p t.parent; EntryK,V ch t; while (p ! null ch p.right) { ch p; p p.parent; } return p; }}private void fixAfterDeletion(EntryK,V x) { while (x ! root colorOf(x) BLACK) { if (x leftOf(parentOf(x))) { EntryK,V sib rightOf(parentOf(x)); if (colorOf(sib) RED) { setColor(sib, BLACK); setColor(parentOf(x), RED); rotateLeft(parentOf(x)); sib rightOf(parentOf(x)); } if (colorOf(leftOf(sib)) BLACK colorOf(rightOf(sib)) BLACK) { setColor(sib, RED); x parentOf(x); } else { if (colorOf(rightOf(sib)) BLACK) { setColor(leftOf(sib), BLACK); setColor(sib, RED); rotateRight(sib); sib rightOf(parentOf(x)); } setColor(sib, colorOf(parentOf(x))); setColor(parentOf(x), BLACK); setColor(rightOf(sib), BLACK); rotateLeft(parentOf(x)); x root; } } else { // symmetric EntryK,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);} https://zhhll.icu/2021/java基础/集合/7.TreeMap详解/ 本文由 mdnice 多平台发布
