[이펙티브 자바 완벽 공략] TreeSet

TreeSet

AbstractSet을 확장한 정렬된 컬렉션
- 엘리먼트를 추가한 순서는 중요하지 않다
- 엘리먼트가 지닌 자연적인 순서(natural order)에 따라 정렬한다
- 오름차순으로 정렬한다
- 스레드 안전하지 않다
  - 스레드 안전하게 사용하고 싶으면 Collections.synchronizedSet() 사용
- 내부적으로 TreeMap을 사용해서 구현
  - TreeMap은 이진 검색 트리, 그 중에서도 레드-블랙 트리를 사용해서 구현

이진 검색 트리(바이너리 서치 트리)

- 왼쪽 서브트리에는 자신보다 작은 값, 오른쪽 서브트리에는 큰 값을 가지도록 구성
- 정렬 순서가 트리 구조 자체에 내재
- 중위 순회(in-order traversal) 만으로 정렬된 순서를 얻을 수 있음
- 탐색, 삽입, 삭제 모두 평균적으로 O(log n)
- 최악의 경우(편향 트리), O(n)이 되기 때문에 BST 장점이 사라질 수 있다.
- 균형 탐색 트리를 사용해서 편향 트리가 되지 않도록 한다
  - AVL, 2-3, 2-3-4, 레드-블랙 트리, B트리, B+트리 등

레드-블랙 트리

- 노드 색깔(레드/블랙)에 대한 제약 조건들을 통해 트리가 한쪽으로 치우치는 것을 막음
- 루트에서 가장 먼 리프가지의 경로와 가장 가까운 리프까지의 경로 길이 차이가 일정 비율 이상 벌어지지 않도록 강제
- 이 속성 덕분에 노드가 n개일 때 트리의 높이 h는 항상 O(log n)으로 보장됨
 
레드-블랙 트리의 5가지 규칙
1. 노드의 색상 : 모든 노드는 레드 또는 블랙 중 하나의 색상을 가진다
2. 루트 노드의 색상 : 루트 노드는 항상 블랙
3. 리프 노드의 색상 : 모든 리프 노드(데이터가 없는 끝 노드)는 블랙
4. 레드 노드의 자식 : 레드 노드의 자식은 반드시 블랙 (레드 노드가 연속해서 나타날 수 없음)
5. 경로의 블랙 노드 수 : 루트 노드에서 임의의 리프 노드까지 이르는 경로에 포함된 블랙 노드의 개수는 모두 동일함
 
데이터 삽입, 삭제 시 규칙이 깨지는 경우, 두 가지 방법을 통해 균형을 다시 맞춤
1. 색상 변경 (recoloring)
2. 회전 (rotation)