现在的位置: 首页 > 编程语言 > 正文

JDK源代码分析聚集篇——-TreeMap下(不按先后,只看谁牛逼,jdk中的红黑树);

2019年06月10日 编程语言 ⁄ 共 14355字 ⁄ 字号 评论关闭
在上一节的分析中,我们已经对红黑色的实现和操作进行了分析,我们可以看见红黑树是一颗高度平衡的数;
TreeMap的实现也是利用的红黑树,我们来看代码:

在TreeMap中包含着一个根结点:

  1. private transient Entry<K,V> root = null;

这个Entry代码如下:

  1. static final class Entry<K,V> implements Map.Entry<K,V> {
  2.         K key;
  3.         V value;
  4.         //指向小儿子
  5.         Entry<K,V> left = null;
  6.         //指向大儿子
  7.         Entry<K,V> right = null;
  8.          //指向父亲
  9.         Entry<K,V> parent;
  10.         //颜色默认为黑色
  11.         boolean color = BLACK;
  12.       
  13.         Entry(K key, V value, Entry<K,V> parent) {
  14.             this.key = key;
  15.             this.value = value;
  16.             this.parent = parent;
  17.         }
  18.         public K getKey() {
  19.             return key;
  20.         }
  21.        
  22.         public V getValue() {
  23.             return value;
  24.         }
  25.       
  26.         public V setValue(V value) {
  27.             V oldValue = this.value;
  28.             this.value = value;
  29.             return oldValue;
  30.         }
  31.         public boolean equals(Object o) {
  32.             if (!(o instanceof Map.Entry))
  33.                 return false;
  34.             Map.Entry<?,?> e = (Map.Entry<?,?>)o;
  35.             return valEquals(key,e.getKey()) && valEquals(value,e.getValue());
  36.         }
  37.         public int hashCode() {
  38.             int keyHash = (key==null ? 0 : key.hashCode());
  39.             int valueHash = (value==null ? 0 : value.hashCode());
  40.             return keyHash ^ valueHash;
  41.         }
  42.         public String toString() {
  43.             return key + "=" + value;
  44.         }
  45.     }

废话不多说,我们来看一下他的插入实现:

  1.  public V put(K key, V value) {
  2.         Entry<K,V> t = root;
  3.         //如果树是空树
  4.         if (t == null) {
  5.             //那么树根节点就是节点
  6.             root = new Entry<K,V>(key, value, null);
  7.             size = 1;
  8.             modCount++;
  9.             return null;
  10.         }
  11.         int cmp;
  12.         Entry<K,V> parent;
  13.         //否则利用提供的比较器进行比较
  14.         Comparator<? super K> cpr = comparator;
  15.         if (cpr != null) {
  16.             do {
  17.                 parent = t; 
  18.                 
  19.                 cmp = cpr.compare(key, t.key);
  20.                 //如果比当前节点小,
  21.                 if (cmp < 0)
  22.                     //往小儿子递归
  23.                     t = t.left;
  24.                 else if (cmp > 0)
  25.                     //往大儿子递归
  26.                     t = t.right;
  27.                 else
  28.                     //如果已经有这个key,那么修改key,并且什么都可以 不修改了
  29.                     return t.setValue(value);
  30.             } while (t != null); //知道找到叶子节点;
  31.         }
  32.         else {
  33.             if (key == null)
  34.                 throw new NullPointerException();
  35.             //如果没有提供外部的比较器,那么就利用内置的比较器
  36.             Comparable<? super K> k = (Comparable<? super K>) key;
  37.             do {
  38.                 parent = t;
  39.                 cmp = k.compareTo(t.key);
  40.                 if (cmp < 0)
  41.                     t = t.left;
  42.                 else if (cmp > 0)
  43.                     t = t.right;
  44.                 else
  45.                     return t.setValue(value);
  46.             } while (t != null);
  47.         }
  48.         //生成一个叶子节点,准备进行加入
  49.         Entry<K,V> e = new Entry<K,V>(key, value, parent);
  50.         //利用最后的判断,将这个节点变成该叶子节点的儿子;
  51.         if (cmp < 0)
  52.             parent.left = e;
  53.         else
  54.             parent.right = e;
  55.         //由于有可能破坏了红黑树的规则,现在进行调整;
  56.         fixAfterInsertion(e);
  57.         size++;
  58.         modCount++;
  59.         return null;
  60.     }

  1. private void fixAfterInsertion(Entry<K,V> x) {
  2.         //首先将该新增节点染红,叶子节点(null)是黑色的;
  3.         x.color = RED;
  4.         //如果他的父亲是红色的,那么冲突开始;
  5.         while (x != null && x != root && x.parent.color == RED) {
  6.             //如果是左子数;
  7.             if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {
  8.                 Entry<K,V> y = rightOf(parentOf(parentOf(x)));
  9.                 //如果其兄弟是红色的,那么根据上一节的分析,将两兄弟都变成黑色,其父节点变红,这样黑色节点的数目没有发生变化,而我们距离跟更近一步;
  10.                 if (colorOf(y) == RED) {
  11.                     setColor(parentOf(x), BLACK);
  12.                     setColor(y, BLACK);
  13.                     setColor(parentOf(parentOf(x)), RED);
  14.                     x = parentOf(parentOf(x));
  15.                 } else {
  16.                  //兄弟为黑色
  17.          
  18.                     if (x == rightOf(parentOf(x))) {
  19.                         x = parentOf(x);
  20.                         rotateLeft(x);
  21.                     }
  22.                     setColor(parentOf(x), BLACK);
  23.                     setColor(parentOf(parentOf(x)), RED);
  24.                     rotateRight(parentOf(parentOf(x)));
  25.                 }
  26.                //如果是右子数,正好与上面相反;
  27.             } else {
  28.                 Entry<K,V> y = leftOf(parentOf(parentOf(x)));
  29.                 if (colorOf(y) == RED) {
  30.                     setColor(parentOf(x), BLACK);
  31.                     setColor(y, BLACK);
  32.                     setColor(parentOf(parentOf(x)), RED);
  33.                     x = parentOf(parentOf(x));
  34.                 } else {
  35.                     if (x == leftOf(parentOf(x))) {
  36.                         x = parentOf(x);
  37.                         rotateRight(x);
  38.                     }
  39.                     setColor(parentOf(x), BLACK);
  40.                     setColor(parentOf(parentOf(x)), RED);
  41.                     rotateLeft(parentOf(parentOf(x)));
  42.                 }
  43.             }
  44.         }
  45.         //冲突会一直追溯到跟,把跟染黑,不违背根节点是黑色的特性,并且使得所有的树枝的黑色节点因此加1,冲突解决;
  46.         root.color = BLACK;
  47.     }

