JAVA 개발자 수업 29일차 - TreeSet, TreeMap

1. TreeSet

2. TreeMap

---

1. TreeSet

[정의]

- 이진 검색 트리(binary search tree)라는 자료구조의 형태로 저장하는 컬렉션 클래스이다.

- 이진 검색 트리는 정렬, 검색에 높은 성능을 보이는 자료구조이다.

- TreeSet은 이진 검색트리의 성능을 향상 시킨 '레드-블랙 트리(Red-Black tree)'로 구현 되어있다.

- Set인터페이스를 구현했으므로, 중복된 데이터의 저장을 허용하지 않으며, 정렬된 위치에 저장하므로 저장 순서를 유지하지도 않는다.

 

[이진 검색 트리(binary search tree)]

- 모든 노드는 최대 2개의 자식노드를 가질 수 있다.

- 왼쪽 자식 노드의 값은 부모노드의 값보다 작고 오른쪽 자식 노드의 값은 부모노드의 값보다 커야한다.

- 노드의 추가/삭제에 시간이 걸린다(순차적으로 저장 안하기 때문이다.)

- 검색과 정렬에 유리하다.

- 중복 값 저장 X

출처: https://coding-factory.tistory.com/555 레드-블랙 트리(Red-Black tree)

 

[TreeSet 예제]

TreeSet<Integer> set = new TreeSet<Integer>();

set.add(10);
set.add(40);
set.add(20);
set.add(30);
set.add(50);
set.add(10); //Set형태라서 중복값 X

System.out.println(set.size());

//어제도 배웠지만 set은 get메소드가 없다! -> 대신 Iterator제공
Iterator<Integer> iter = set.iterator();

while(iter.hasNext()) {
    System.out.print(iter.next());
}

//TreeSet 메소드
System.out.println(set.first()); //최솟값
System.out.println(set.last()); //최댓값
System.out.println(set.headSet(30)); //처음 ~ 30 전까지
System.out.println(set.tailSet(30)); //30 ~ 끝까지
System.out.println(set.subSet(30, 50)); //30 ~ 50 전까지


//OUTPUT
5 //size()

10 20 30 40 50

10
50
[10, 20]
[30, 40, 50]
[30, 40]

----> iterator로 확인 결과 순차정렬이 된걸 알 수 있다.

 

2. TreeMap

[정의]

- TreeSet과 마찬가지로 이진 검색 트리(binary search tree)구조로 저장하는 컬렉션 클래스이다.

- TreeSet은 값만 저장하지만, TreeMap은 키, 값이 저장된 Map.Entry를 저장한다. 이것이 TreeSet과의 차이점이다.

- TreeMap에 객체를 저장하면 자동으로 정렬되는데, 키는 저장과 동시에 자동 오름차순으로 정렬되고

  숫자 타입일 경우에는 값으로, 문자열 타입일 경우에는 유니코드로 정렬합니다.

- 정렬 순서는 기본적으로 부모 키값과 비교해서 키 값이 낮은 것은 왼쪽 자식 노드 키값이 높은 것은 오른쪽 자식 노드      에 Map.Etnry 객체를 저장합니다

 

[TreeMap 예제]

TreeMap<String, String> map = new TreeMap<String, String>();

map.put("one", "하나");
map.put("two", "둘");
map.put("three", "셋");
map.put("four", "넷");
map.put("five", "다섯");

System.out.println(map.size());
System.out.println(map);

System.out.println(map.get("three"));

System.out.println();
System.out.println(map.firstKey()); //처음 Key값
System.out.println(map.lastKey());  //마지막 Key값
System.out.println(map.firstEntry()); //처음 Entry값
System.out.println(map.lastEntry()); //마지막 Entry값
System.out.println(map.headMap("o")); //알파벳 o부터 시작하는 값부터~ 
System.out.println(map.tailMap("o")); //위의값 반대
System.out.println(map.subMap("f", "o"));


//OUTPUT
5 //size()
{five=다섯, four=넷, one=하나, three=셋, two=둘}
셋

five
two
five=다섯
two=둘
{five=다섯, four=넷}
{one=하나, three=셋, two=둘}
{five=다섯, four=넷}

---

MEMO>

 

# 컬렉션(List, Set, Map)을 오늘로써 전부 다 배웠다. 아직 전부 숙지, 이해는 안되지만 기본적으로 ArrayList와 HashMap, HashSet 이 가장 많이 쓰이는 3가지는 다른 컬렉션보다 무조건 더 깊게 공부하자!!

 

# 자바 수업이 다음주에 끝나고..... 이제 오라클수업이다.. 복습철저히 하면서 남은 프로젝트도 빨리 마무리 하자!!