Collection - Tree

TreeSet

이진 트리를 기반으로한 Set Collection이다. TreeSet에 객체를 저장하면 자동으로 정렬되는데 이진탐색트리처럼 부모 노드값과 비교해 낮으면 왼쪽 자식노드, 높으면 오른쪽 자식 노드에 저장한다.

TreeSet<E> treeSet = new TreeSet<E>();

리턴타입	메소드	설명
E	first()	제일 낮은 객체를 리턴
E	last()	제일 높은 객체를 리턴
E	lower(E e)	주어진 객체보다 바로 아래 객체 리턴
E	higher(E e)	주어진 객체보다 바로 위 객체 리턴
E	floor(E e)	주어진 객체와 동등한 객체가 있으면 리턴, 만약 없다면 바로 아래의 객체 리턴
E	ceiling(E e)	주어진 객체와 동등한 객체가 있으면 리턴, 만약 없다면 바로 위의 객체 리턴
E	pollFirst()	제일 낮은 객체 꺼내오고 Collection에서 제거
E	pollLst()	제일 높은 객체 꺼내오고 Collection에서 제거

TreeSet<Integer> scores = new TreeSet<Integer>();
scores.add(new Integer(87));
scores.add(new Integer(95));
scores.add(new Integer(90));

System.out.println("first() : "+ scores.first());

리턴타입	메소드	설명
Iterator\	descendingIterator()	내림차순으로 정렬된 Iterator 리턴
NavigableSet\	descendingSet()	내림차순으로 정렬된 navigableSet 리턴

NavigableSet<Integer> descendingSet = treeSet.descendingSet();

만약 오름차순 정렬을 하고 싶다면, descendingSet()을 두번 호출하면된다.

NavigableSet<Integer> ascendingSet = descendingSet.descendingSet();

리턴타입	메소드	설명
NavigableSet\	headSet( E toElement, boolean inclusive)	주어진 객체보다 낮은 객체들을 NavigableSet으로 리턴 주어진 객체 포함 여부는 두 번째 boolean값에 따라 달라진다.
NavigableSet\	tailSet( E fromElement, boolean inclusive)	주어진 객체보다 큰 객체들을 NavigableSet으로 리턴 주어진 객체 포함 여부는 두 번째 boolean값에 따라 달라진다.
NavigableSet\	subSet( E fromElement, boolean fromInclusive, E toElement, boolean toInclusive)	시작과 끝으로 주어진 객체 사이의 객체들을 NavigableSet으로 리턴

TreeSet<String> treeSet = new TreeSet<String>();
treeSet.add("banana");
treeSet.add("apple");
treeSet.add("grape");
treeSet.add("cherry");
treeSet.add("strawberry");

NavigableSet<String> rangeSet = treeSet.subSet("c", true, "f", true);
for(String word : rangeSet){
  System.out.println(word); // cherry
}

TreeMap

TreeMap은 이진 트리를 기반으로 한 Map Collection이다. TreeSet과의 차이점은 키와 값이 저장된 Map.Entry를 저장한다는 점이다. 키값을 비교해서 자동으로 정렬된다.

TreeMap<K, V> treeMap = new TreeMap<K, V>();

Map 인터페이스 타입 변수에 대입해도되지만 TreeMap 클래스 타입으로 대입한 이유는 특정 객체를 찾거나 범위 검색과 관련된 메소드를 사용하기 위해서이다.

리턴타입	메소드	설명
Map.Entry	firstEntry()	제일 낮은 Map.Entry 리턴
Map.Entry	lastEntry()	제일 높은 Map.Entry 리턴
Map.Entry	lowerEntry(K key)	주어진 키보다 바로 아래 Map.Entry 리턴
Map.Entry	higherEntry(K key)	주어진 키보다 바로 위 Map.Entry 리턴
Map.Entry	flooreEntry(K key)	주어진 키와 같은 키가 있으면 해당 Map.Entry 리턴 없다면 주어진 키 바로 아래 Map.Entry 리턴
Map.Entry	ceilingEntry(K key)	주어진 키와 같은 키가 있으면 해당 Map.Entry 리턴 없다면 주어진 키 바로 위 Map.Entry 리턴
Map.Entry	pollFirstEntry()	제일 낮은 Map.Entry 리턴하고 Collection에서 제거
Map.Entry	pollLastEntry()	제일 높은 Map.Entry 리턴하고 Collection에서 제거

리턴타입	메소드	설명
NavigableSet\	descendingKeySet()	내림차순으로 정렬된 키의 NavigableSet 리턴
NavigableMap\	descendingMap()	내림차순으로 정렬된 Map.Entry의 NavigableSet 리턴

오름차순 정렬하고 싶다면, descendingMap()을 두번 호출하면된다.

리턴타입	메소드	설명
NavigableMap\	headMap( K toKey, boolean inclusive)	주어진 키보다 낮은 Map.Entry를 NavigableMap으로 리턴 주어진 객체 포함 여부는 두 번째 boolean값에 따라 달라진다.
NavigableMap\	tailMap( K fromKey, boolean inclusive)	주어진 키보다 높은 Map.Entry를 NavigableMap으로 리턴 주어진 객체 포함 여부는 두 번째 boolean값에 따라 달라진다.
NavigableMap\	subMap( K fromKey, boolean fromInclusive, K toKey, boolean toInclusive)	시작과 끝 사이의 Map.Entry를 NavigableMap으로 리턴

TreeMap<String,Integer> TreeMap = new TreeMap<String,Integer>();
TreeMap.put("banana", new Integer(10));
TreeMap.put("apple", new Integer(50));
TreeMap.put("grape", new Integer(30));
TreeMap.put("cherry", new Integer(20));
TreeMap.put("strawberry", new Integer(40));

NavigableMap<String,Integer> rangeMap = TreeMap.subMap("c", true, "f", true);
for(Map.Entry<String,Integer> entry : rangeMap.entrySet()){
    System.out.println(entry.getKey()); // cherry
}

Comparable, Comparator

TreeSet과 TreeMap은 정렬을 위해 java.lang.Comparable 을 구현한 객체를 요구한다. 만약 Comparable을 구현하고 있지 않을 경우에는 저장하는 순간 ClassCastException이 발생한다. 이때, 생성자의 매개 값으로 Comparator를 제공하면 Comparable이 없는 객체도 정렬시킬 수 있다.

혹은 사용자 정의 클래스에서 compareTo() 메소드를 오버라이딩하여 구현하면된다.

Comparable

public class Fruit implemets Comparable<Fruit>{
  public String name;
  public Integer stock;
  ...
  @Override
  public int compareTo(Fruit o){
    // 로직
  }
}

Comparator

public class DescendingComparator implements Comparator<Fruit>{
  @Override
  public int compare(Fruit o1, Fruit o2){
    // 로직
  }
}

TreeSet<Fruit> treeSet = new TreeSet<Fruit>(new DescendingComparator())