概要-TreeSet要素を追加して削除する

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層-2は20の右サブノードであり、削除時にルートをたどって検索するため、-2はずっと左へ検索し、最後に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;
}

 
追加時にコード略に触れる