在上一节的分析中,我们已经对红黑色的实现和操作进行了分析,我们可以看见红黑树是一颗高度平衡的数;
TreeMap的实现也是利用的红黑树,我们来看代码:
TreeMap的实现也是利用的红黑树,我们来看代码:
在TreeMap中包含着一个根结点:
- private transient Entry<K,V> root = null;
这个Entry代码如下:
- static final class Entry<K,V> implements Map.Entry<K,V> {
- K key;
- V value;
- //指向小儿子
- Entry<K,V> left = null;
- //指向大儿子
- Entry<K,V> right = null;
- //指向父亲
- Entry<K,V> parent;
- //颜色默认为黑色
- boolean color = BLACK;
- Entry(K key, V value, Entry<K,V> parent) {
- this.key = key;
- this.value = value;
- this.parent = parent;
- }
- public K getKey() {
- return key;
- }
- public V getValue() {
- return value;
- }
- 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;
- }
- public String toString() {
- return key + "=" + value;
- }
- }
废话不多说,我们来看一下他的插入实现:
- public V put(K key, V value) {
- Entry<K,V> t = root;
- //如果树是空树
- if (t == null) {
- //那么树根节点就是节点
- root = new Entry<K,V>(key, value, null);
- size = 1;
- modCount++;
- return null;
- }
- int cmp;
- Entry<K,V> parent;
- //否则利用提供的比较器进行比较
- 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
- //如果已经有这个key,那么修改key,并且什么都可以 不修改了
- return t.setValue(value);
- } while (t != null); //知道找到叶子节点;
- }
- else {
- if (key == null)
- throw new NullPointerException();
- //如果没有提供外部的比较器,那么就利用内置的比较器
- Comparable<? super K> k = (Comparable<? super K>) 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);
- }
- //生成一个叶子节点,准备进行加入
- Entry<K,V> e = new Entry<K,V>(key, value, parent);
- //利用最后的判断,将这个节点变成该叶子节点的儿子;
- if (cmp < 0)
- parent.left = e;
- else
- parent.right = e;
- //由于有可能破坏了红黑树的规则,现在进行调整;
- fixAfterInsertion(e);
- size++;
- modCount++;
- return null;
- }
- private void fixAfterInsertion(Entry<K,V> x) {
- //首先将该新增节点染红,叶子节点(null)是黑色的;
- 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)));
- }
- }
- }
- //冲突会一直追溯到跟,把跟染黑,不违背根节点是黑色的特性,并且使得所有的树枝的黑色节点因此加1,冲突解决;
- root.color = BLACK;
- }
看完了增加,我们再来看看删除
- 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) {
- if (comparator != null)
- //利用外部比较器
- return getEntryUsingComparator(key);
- if (key == null)
- throw new NullPointerException();
- //内置比较器
- Comparable<? super K> k = (Comparable<? super K>) key;
- Entry<K,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;
- }
外部比较器查找节点:
- final Entry<K,V> getEntryUsingComparator(Object key) {
- K k = (K) key;
- Comparator<? super K> cpr = comparator;
- if (cpr != null) {
- Entry<K,V> p = root;
- while (p != null) {
- int cmp = cpr.compare(k, p.key);
- if (cmp < 0)
- p = p.left;
- else if (cmp > 0)
- p = p.right;
- else
- return p;
- }
- }
- return null;
- }
删除操作:
- private void deleteEntry(Entry<K,V> p) {
- modCount++;
- size--;
- //如果删除的节点有两个子节点;
- if (p.left != null && p.right != null) {
- Entry<K,V> s = successor (p);
- p.key = s.key;
- p.value = s.value;
- p = s;
- }
- //两个子节点的删除转化为了一个子节点的删除
- //进行一个子节点的删除操作;
- Entry<K,V> replacement = (p.left != null ? p.left : p.right);
- //如果有一个以上的节点;重新接上树枝;
- if (replacement != null) {
- 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;
- p.left = p.right = p.parent = null;
- //如果删除位置的新节点是黑色的,那么会少一个黑节点,调整
- if (p.color == BLACK)
- //调整新的节点,即删除节点的子节点;
- fixAfterDeletion(replacement);
- } else if (p.parent == null) { // return if we are the only node.
- root = null;
- } else {
- //如果没有子节点
- //红色的节点要可以直接删除,黑色的话,必须要经过调整;
- 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;
- }
- }
- }
删除后的调整:
- 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) {
- 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 {
- 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) {
- //如果为null,则返回
- 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;
- }
- }
我们再来看一下我们在获取其集合的时候的顺序:
- static final class KeySet<E> extends AbstractSet<E> implements NavigableSet<E> {
- private final NavigableMap<E, Object> m;
- KeySet(NavigableMap<E,Object> map) { m = map; }
- public Iterator<E> iterator() {
- if (m instanceof TreeMap)
- return ((TreeMap<E,Object>)m).keyIterator();
- else
- return (Iterator<E>)(((TreeMap.NavigableSubMap)m).keyIterator());
- }
- public Iterator<E> descendingIterator() {
- if (m instanceof TreeMap)
- return ((TreeMap<E,Object>)m).descendingKeyIterator();
- else
- return (Iterator<E>)(((TreeMap.NavigableSubMap)m).descendingKeyIterator());
- }
- public int size() { return m.size(); }
- public boolean isEmpty() { return m.isEmpty(); }
- public boolean contains(Object o) { return m.containsKey(o); }
- public void clear() { m.clear(); }
- public E lower(E e) { return m.lowerKey(e); }
- public E floor(E e) { return m.floorKey(e); }
- public E ceiling(E e) { return m.ceilingKey(e); }
- public E higher(E e) { return m.higherKey(e); }
- public E first() { return m.firstKey(); }
- public E last() { return m.lastKey(); }
- public Comparator<? super E> comparator() { return m.comparator(); }
- public E pollFirst() {
- Map.Entry<E,Object> e = m.pollFirstEntry();
- return e == null? null : e.getKey();
- }
- public E pollLast() {
- Map.Entry<E,Object> e = m.pollLastEntry();
- return e == null? null : e.getKey();
- }
- public boolean remove(Object o) {
- int oldSize = size();
- m.remove(o);
- return size() != oldSize;
- }
- public NavigableSet<E> subSet(E fromElement, boolean fromInclusive,
- E toElement, boolean toInclusive) {
- return new TreeSet<E>(m.subMap(fromElement, fromInclusive,
- toElement, toInclusive));
- }
- public NavigableSet<E> headSet(E toElement, boolean inclusive) {
- return new TreeSet<E>(m.headMap(toElement, inclusive));
- }
- public NavigableSet<E> tailSet(E fromElement, boolean inclusive) {
- return new TreeSet<E>(m.tailMap(fromElement, inclusive));
- }
- public SortedSet<E> subSet(E fromElement, E toElement) {
- return subSet(fromElement, true, toElement, false);
- }
- public SortedSet<E> headSet(E toElement) {
- return headSet(toElement, false);
- }
- public SortedSet<E> tailSet(E fromElement) {
- return tailSet(fromElement, true);
- }
- public NavigableSet<E> descendingSet() {
- return new TreeSet(m.descendingMap());
- }
- }
这个是返回的set,他的查找排序是利用的迭代模式委托给了迭代器,我们看看他的迭代器实现:
- final class KeyIterator extends PrivateEntryIterator<K> {
- KeyIterator(Entry<K,V> first) {
- super(first);
- }
- public K next() {
- return nextEntry().key;
- }
- }
其中获取下一个nextEntry是:
- final Entry<K,V> nextEntry() {
- Entry<K,V> e = next;
- if (e == null)
- throw new NoSuchElementException();
- if (modCount != expectedModCount)
- throw new ConcurrentModificationException();
- next = successor(e);
- lastReturned = e;
- return e;
- }
利用的successvor(),在开始的分析中我们知道,successor的查找,是通过了树的中序遍历的;