[백업][가리사니] 클래스 배열을 이진트리로 정렬／검색 하는 방법
java
이 문서는 가리사니 개발자 포럼에 올렸던 글의 백업 파일입니다. 오래된 문서가 많아 현재 상황과 맞지 않을 수 있습니다.
대략 1000개이하의 데이터를 찾고싶을땐 HashMap을 사용하면되지만 데이터가 점점 많아지면 HashMap 보단 binarySearch [이진검색] 이 더 빠르게 작동하게 됩니다.
자바에서는 원시자료의 배열형태는 Arrays.binarySearch 그외 클래스들의 배열형태는 Collections.binarySearch 를 통해 이진검색 찾기가 가능합니다.
예를들어 아래와 같은 객체가 있습니다.
public class Member
{
public int id;
public String name;
public String mobilePhone;
public String homePhone;
public String officePhone;
public String fax;
public String nick;
public String homeAddr;
public String homeZip;
public String officeAddr;
public String officeZip;
public String email;
public String memo;
public String company;
public String duty;
public String homepage;
public String birthday;
}
ArrayList<Member> list = new ArrayList<Member>();
// id를 기준으로 리스트를 찾는 소스를 만들고 싶을땐 Collections.binarySearch를 사용합니다.
하. 지. 만. 프로그램은 뭘 기준으로 찾아야할지 알수 없습니다. 그래서 아래와 같이 Comparable인터페이스를 사용하여 추가로 정렬할 수 있는 코드를 찾아줍니다.
public static class Member implements Comparable<Member>
{
public int id;
public String name;
public String mobilePhone;
public String homePhone;
public String officePhone;
public String fax;
public String nick;
public String homeAddr;
public String homeZip;
public String officeAddr;
public String officeZip;
public String email;
public String memo;
public String company;
public String duty;
public String homepage;
public String birthday;
@Override public int compareTo(Member another)
{
// 비교할 대상을 찾아줍니다.
// 0이면 정확히 찾은것이며
// - 이면 작은것 입니다.
// + 이면 큰것 입니다.
return this.id - another.id;
}
}
앞서 설명을 깜박했지만 binarySearch를 쓰기전엔 먼저 정렬을 해야합니다.
Collections.sort(list);
그다음 이제 찾고싶은걸 찾으면됩니다.
ArrayList<Member> list = new ArrayList<Member>();
Collections.sort(list); // 최초 1회 정렬 [소스를 보시면아시겠지만 이진검색을 위해선 정렬이 필수입니다.]
...
Member node = new Member();
node.id = 1;
int rv = Collections.binarySearch(list, node);
// rv가 음수이면 없음.
// rv가 양수이면 해당 인덱스