TreeSet
- 이진 탐색 트리(binary search tree)로 구현.
- 범위 탐색과 정렬에 유리하다(from~to)
- 이진 트리는 모든 노드가 최대 2개의 하위 노드를 갖음
- 하나의 요소에 연결된 요소가 최대 2개(0개~2개)
- 각 요소(node)가 나무(tree) 형태로 연결(LinkedList의 변형)
이진트리!
class TreeNode {
TreeNode left; // 왼쪽 자식 노드
Object element; // 저장할 객체
TreeNode right; //오른쪽 자식 노드
}이진 탐색 트리(binary search tree)
- 부모보다 작은 값은 왼쪽, 큰 값은 오른쪽에 저장한다.
- 이진트리의 한 종류이다.
- 이진트리의 한 종류이다.
- 데이터가 많아질 수록 추가, 삭제에 시간이 더 걸린다(비교 횟수 증가)
왜냐하면 넣을 때마다 부모보다 큰지 작은지 비교해가면서 넣어야 하니까!
TreeSet의 데이터 저장 과정
boolean add(Object o) add()를 실행하는 순간
1. equals()
(중복이 안되므로 계속 체크를 해줘야 하니까! 중복된게 있으면 저장안됨)
2. hashCode()
이 호출된다.
‣ TreeSet에 7,4,9,1,5의 순서대로 데이터를 저장하면, 아래의 과정을 거친다.
(루트부터 트리를 따라 내려가며 값을 비교. 작으면 왼쪽, 크면 오른쪽에 저장)
비교횟수는 7(0), 4(1), 9(1), 1(2), 5(2)
저장에 따라 비교횟수가 더 늘어나서 저장에 시간이 더 오래걸린다는 단점이 있다.
TreeSet의 주요 생성자와 메서드
트리 순회(tree traversal)
- 이진 트리의 모든 노드를 한번씩 읽는 것을 트리 순회라고 한다.
- 전위, 중위 후위 순회법이 있으며, 중위 순회하면 오름차순으로 정렬된다.
