TreeSet / TreeMap

  • 검색 기능을 강화시킨 컬렉션
  • 이진트리를 사용하기 때문에 검색속도가 향상된다.
    • 왼쪽 자식 노드 : 부모보다 작은 값
    • 오른쪽 자식 노드 : 부모 보다 큰 값
  • 이진트리 정렬
    • 오름차순(작->큰) : 왼쪽노드 - 부모노드 - 오른쪽노드
    • 내림차순(큰->작) : 오른쪽노드 - 부모노드 - 왼쪽노드

TreeSet 활용

    1. TreeSet 객체를 생성
TreeSet<Integer> scores = new TreeSet<>(); //타입추론 
    1. 새로운 요소 추가 ---> 이진트리가 확장되고 ----> 즉, 자동으로 정렬이 된다!
scores.add(75);
scores.add(95);
....
    1. TreeSet안에 구성된 이진트리를 탐색하는 메소드
//가장 작은 점수
scores.first(); 
//가장 큰 점수
scores.last();
//지정된 값(95)보다 작은 바로 아래의 하나의 값을 반환 ( < )
scores.lower(95);
// 지정된 값(95)보다 큰 바로 아래의 하나의 값을 반환 ( > )
scores.higher(95); 
// 지정된 값(95)과 같고, 바로 아래 작은 하나의 값을 반환 ( <= )
scores.floor(95); 
// 지정된 값(95)과 같거나, 바로 아래 큰 하나의 값을 반환 ( >= )
scores.ceiling(95); 

TreeSet의 범위 검색 메소드

//범위검색 메소드의 활용(TreeSet.subSet() 메소드)
NavigableSet<String> rangeSet = 
// 요소 값을 완전하게 지정해줘야한다. -> "c", true, "f", true 는 값이 제대로 출력이 안됨 
	treeset.subSet("cherry", true, "forever", true);	
for(String word : rangeSet) {
	log.info(word);
}

TreeSet의 순회

  • Enhanced For를 통한 순회
//Set객체를 통해 keySet으로 key값을 가져온다
Set<Integer> keySet = scores.keySet();
for(int key : keySet){
	String val = scores.get(key);
	log.info(key + " - " + val);
}
  • entrySet 을 통한 Set 객체 순회
Set<Entry<Integer, String>> entrySet = scores.entrySet();
for(Entry<Integer, String> element : entrySet) {
	int key = element.getKey();
	String val = element.getValue();
	log.info(key + " - " + val);
}
  • forEach 람다식 순회
// void accept(T t, U u); 타겟타입의 시그니처 메소드 확인 
scores.forEach( (k, v) -> { log.info(k + " - " + v);} );

descendingSet / ascendingSet

  • descendingSet
//TreeSet.descendingSet() 메소드로, 내림차순으로 정렬된 Set객체를 반환
NavigableSet<Integer> descendingSet = scores.descendingSet();
for(int score : descendingSet) {
	log.info(score + " ");
}
  • ascendingSet
NavigableSet<Integer> ascendingSet = descendingSet.descendingSet();
for(int score : ascendingSet) {
	log.info(score + " ");
}

TreeMap 활용

    1. TreeMap<Key, Value> 객체 생성
TreeMap<Integer, String> scores = new TreeMap<>();
    1. 새로운 요소를 추가(Key/Value쌍으로 넣어도, 실제 저장되는 요소의 타입은 Map.Entry 객체임)
scores.put(87, "홍길동");
scores.put(98, "이동수");
    1. 이진트리를 탐색하는 다양한 메소드
