TreeSet & TreeMap

TreeSet

TreeSet이란?

• Set의 성질을 그대로 상속받는 Tree 데이텉
• 이진 탐색 트리(Binary Search Tree)의 구조로 이루어져 있음
• 이진 탐색 트리 형태로 데이터를 저장하기에 nature ordering을 지원함
• 생성자 매개변수로 Comparator 객체를 입력해 정렬 방법을 임의로 지정 가능함

** 이진 탐색 트리(Binary Search Tree)

• 데이터 정렬, 검색에 높은 성능을 보이는 자료구조
• 데이터 추가, 삭제에는 시간이 소요됨

• TreeSet은 이진 탐색 트리 중에서도 성능을 향상시킨 레드-블랙 트리로 구현됨
  ⇒ 레드 블랙 트리 : 부모 노드보다 작은 값을 가지는 왼쪽 자식으로, 큰 값을 가지는 노드는 오른쪽 자식으로 배치하여 데이터 추가, 삭제 시 트리가 한 쪽으로 치우쳐지지 않도록 균형을 맞춤

TreeSet 생성

import java.util.TreeSet;

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

TreeSet 메서드

// 요소 값 추가
tset.add(5);
tset.add(3);
tset.add(9);
tset.add(7);

System.out.println(tset);    // [3, 5, 7, 9]

// 요소 값 삭제
tset.remove(5);
System.out.println(tset);    // [3, 7, 9]

// tree set의 크기
tset.size();

// tree set의 최소값
tset.first();

// tree set의 최대값
tset.last();

TreeSet의 내림차순 정렬
: Comparator 객체를 이용해 정렬 방법 설정

TreeSet<Integer> tset = new TreeSet<>(Comparator.reverseOrder());

tset.add(5);
tset.add(3);
tset.add(9);

System.out.println(tset);    // [9, 5, 3]

TreeMap

TreeMap이란?

• TreeSet과 동일하게 이진 탐색 트리 형태로 데이터 저장
• Map 특성을 사용하기 때문에 key와 value로 이루어진 entry 객체 형태로 저장
• key를 추가하면 정렬됨

TreeMap 생성

import java.util.TreeMap;

TreeMap<Integer, String> tmap = new TreeMap<>();

TreeMap 메서드

// 요소 값 추가
tmap.put(1, "부산");
tmap.put(2, "인천");
tmap.put(3, "대구");
tmap.put(4, "대전");
tmap.put(5, "광주");

System.out.println(tmap);    // {1=부산, 2=인천, 3=대구, 4=대전, 5=광주, 6=울산}

// 요소 값 삭제
tmap.remove(1);

// tree set 크기
tmap.size();

// 요소 값 찾기
tmap.get(1);    // 부산

// key 값만 추출(중복X)
tmap.keySet();