15. 이진 검색 트리와 TreeSet

이진 검색 트리(binary search tree)
: 이진트리는 여러개의 노드가 서로 연결된 구조로, 이진 검색 트리는 부모노드의 왼쪽에는 부모노드의 값보다 작은 값의 자식노드를,
  오른쪽에는 큰 값의 자식노드를 저장하는 이진 트리이다. 
  정렬, 검색, 범위검색에 높은 성능을 보이는 자료구조이다.

 

예시 ) 이진 검색트리에 7,4,9,1,5의 순서로 값을 저장한다고 할 때 

첫번째로 저장되는 값(7)은 루트가 되고, 

두 번째 값(4)은 트리의 루트부터 시작해서 값의 크기를 비교하면서 트리를 따라 내려간다.

작은 값은 왼쪽에, 큰 값은 오른쪽에 저장되면서

결과적으로 왼쪽 마지막 레벨이 제일 가장 작은 값이 되고 오른쪽 마지막 레벨의 값이 제일 큰 값이 된다.  

 

* 이진 검색 트리의 특징

- 모든 노드는 최대 두 개의 자식노드를 가질 수 있다.
- 왼쪽 자식노드의 값은 부모노드의 값보다 작고 오른쪽 자식노드의 값은 부모노드의 값보다 커야한다.
- 노드의 추가 삭제에 시간이 걸린다.(순차적 저장x)
- 검색(범위검색)과 정렬에 유리하다.
- 중복된 값을 저장하지 못한다. 

 

TreeSet
: 이진 검색 트리의 형태로 데이터를 저장하는 컬렉션 클래스이다.
  TreeSet은 이진 검색 트리의 성능을 향상시킨 '레드-블랙 트리'로 구현되어있다. 
  (레드-블랙 트리 참조글 : https://code-lab1.tistory.com/62)
  Set인터페이스를 구현했으므로 데이터의 중복을 허용하지 않고, 저장순서를 유지하지도 않는다.

 

* TreeSet의 검색 예시 

import java.util.*;

class TreeSetEx {
	public static void main(String[] args) {
    	TreeSet set = new TreeSet();
        
        String from = "b";
        String to   = "d";
        
        set.add("abc");
        set.add("alien");
        set.add("bat");
        set.add("car");
        set.add("Car");
        set.add("disc");
        set.add("dance");
        set.add("dZZZZ");
        set.add("dzzzz");
        
        System.out.println(set);
        System.out.println(set.subSet(from,to));
        System.out.println(set.subSet(from,to + "zzz"));
        
    }
}
/*

실행결과 
1. [Car, abc, alien, bat, car, dZZZZ, dance, dzzzz]
2. [bat, car]
3. [bat, car, dZZZZ, dance, disc]

*/

* 주의할 점 

1. subSet()을 이용하여 범위검색을 할 때, 끝 범위는 포함되지 않는다.

2. 끝 범위까지 포함시키려고 한다면 끝 범위에 'zzz'와 같은 문자열을 붙이면 된다. 

(실행결과 3을 보면 끝범위가 "d"+"zzz"로 설정되어 "dZZZZ"는 출력, "dzzzz"는 미출력)

3. 정렬시 대소문자 구분을 하기 때문에 대소문자가 섞여있는경우 의도한 것과 다른 결과를 얻을 수 있다.

가능하면 대문자 또는 소문자로 통일하여 저장하는 것이 좋다. 

(문자열의 정렬우선순위 - 공백, 숫자, 대문자, 소문자(->오름차순일때, 내림차순은 반대 ))

 

* TreeSet 메소드

https://docs.oracle.com/en/java/javase/19/docs/api/java.base/java/util/TreeSet.html#method-summary

TreeSet (Java SE 19 & JDK 19)