TreeSet과 Comparator

레드-블랙 트리

-  TreeSet 특징

• TreeSet은 이진탐색트리이다. 
• 검색, 정렬에 유리하나 추가, 삭제에는 취약하다.
• Set이라서 중복을 허용하지 않는다.
• 기본적으론 nature ordering을 지원하지만 Comparator 객체를 매개변수로 사용하면 임의의 정렬방법을 지정할 수 있다.
• 노드는 2개의 자식노드를 가지고 있고 본인보다 작은 값을 가진 자식노드는 왼쪽, 큰 값을 가진 자식노드는 오른쪽에 추가된다.(그림 참조)

 

-  Comparator를 응용한 TreeSet 정렬

TreeSet<String> treeSet = new TreeSet<String>(new Comparator<String>{
    public int compare(String o1, String o2){
    	if(o1.length() <= o2.length()){
        	return -1;
        }else{
        	return 1;
        }
    }
});
//TreeSet 생성자의 매개변수로 Comparator 객체를 사용한다. 
//Comparator 객체 생성 시, compare 메소드를 오버라이드하여 원하는 정렬순서를 만들 수 있다.
//리턴값이 음수라면 o1이 왼쪽자식노드로 o2가 오른쪽자식노드로 TreeSet이 구성된다.
//리턴값이 양수라면 o2가 왼쪽자식노드로 o1이 오른쪽자식노드로 TreeSet이 구성된다.
//위의 compare은 길이가 짧은 문자부터 정렬되도록 만드는 메소드이다.

String str1 = "1234";
String str2 = "12";
String str3 = "1234567";
String str4 = "12345";

treeSet.add(str1);
treeSet.add(str2);
treeSet.add(str3);
treeSet.add(str4);

Iterator<String> iter = treeSet.iterator();
System.out.println("<출력>");
while(iter.hasNext()) {
	System.out.println(iter.next());
}

<출력>
12
1234
12345
1234567