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

 

item13. clone 재정의는 항상 주의해서 진행하라. 

" p86. TreeSet"

 

 

TreeSet

: TreeSet은 Set 인터페이스를 구현한 클래스로, Set의 특징인 객체를 중복해서 저장할 수 없고, 저장 순서가 유지되지 않는 특징을 그대로 가지고 있다. 

 

TreeSet은 이진 탐색 트리의 구조로 이루어져 있는데, 이진 탐색 트리는 추가와 삭제에는 시간이 좀 걸리지만 정렬, 검색에 높은 성능을 보이는 자료구조이다. 

 

TreeSet은 엘리먼트가 지닌 자연적인 순서 natural order에 따라 정렬하고, 오름차순으로 정렬한다. 

생성자의 매개변수로 Comparator 객체를 입력하여 정렬 방법을 임의로 지정해 줄 수도 있다. 

 

TreeSet<Integer> numbers = new TreeSet<>();
numbers.add(10);
numbers.add(4);
numbers.add(6);

for (Integer number : numbers)
{
   System.out.println("number = " + number);
}

-> TreeSet을 생성하기 위해서는 기본 생성자를 호출하면 되고, add를 통해  TreeSet에 값을 추가할 수 있다. 

이때 natural order를 통해 오름차순으로 정렬해 4,6,10 순으로 출력된 것을 확인할 수 있다. 

 

 

TreeSet<PhoneNumber> phoneNumbers = new TreeSet<>(Comparator.comparingInt(PhoneNumber::hashCode));
phoneNumbers.add(new PhoneNumber(123, 456,780));
phoneNumbers.add(new PhoneNumber(123, 456,7800));
phoneNumbers.add(new PhoneNumber(123, 456,789));

for (PhoneNumber phoneNumber : phoneNumbers)
{
   System.out.println("phoneNumber = " + phoneNumber); // Comparable을 구현하지 않아서 Error 발생 !
}

근데 PhoneNumber의 경우에는 컴퓨터가 이게 뭔지 알 수 없기 때문에 정렬할 수 없는데 이럴 때는 Comparator를 추가해 정렬하는 방법을 알려줘야 한다. 

지금은 hashcode 기준으로 정렬하도록 했고, 

 정렬 결과 이렇게 출력되는 것을 확인할 수 있다. 

 

 

TreeSet<PhoneNumber> phoneNumbers = new TreeSet<>(Comparator.comparingInt(PhoneNumber::hashCode));
Set<PhoneNumber> phoneNumberSet = Collections.synchronizedSet(phoneNumbers); // 스레드 안전하기 위해서
phoneNumbers.add(new PhoneNumber(123, 456,780));
phoneNumbers.add(new PhoneNumber(123, 456,7800));
phoneNumbers.add(new PhoneNumber(123, 456,789));

for (PhoneNumber phoneNumber : phoneNumbers)
{
   System.out.println("phoneNumber = " + phoneNumber); // Comparable을 구현하지 않아서 Error 발생 !
}

TreeSet은 스레드 안전하지 않기 때문에 만약 스레드 안전해야 한다면 Collections.synchronizedSet을 통해 동기화 시켜줘야 한다. 

 

 

 

📚 레드-블랙 트리 Red-Black Tree 

출처: https://coding-factory.tistory.com/555

TreeSet은 이진 탐색 트리의 구조로 이루어져 있는데 TreeSet은 이진 탐색 트리 중에서도 성능을 향상시킨 레드-블랙 트리로 구현되어 있다. 

레드-블랙 틀리나 부모 노드보다 작은 값을 가지는 노드는 왼쪽 자식으로, 큰 값을 가지는 노드는 오른쪽 자식으로 배치하여 데이터의 추가나 삭제 시 트리가 한쪽으로 치우치지 않도록 균형을 맞춰준다.