TreeSet

1. TreeSet

---

이진 검색 트리(Binary Search Tree) 형태로 데이터를 저장하는 컬렉션 클래스. 정렬, 검색/범위검색에 높은 성능을 보이며 이진 검색 트리의 성능을 향상시킨 Red-Black tree 형태로 구현되어 있습니다. Set 인터페이스를 구현했기 때문에 데이터의 중복을 허용하지 않으며 정렬된 위치에 저장하므로 저장순서를 유지하지도 않습니다. 

 

데이터를 저장하기 위한 Object 타입의 참조변수 하나와 두 개의 노드를 참조하기 위한 두 개의 참조변수

 

 

 

 

 

 

 

 

첫 번째로 저장되는 값은 루트가 되고, 두 번째 값은 트리의 루트부터 시작해서 값의 크기를 비교하면서 트리를 따라 내려갑니다. 이때 작은 값은 왼쪽에, 큰 값은 오른쪽에 저장합니다. 컴퓨터는 값을 스스로 못 비교하기 때문에 Comparable 혹은 Comparator를 제공해 두 객체를 비교할 방법을 알려줘야 합니다. 그렇지 않으면 TreeSet에 객체를 저장할 때 예외가 발생하게 됩니다. 

 

 

 

 

 

 

왼쪽 마지막 값에서부터 오른쪽 값까지 값을 [ 왼쪽 노드 -> 부모 노드 -> 오른쪽 노드 ] 순으로 읽어오면 오름차순으로 정렬된 노드를 얻을 수 있습니다. TreeSet은 정렬된 상태를 유지하기 때문에 단일 값 검색과 범위검색이 매우 빠릅니다. * 저장된 값의 개수에 비례해 검색시간이 증가한다.

 

순서가 보장된 트리

 

 

 

 

 

 

 

데이터를 순차적으로 저장하는 것이 아니라 저장위치를 찾아서 저장해야하고 삭제하는 경우 트리의 일부를 재구성하기 때문에 링크드 리스트보다 데이터의 추가/삭제 시간은 오래 걸립니다. 하지만 배열이나 링크드 리스트에 비해 검색과 정렬기능이 더 뛰어납니다.

 

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

 

 

 

 

 

 

데이터를 넣을 때 정렬하기 때문에 따로 값을 정렬할 필요가 없습니다. 단, 스스로 정렬하는 대신 데이터를 추가/삭제할 때 드는 시간과 비용이 추가로 발생합니다. **읽기 기능을 향상하면서 쓰기에 약하다고 생각하시면 될 것 같습니다.

 

 

 

 

 

 

 

 

 

2. 부분검색(subset)

---

부분검색을 위한 메서드. 이는 Set인터페이스에는 없는 TreeSet만의 기능입니다. 따라서 TreeSet<String>을 Set<String>으로 바꾸면 아래와 같이 에러가 발생하게 됩니다. 

 

 

 

 

 

 

 

 

상속 계층도를 확인해보면 Set은 AbstractSet<E>을 상속했고 . Set은 subSet( ) 메서드를 가지고 있지 않습니다.

 

TreeSet에만 존재하는 Method

What is the purpose of AbstractCollection

 

 

 

 

 

 

 

3. 정렬

---

문자열의 경우 정렬순서는 문자의 코드값이 기준이 되므로 오름차순 정렬의 경우 코드값의 크기가 작은 순서에서 큰 순서, 즉 공백, 숫자, 대문자, 소문자 순으로 정렬되고 내림차순의 경우 그 반대가 됩니다.

 

 

 

 

 

 

 

 

 

문자의 코드값 기준으로 정렬한 경우 아래와 같은 결과를 볼 수 있습니다.

 

 

 

 

 

 

 

 

4. headSet / tailSet

---

headSet, tailSet을 이용하면 TreeSet에 저장된 객체 중 지정된 기준 값보다 큰 값 객체들과 작은 값 객체들을 얻을 수 있습니다.