# Collection - Tree

## TreeSet

[이진 트리](https://github.com/dh00023/TIL/blob/master/algorithm/2018-05-11-algorithm-tree.md)를 기반으로한 Set Collection이다. TreeSet에 객체를 저장하면 자동으로 정렬되는데 [이진탐색트리](https://github.com/dh00023/TIL/blob/master/algorithm/2018-05-21-algorithm-bst.md)처럼 부모 노드값과 비교해 낮으면 왼쪽 자식노드, 높으면 오른쪽 자식 노드에 저장한다.

```java
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에서 제거               |

```java
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 리턴 |

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

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

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

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

```java
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를 저장한다는 점이다. 키값을 비교해서 자동으로 정렬된다.

```java
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)  | <p>주어진 키와 같은 키가 있으면 해당 Map.Entry 리턴<br>없다면 주어진 키 바로 아래 Map.Entry 리턴</p> |
| Map.Entry | ceilingEntry(K key) | <p>주어진 키와 같은 키가 있으면 해당 Map.Entry 리턴<br>없다면 주어진 키 바로 위 Map.Entry 리턴</p>  |
| 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)                                    | <p>주어진 키보다 낮은 Map.Entry를 NavigableMap으로 리턴 <br>주어진 객체 포함 여부는 두 번째 boolean값에 따라 달라진다.</p> |
| NavigableMap\\ | tailMap( K fromKey, boolean inclusive)                                  | <p>주어진 키보다 높은 Map.Entry를 NavigableMap으로 리턴 <br>주어진 객체 포함 여부는 두 번째 boolean값에 따라 달라진다.</p> |
| NavigableMap\\ | subMap( K fromKey, boolean fromInclusive, K toKey, boolean toInclusive) | <p>시작과 끝 사이의 Map.Entry를 NavigableMap으로 리턴 <br></p>                                       |

```java
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

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

### Comparator

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

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