看完了增加,我们再来看看删除

  1.   public V remove(Object key) {
  2.         //查找到该节点
  3.         Entry<K,V> p = getEntry(key);
  4.         //不存在则结束
  5.         if (p == null)
  6.             return null;
  7.         V oldValue = p.value;
  8.         //删除
  9.         deleteEntry(p);
  10.         //返回原值
  11.         return oldValue;
  12.     }

查找该节点:

  1. final Entry<K,V> getEntry(Object key) {
  2.         if (comparator != null)
  3.             //利用外部比较器
  4.             return getEntryUsingComparator(key);
  5.         if (key == null)
  6.             throw new NullPointerException();
  7.         //内置比较器
  8.     Comparable<? super K> k = (Comparable<? super K>) key;
  9.         Entry<K,V> p = root;
  10.         while (p != null) {
  11.             int cmp = k.compareTo(p.key);
  12.             if (cmp < 0)
  13.                 p = p.left;
  14.             else if (cmp > 0)
  15.                 p = p.right;
  16.             else
  17.                 return p;
  18.         }
  19.         return null;
  20.     }

外部比较器查找节点:

  1.     final Entry<K,V> getEntryUsingComparator(Object key) {
  2.     K k = (K) key;
  3.         Comparator<? super K> cpr = comparator;
  4.         if (cpr != null) {
  5.             Entry<K,V> p = root;
  6.             while (p != null) {
  7.                 int cmp = cpr.compare(k, p.key);
  8.                 if (cmp < 0)
  9.                     p = p.left;
  10.                 else if (cmp > 0)
  11.                     p = p.right;
  12.                 else
  13.                     return p;
  14.             }
  15.         }
  16.         return null;
  17.     }