//키값이 가장 낮은 요소 획득 
entry = scores.firstEntry();
//키값이 가장 높은 요소 획득 
entry = scores.lastEntry();
//지정된 값(95)보다 작은 바로 아래의 하나의 값을 반환 ( < )
entry = scores.lowerEntry(95);
// 지정된 값(95)보다 큰 바로 아래의 하나의 값을 반환 ( > )
entry = scores.higherEntry(95);
// 지정된 값(95)과 같고, 바로 아래 작은 하나의 값을 반환 ( <= )
entry = scores.floorEntry(95);
// 지정된 값(95)과 같거나, 바로 아래 큰 하나의 값을 반환 ( >= )
entry = scores.ceilingEntry(85);
  • TreeMap 순회 방법. Enhanced For 이용
    ---> Map 객체는 Iterable 하지 않기 때문에 enhanced for 사용 불가
    ---> 따라서 Set 객체를 통해 keySet, entrySet으로 순회
Set<Integer> keySet = scores.keySet();
for(int key : keySet) {
   String val = scores.get(key);
   log.info(key + " #- " + val);
}//enhanced for
Set<Entry<Integer, String>> entrySet = scores.entrySet();
for(Entry<Integer, String> element : entrySet) {
   int key = element.getKey();
   String val = element.getValue();
   log.info(key + " !- " + val);
}//enhanced for
  • TreeMap 순회 방법. forEach 이용
// void accept(T t, U u); 타겟타입의 시그니처 메소드 확인 
scores.forEach( (k, v) -> { log.info(k + " @ - " + v);} );

TreeSet과 TreeMap의 차이점

  • TreeSet은 기본적으로 Set 객체이므로 get()으로 값을 얻어올 수 없다.
    --> 따라서 Iterator를 통해 값을 얻어야한다.
    하지만, TreeMap은 Map 객체이므로 key값을 통해 value값을 얻어낼 수 있다.( get(key) )

  • TreeMap은 키와 값이 저장된 Map.Entry를 저장한다는점
    TreeMap에 객체를 저장하면 자동으로 정렬되는데, 기본적으로 부모 키값과 비교해서 키 값이 낮은 것은 왼쪽 노드에, 키 값이 높은 것은 오른쪽 노드에 Map.Entry에 저장

TreeSet

  • 정렬 순서 유지
  • Value만 존재
  • Value 존재여부 판별가능

TreeMap

  • 정렬 순서 유지
  • Key, Value 존재
  • get(key)으로 Value값 얻기 가능

Comparable / Comparator

  • TreeSet의 객체와 TreeMap의 키는 저장과 동시에 자동 오름차순으로 정렬된다.
  • TreeSet과 TreeMap은 정렬을 위해 java.lang.Comparable 구현객체를 요구한다. (implements Comparable 하라는 뜻)
  • Comparable에는 compareTo() 메소드가 정의되어 있기 때문에 사용자 정의 클래스에서는 이 메소드를 오버리이딩하여 다음과 같이 리턴 값을 만들어 내야 한다.

    1) if (오른쪽이 큰 경우) --> return -음수
    2) if (같으면) --> return 0
    3) if (왼쪽이 큰 경우) --> return +양수

재정의한 compareTo() 메소드에서

  • return 값이 0이나 음수이면 자리바꿈을 하지않고(x)
  • return 값이 양수이면 자리바꿈 수행(O)
//TreeSet에 요소 추가
treeSet.add(45);
treeSet.add(25);
treeSet.add(31);
  1. treeSet에 요소가 추가되기 전 들어있는 값은 Null
  2. Null과 추가될 45를 비교
  3. Null 보다 45가 크기때문에(오른쪽이 큰 경우) 음수 리턴
    --> (Null < 45) : return 음수
  4. 따라서, 자리바꿈을 하지 않고 다음요소 비교
  5. 45 와 추가될 25 비교
  6. 45 보다 25가 작기때문에(왼쪽이 큰 경우) 양수 리턴
    --> (45 > 25) : return 양수
  7. 따라서 자리바꿈을 수행해서 현재 요소는 [ 25 , 45 ]
  8. 45 와 추가될 31 비교
  9. 45보다 31이 작기때문에(왼쪽이 큰 경우) 양수 리턴
    --> (45 > 31) : return 양수
  10. 따라서 자리바꿈을 수행해서 현재 요소는 [25, 31, 45]

0개의 댓글