TreeSet은 이진 검색 트리(binary search tree)라는 자료구조의 형태로 데이터를 저장하는 컬렉션 클래스이다.
이진 검색 트리는 정렬, 검색, 범위 검색에 높은 성능을 보이는 자료구조이며 TreeSet은 이진 검색 트리의 성능을 향상시킨 '레드-블랙 트리'로 구현되어 있다.
Set인터페이스를 구현했으므로 중복된 데이터의 저장을 허용하지 않으며 정렬된 위치에 저장하므로 저장순서를 유지하지도 않는다.
이진 트리의 노드를 코드로 표현한 코드
class TreeNode{
TreeNode left; //왼쪽 자식 노드.
Object element; //객체를 저장하기 위한 참조변수
TreeNode right; //오른쪽 자식 노드
}
데이터를 저장하기 위한 Object타입의 참조변수 하나와 두 개의 노드를 참조하기 위한 두 개의 참조변수를 선언했다.
이진 탐색 트리는 부모노드의 왼쪽에는 부모노드의 값보다 작은 값의 자식노드를 오른쪽에는 큰 값의 자식노드를 저장하는 이진 트리이다.
이진검색트리에 7, 4, 9, 1, 5 순서로 값을 저장과정
왼쪽 마지막 값에서부터 오른쪽 값까지 값을 '왼쪽노드 -> 부모노드 -> 오른쪽노드'순으로 읽어오면 오름차순으로 정렬된 순서를 얻을 수 있다.
TreeSet은 정렬된 상태를 유지하기 때문에 단일 값 검색과 범위검색이 매우 빠르다.
저장된 값의 개수가 비례해서 검색시간이 증가하긴 하지만 값의 개수가 10배 증가해도 특정 값을 찾는데 필요한 비교횟수가 3~4번만 증가할 정도로 검색효율이 뛰어난 자료구조이다.
트리는 데이터를 순차적으로 저장하는 것이 아니라 저장위치를 찾아서 저장해야하고, 삭제하는 경우 트리의 일부를 재구성해야하므로 링크드 리스트보다 데이터의 추가/삭제 시간은 더 걸린다.
대신 배열이나 링크드 리스트에 비해 검색과 정렬 기능이 더 뛰어나다.
이진 검색 트리는
- 모든 노드는 최대 두 개의 자식 노드를 가질 수 있다.
- 왼쪽 자식노드의 값은 부모노드의 값보다 작고 오른쪽자식노드의 값은 부모노드의 값보다 커야한다.
- 노드의 추가 삭제에 시간이 걸린다.(순차적으로 저장하지 않으므로)
- 검색(범위검색)과 정렬에 유리하다.
- 중복된 값을 저장하지 못한다.