자바의 Collection 인터페이스나 Map 인터페이스를 구현한 클래스 중 Tree 로 시작하는 클래스는 데이터를 추가한 후 결과를 출력하면 결과 값이 정렬됩니다. TreeSet 는 자료의 중복을 허용하지 않으면서 출력 결과 값을 정렬하는 클래스입니다.
TreeSetTest
TreeSetTest 코드를 작성해서 TreeSet 의 특징을 살펴보겠습니다. TreeSet 에 자료를 추가한 다음에 출력을 해보았는데요. 별도의 코드를 구현하지 않아도 요소들이 정렬되었던 이유는 String 클래스 안에 정렬 방식이 이미 구현되어 있기 때문입니다. 그렇다면 실제로 TreeSet 에서 어떻게 자바는 정렬을 진행했다는 것일까요?
binary tree 이진 트리 & binary search tree 이진 검색 트리
자바는 정렬을 구현하기 위해 '이진 트리 binary tree'를 사용합니다. 트리는 자료 사이의 계층 구조를 나타내는 자료 구조 입니다. 트리 자료 구조를 자세히 살펴보기보다는 TreeSet 를 이해하기 위해 필요한 '이진 검색 트리 Binary Search Tree'에 대해서만 간단히 알아보겠습니다. 트리 자료 구조에서 각 자료가 들어가는 공간을 노드라고 합니다. 그리고 위 아래로 연결된 노드의 관계를 '부모-자식 노드'라고 합니다. 이진 검색 트리는 노드에 저장되는 자료의 중복을 허용하지 않고, 부모가 가지는 자식 노드의 수가 2개 이하입니다. 또한 왼쪽에 위치하는 자식 노드는 부모 노드보다 항상 작은 값을 가집니다. 반대로 오른쪽에 놓인 자식 노드는 부모 노드보다 항상 큰 값을 가집니다. 따라서 어떤 특정 값을 찾으려 할 때 한 노드와 비교하여 작은 값이면 왼쪽 자식 노드 방향으로, 그렇지 않으면 오른쪽 자식 노드 방향으로 이동합니다. 따라서 비교 범위가 평균 1/2 만큼씩 줄어들어 효과적으로 자료를 검색할 수 있습니다. 예를 들어 50, 15, 62, 80, 7, 54, 11 순으로 숫자가 입력되었다면 트리가 만들어지는 과정은 위 그림과 같습니다. 이렇게 만들어진 이진 검색 트리는 왼쪽 -> 부모 -> 오른쪽 순으로 순회하면 오름차순이 됩니다. 그 반대로 오른쪽 -> 부모 -> 왼쪽 순으로 순회하면 내림차순이 됩니다. 자바의 TreeSet 은 바로 이런 이진 검색 트리를 활용하여 자료를 정렬합니다.
MemberTreeSet & MemberTreeSetTest 클래스
TreeSet 를 활용해 회원 관리 프로그램을 구현해보겠습니다. 회원 정렬 기준은 회원 아이디순으로 하겠습니다. 완성된 코드를 작성하기 전에 다음과 같은 코드를 우선 작성해보겠습니다. TreeSet 테스트 코드를 작성하여 회원 아이디 순서대로 정렬이 되는지 확인해 보겠습니다. 테스트 코드를 작성하였는데요. 한번 실행시켜 보겠습니다. 오류가 발생한 것을 볼 수 있는데요. 오류 내용을 살펴보도록 하겠습니다. 오류를 보면 Member 클래스가 Comparable 인터페이스를 구현하지 않아서 오류가 발생했음을 알 수 있습니다. Comparable 인터페이스를 구현하지 않았다는 의미는 우리가 만든 Member 클래스를 TreeSet 의 요소로 추가할 때 어떤 기준으로 노드를 비교하여 트리를 형성해야 하는지를 구현하지 않았다는 의미입니다. 회원을 TreeSet 에 추가할 때 어떤 기준으로 비교할 것인지를 구현해 주어야 하며 이때 사용하는 인터페이스가 Comparable 또는 Comparator 입니다.
Comparable 인터페이스
우리는 Member 클래스가 가진 회원 아이디를 기준으로 하여 오름차순으로 정렬할 것입니다. Comparable 과 Comparator 는 이러한 정렬을 구현할 수 있게 해주는 인터페이스입니다. 이 인터페이스를 그럼 누가 구현해야 할까요? 바로 정렬 기준 값이 있는 Member 클래스에 구현하면 됩니다. Coparable 인터페이스에는 compareTo( ) 추상 메서드가 있고 이것을 구현해야합니다. 위 코드에서 재정의한 compareTo( ) 메서드의 의미는 다음과 같습니다. this.memberId - member.memberId 로 리턴값을 작성하면 오름차순 정렬을 하겠다는 것을 의미하고 this.memberId - member.memberId*(-1) 로 리턴 값을 작성하면 내림차순 정렬을 하겠다는 것을 의미합니다.
this.memberId 는 새로 추가한 회원의 아이디이며 member.memberId 는 매개변수로 전달된 기존에 있던(처음 추가하는 자료라면 Null 일 수도 있음) member 의 회원 아이디와 비교하여 더 크면 양수 그렇지 않으면 음수를 반환하는 메서드가 compareTo( ) 메서드 입니다. compareTo( ) 의 반환 값은 정수 값인데, 비교하는 두 값 중 this 값이 더 크면 양수를 반환하여 오름차순으로 정렬 되고 this 값이 더 작으면 음수를 반환하여 내림차순으로 정렬됩니다. 또한 compareTo( ) 메서드는 프로그래머가 호출하는 메서드가 아닌 객체가 TreeSet에 요소를 추가할 때 호출되는 메서드입니다. 그리고 어떤 매개변수(member)가 전달될지는 기존 TreeSet 에 어떤 요소가 들어 있는지에 따라 달라집니다. 코드를 약간 수정하고 실행해 보았는데요. MemberTreeSetTest 클래스를 다시 실행하면 위와 같은 정렬 결과를 볼 수 있습니다. 오름차순으로 정렬된 것을 볼 수 있는데, 내림차순으로 정렬하기 위해서는 위와 같이 compareTo 반환 값을 음수로 만들면 됩니다.
Comparator 인터페이스
이번에는 Comparator 인터페이스를 구현하겠습니다. Comparator 인터페이스는 compare( ) 메서드를 구현해야 합니다. Member2 클래스를 만들어서 Comparator 인터페이스를 구현하겠습니다. Member2 클래스는 Member 클래스의 코드와 거의 똑같고 compare( ) 메서드만 override 했습니다. Comparator 인터페이스는 compare( ) 메서드를 구현해야 하는데, 이 메서드에는 매개변수가 2개 전달됩니다. comarator 는 compareTo( ) 메서드와는 다르게 이 두 개의 매개변수를 서로 비교합니다.
TreeSet<Member> treeSet = new TreeSet<Member>(new Member());
또한 Comparator 를 사용할 때는 위와 같이 Test 파일에서 생성자를 수정해주어야 합니다. TreeSet 생성자에 Comparator 를 구현한 객체를 매개변수로 전달하는 것을 볼 수 있습니다.
Comparable vs Comparator ; 언제 무엇을 사용할까?
일반적으로 Comparator 인터페이스보다는 Comparable 인터페이스를 더 많이 사용합니다. 다만 어떤 클래스가 이미 Comparable 인터페이스를 구현한 경우에 이 클래스의 정렬 방식을 저으이할 때 Comparator 인터페이스를 사용할 수 있습니다. 예를 들어 String 클래스는 Comparable 인터페이스를 이미 구현했다고 했습니다. 그리고 Comparable 인터페이스의 compareTo( ) 메서드는 오름차순 정렬을 구현하고 있습니다. 만약 정렬 방식을 내림차순으로 바꾸고 싶다면 어떻게 해야 할까요? String 클래스의 경우에는 final 로 선언되어 있기 때문에 상속받아 compareTo( ) 메서드를 재정의할 수도 없습니다. 이러한 경우에 Comparator 를 사용하게 됩니다.
