??? 知道TreeSet的backing map是TreeMap,看程序:
import java.util.TreeSet; class R implements Comparable<Object> { int count; public R(int count) { this.count = count; } public String toString() { return "R(count:" + count + ")"; } public boolean equals(Object o) { if (o instanceof R) { R r = (R) o; if (this.count == r.count) return true; } return false; } public int compareTo(Object o) { R r = (R) o; if (this.count > r.count) return 1; else if (this.count == r.count) return 0; else return -1; } } public class TestTreeSetError { /** * @param args */ public static void main(String[] args) { // TODO Auto-generated method stub TreeSet<R> ts = new TreeSet<R>(); ts.add(new R(5)); ts.add(new R(-3)); ts.add(new R(9)); ts.add(new R(-2)); System.out.println("1 = " + ts); R first = (R) ts.first(); first.count = 20; System.out.println("2 = " + ts); R last = (R) ts.last(); last.count = -2; System.out.println("3 = " + ts); System.out.println(ts.remove(new R(-2))); System.out.println(ts); System.out.println(ts.remove(new R(5))); System.out.println(ts); System.out.println(ts.remove(new R(-2))); System.out.println(ts); } }
?
树添加修改稳定之后,形成的红黑树是这样的:
????????? 5
20????????????? -2
????? -2
第二层-2是20的右子节点,因为删除时循根搜索,-2一直往左路搜,{zh1}搜到20左子节点为空,所以删除失败,待5删除之后,重新平衡了树结构:
???? -2
20????? -2
因此-2就能被删除
?
这其中涉及到了TreeSet中的remove:
public boolean remove(Object o) { return m.remove(o)==PRESENT; }
?
TreeMap中的remove:
public V remove(Object key) { Entry<K,V> p = getEntry(key); if (p == null) return null; V oldValue = p.value; deleteEntry(p); return oldValue; }
?
最终到TreeMap的getEntry:
final Entry<K,V> getEntry(Object key) { // Offload comparator-based version for sake of performance 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; }?
? 添加时涉及到代码略