11-39~45 TreeSet

TreeSet

バイナリ検索ツリーとして実装されます.コレクションクラス

は、範囲の検索とソートに役立ちます.

バイナリツリーのすべてのノードには、最大2つのサブノードがあります.
(各ノードはツリー形式で接続されています.リンクリストのバリエーション)

バイナリ検索ツリー

左側に格納値は

の親より小さく、右側の値は

より大きい.
データが多ければ多いほど、追加と削除の時間が長くなります.

データストレージプロシージャboolean add(オブジェクトo)

addメソッド内でcompare()を呼び出して比較して保存
(cf.HashSetとequals()とHashCode()の比較)

主な作成者と方法

TreeSet(Comparator Comp)-Comparator提供比較規格

TreeSet()-ストレージ・オブジェクトを使用するCompareable(デフォルトの比較基準)

(比較基準なし)
例1

public static void main(String[] args){
   Set set = new TreeSet();	// 정렬 필요 없음. 기본 생성자.
   // Set set = new HashSet();	// 정렬 필요

   for(int i = 0; set.size() < 6; i++) {
       int num = (int)(Math.random()*45) + 1;
       set.add(num);	// set.add(new Integer(num)); 
       // Integer class가 가진 정렬기준을 이용하므로 TreeSet(); 기본 생성자 선언 OK
   }
   System.out.println(set);	// TreeSet은 정렬 O
}

比較基準の例-オブジェクトに比較基準があるかどうかにかかわらず、TreeSetの比較基準を指定する必要があります.
比較基準は、例2−TreeSetのために提供される.

public class practice {
  public static void main(String[] args){
      // Test class에 비교 기준 없으므로 TestComp()와 같이 비교 기준 제공해야 함
      Set set = new TreeSet(new TestComp());	// 생성자에 정렬기준 제공
      set.add(new Test());
      set.add(new Test());
      set.add(new Test());	
      System.out.println(set);
  }
}
class Test {}	// 비교 기준이 없음.

class TestComp implements Comparator{
  @Override
  public int compare(Object o1, Object o2) {
      return 1;	// return 0;, return -1;
  }
}

例3-オブジェクトに比較条件がある場合:

public class practice {
  public static void main(String[] args){
      Set set = new TreeSet(); // Test 객체가 비교 기준을 가진 경우 기본 생성자 선언 OK
      set.add(new Test());
      set.add(new Test());
      set.add(new Test());	
      System.out.println(set);
  }
}
class Test implements Comparable{
  @Override
  public int compareTo(Object o) {
      return 1;	// return 0;, return -1;
  }
}

有効範囲検索

subSet(), headSet(), tailSet()

headSet(50):左側、尾部(50):右側