删除操作:

  1.   private void deleteEntry(Entry<K,V> p) {
  2.         modCount++;
  3.         size--;
  4.         //如果删除的节点有两个子节点;
  5.         if (p.left != null && p.right != null) {
  6.             Entry<K,V> s = successor (p);
  7.             p.key = s.key;
  8.             p.value = s.value;
  9.             p = s;
  10.         } 
  11.         //两个子节点的删除转化为了一个子节点的删除
  12.        //进行一个子节点的删除操作;
  13.         Entry<K,V> replacement = (p.left != null ? p.left : p.right);
  14.         
  15.        //如果有一个以上的节点;重新接上树枝; 
  16.         if (replacement != null) {
  17.             
  18.             replacement.parent = p.parent;
  19.             if (p.parent == null)
  20.                 root = replacement;
  21.             else if (p == p.parent.left)
  22.                 p.parent.left  = replacement;
  23.             else
  24.                 p.parent.right = replacement;
  25.             p.left = p.right = p.parent = null;
  26.             //如果删除位置的新节点是黑色的,那么会少一个黑节点,调整
  27.             if (p.color == BLACK)
  28.             //调整新的节点,即删除节点的子节点;
  29.                 fixAfterDeletion(replacement);
  30.         } else if (p.parent == null) { // return if we are the only node.
  31.             root = null;
  32.         } else {  
  33.             //如果没有子节点
  34.             //红色的节点要可以直接删除,黑色的话,必须要经过调整;
  35.             if (p.color == BLACK)
  36.                 fixAfterDeletion(p);
  37.            //删除操作;
  38.             if (p.parent != null) {
  39.                 if (p == p.parent.left)
  40.                     p.parent.left = null;
  41.                 else if (p == p.parent.right)
  42.                     p.parent.right = null;
  43.                 p.parent = null;
  44.             }
  45.         }
  46.     }

删除后的调整:

  1. private void fixAfterDeletion(Entry<K,V> x) {
  2.         // 如果节点是黑色的;那么要经过调整,如果是红色的,可以直接修改成为黑色的,结束循环;
  3.         while (x != root && colorOf(x) == BLACK)
  4.             // 判断被删除节点是左子树;
  5.             if (x == leftOf(parentOf(x))) {
  6.                 // 获得兄弟节点;
  7.                 Entry<K,V> sib = rightOf(parentOf(x));
  8.                 //兄弟节点是红色的
  9.                 if (colorOf(sib) == RED) {
  10.                     setColor(sib, BLACK);
  11.                     setColor(parentOf(x), RED);
  12.                     //开始旋转
  13.                     rotateLeft(parentOf(x));
  14.                     // 得到旋转后的新的兄弟节点;这个时候是黑色的
  15.                     sib = rightOf(parentOf(x));
  16.                 }
  17.                 //判断侄子的颜色;如果两个都是黑色的
  18.                 if (colorOf(leftOf(sib))  == BLACK &&
  19.                     colorOf(rightOf(sib)) == BLACK) {
  20.                     setColor(sib, RED);
  21.                     x = parentOf(x);
  22.                 } else {
  23.                     // 只有一个是黑色的
  24.                    // 如果是黑色的那个侄子位置不对,那么经过一次转换;
  25.                     if (colorOf(rightOf(sib)) == BLACK) {
  26.                         setColor(leftOf(sib), BLACK);
  27.                         setColor(sib, RED);
  28.                         rotateRight(sib);
  29.                         sib = rightOf(parentOf(x));
  30.                     }
  31.                     setColor(sib, colorOf(parentOf(x)));
  32.                     setColor(parentOf(x), BLACK);
  33.                     setColor(rightOf(sib), BLACK);
  34.                     rotateLeft(parentOf(x));
  35.                     x = root;
  36.                 }
  37.             } else {
  38.                 Entry<K,V> sib = leftOf(parentOf(x));
  39.                 if (colorOf(sib) == RED) {
  40.                     setColor(sib, BLACK);
  41.                     setColor(parentOf(x), RED);
  42.                     rotateRight(parentOf(x));
  43.                     sib = leftOf(parentOf(x));
  44.                 }
  45.                 if (colorOf(rightOf(sib)) == BLACK &&
  46.                     colorOf(leftOf(sib)) == BLACK) {
  47.                     setColor(sib, RED);
  48.                     x = parentOf(x);
  49.                 } else {
  50.                     if (colorOf(leftOf(sib)) == BLACK) {
  51.                         setColor(rightOf(sib), BLACK);
  52.                         setColor(sib, RED);
  53.                         rotateLeft(sib);
  54.                         sib = leftOf(parentOf(x));
  55.                     }
  56.                     setColor(sib, colorOf(parentOf(x)));
  57.                     setColor(parentOf(x), BLACK);
  58.                     setColor(leftOf(sib), BLACK);
  59.                     rotateRight(parentOf(x));
  60.                     x = root;
  61.                 }
  62.             }
  63.         }
  64.         //如果该节点不是黑色的,或者是根节点,那么把他染黑;
  65.         setColor(x, BLACK);
  66.     }
  1.  static <K,V> TreeMap.Entry<K,V> successor(Entry<K,V> t) {
  2.         //如果为null,则返回
  3.         if (t == null)
  4.             return null;
  5.         //如果大儿子存在,那么沿着这条路下去,找到其这个枝条中最小的节点
  6.         else if (t.right != null) {
  7.             Entry<K,V> p = t.right;
  8.             while (p.left != null)
  9.                 p = p.left;
  10.             return p;
  11.         } else {
  12.         //如果右边子树是空的,那么找到其长辈节点中间第一个大于他的
  13.             Entry<K,V> p = t.parent;
  14.             Entry<K,V> ch = t;
  15.             while (p != null && ch == p.right) {
  16.                 ch = p;
  17.                 p = p.parent;
  18.             }
  19.             return p;
  20.         }
  21.     }

