[Kotlin] SortedSet, NavigableSet, TreeSet

 

Set 은 중복이 제거된 집합으로 정의할 수 있다.

 

SortedSet, NavigableSet, TreeSet 은 서로 연관관계가 깊은데 다음과 같은 다이어그램으로 나타낼 수 있다.

[사진 출처] https://onlineitguru.com/blog/understanding-java-treeset-with-examples

SortedSet과 NavigableSet 은 인터페이스에 불과하기 때문에 결국 실전에서 사용할 컬렉션은 클래스인 'TreeSet'이다.

 

TreeSet 의 구성

 

이름이 나타내듯 , Binary Search Tree (Red-BlackTree) 로 구현되어있고 

주요 operation 별 시간 복잡도는 다음과같다.

Operation	Time Complexity
Search	O (Log N)
Insert	O (Log N)
Delete	O (Log N)

 

이진 트리로 구성되있기 때문에 Log 의 밑은 2다.

 

그래서 TreeSet 은 언제 써야할까?

• 항상 정렬된 상태의 큰 자료구조가 필요할 때
• Range-Based search 
• Subset 구하기

 

class TreeSetTest {
    @Test
    fun testTreeSet() {
    	// 문자열 오름차순을 Comparator 로 전달.
    	// 항상 정렬된 상태를 유지한다.
        val treeSet = TreeSet<String>(){ str1, str2 -> str1.compareTo(str2) }
        treeSet.add("Rumble")
        treeSet.add("Banana")
        treeSet.add("Apple")

		
        
    	// 이렇게 부분집합을 구하는게 용이하다.
        // return elements up to a limit defined sorted manner excluding the element.
        println(treeSet.headSet("Apple")) // []
        // return elements from the element including the element.
        println(treeSet.tailSet("Banana")) // [Banana, Rumble]
    }
}