2020-03-24-tree.md

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<E>	descendingIterator()	내림차순으로 정렬된 Iterator 리턴
NavigableSet<E>	descendingSet()	내림차순으로 정렬된 navigableSet 리턴

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

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

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

리턴타입	메소드	설명
NavigableSet<E>	headSet( E toElement, boolean inclusive)	주어진 객체보다 낮은 객체들을 NavigableSet으로 리턴 주어진 객체 포함 여부는 두 번째 boolean값에 따라 달라진다.
NavigableSet<E>	tailSet( E fromElement, boolean inclusive)	주어진 객체보다 큰 객체들을 NavigableSet으로 리턴 주어진 객체 포함 여부는 두 번째 boolean값에 따라 달라진다.
NavigableSet<E>	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<K,V>	firstEntry()	제일 낮은 Map.Entry 리턴
Map.Entry<K,V>	lastEntry()	제일 높은 Map.Entry 리턴
Map.Entry<K,V>	lowerEntry(K key)	주어진 키보다 바로 아래 Map.Entry 리턴
Map.Entry<K,V>	higherEntry(K key)	주어진 키보다 바로 위 Map.Entry 리턴
Map.Entry<K,V>	flooreEntry(K key)	주어진 키와 같은 키가 있으면 해당 Map.Entry 리턴 없다면 주어진 키 바로 아래 Map.Entry 리턴
Map.Entry<K,V>	ceilingEntry(K key)	주어진 키와 같은 키가 있으면 해당 Map.Entry 리턴 없다면 주어진 키 바로 위 Map.Entry 리턴
Map.Entry<K,V>	pollFirstEntry()	제일 낮은 Map.Entry 리턴하고 Collection에서 제거
Map.Entry<K,V>	pollLastEntry()	제일 높은 Map.Entry 리턴하고 Collection에서 제거

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

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

리턴타입	메소드	설명
NavigableMap<K, V>	headMap( K toKey, boolean inclusive)	주어진 키보다 낮은 Map.Entry를 NavigableMap으로 리턴 주어진 객체 포함 여부는 두 번째 boolean값에 따라 달라진다.
NavigableMap<K, V>	tailMap( K fromKey, boolean inclusive)	주어진 키보다 높은 Map.Entry를 NavigableMap으로 리턴 주어진 객체 포함 여부는 두 번째 boolean값에 따라 달라진다.
NavigableMap<K, V>	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())