我们再来看一下我们在获取其集合的时候的顺序:

  1.    static final class KeySet<E> extends AbstractSet<E> implements NavigableSet<E> {
  2.         private final NavigableMap<E, Object> m;
  3.         KeySet(NavigableMap<E,Object> map) { m = map; }
  4.         public Iterator<E> iterator() {
  5.             if (m instanceof TreeMap)
  6.                 return ((TreeMap<E,Object>)m).keyIterator();
  7.             else
  8.                 return (Iterator<E>)(((TreeMap.NavigableSubMap)m).keyIterator());
  9.         }
  10.         public Iterator<E> descendingIterator() {
  11.             if (m instanceof TreeMap)
  12.                 return ((TreeMap<E,Object>)m).descendingKeyIterator();
  13.             else
  14.                 return (Iterator<E>)(((TreeMap.NavigableSubMap)m).descendingKeyIterator());
  15.         }
  16.         public int size() { return m.size(); }
  17.         public boolean isEmpty() { return m.isEmpty(); }
  18.         public boolean contains(Object o) { return m.containsKey(o); }
  19.         public void clear() { m.clear(); }
  20.         public E lower(E e) { return m.lowerKey(e); }
  21.         public E floor(E e) { return m.floorKey(e); }
  22.         public E ceiling(E e) { return m.ceilingKey(e); }
  23.         public E higher(E e) { return m.higherKey(e); }
  24.         public E first() { return m.firstKey(); }
  25.         public E last() { return m.lastKey(); }
  26.         public Comparator<? super E> comparator() { return m.comparator(); }
  27.         public E pollFirst() {
  28.             Map.Entry<E,Object> e = m.pollFirstEntry();
  29.             return e == nullnull : e.getKey();
  30.         }
  31.         public E pollLast() {
  32.             Map.Entry<E,Object> e = m.pollLastEntry();
  33.             return e == nullnull : e.getKey();
  34.         }
  35.         public boolean remove(Object o) {
  36.             int oldSize = size();
  37.             m.remove(o);
  38.             return size() != oldSize;
  39.         }
  40.         public NavigableSet<E> subSet(E fromElement, boolean fromInclusive,
  41.                                       E toElement,   boolean toInclusive) {
  42.             return new TreeSet<E>(m.subMap(fromElement, fromInclusive,
  43.                                            toElement,   toInclusive));
  44.         }
  45.         public NavigableSet<E> headSet(E toElement, boolean inclusive) {
  46.             return new TreeSet<E>(m.headMap(toElement, inclusive));
  47.         }
  48.         public NavigableSet<E> tailSet(E fromElement, boolean inclusive) {
  49.             return new TreeSet<E>(m.tailMap(fromElement, inclusive));
  50.         }
  51.         public SortedSet<E> subSet(E fromElement, E toElement) {
  52.             return subSet(fromElement, true, toElement, false);
  53.         }
  54.         public SortedSet<E> headSet(E toElement) {
  55.             return headSet(toElement, false);
  56.         }
  57.         public SortedSet<E> tailSet(E fromElement) {
  58.             return tailSet(fromElement, true);
  59.         }
  60.         public NavigableSet<E> descendingSet() {
  61.             return new TreeSet(m.descendingMap());
  62.         }
  63.     }

这个是返回的set,他的查找排序是利用的迭代模式委托给了迭代器,我们看看他的迭代器实现:

  1.  final class KeyIterator extends PrivateEntryIterator<K> {
  2.         KeyIterator(Entry<K,V> first) {
  3.             super(first);
  4.         }
  5.         public K next() {
  6.             return nextEntry().key;
  7.         }
  8.     }

其中获取下一个nextEntry是:

  1. final Entry<K,V> nextEntry() {
  2.             Entry<K,V> e = next;
  3.             if (e == null)
  4.                 throw new NoSuchElementException();
  5.             if (modCount != expectedModCount)
  6.                 throw new ConcurrentModificationException();
  7.             next = successor(e);
  8.             lastReturned = e;
  9.             return e;
  10.         }

利用的successvor(),在开始的分析中我们知道,successor的查找,是通过了树的中序遍历的;

抱歉!评论已关闭.