이진 탐색 트리와 TreeSet
TreeSet
TreeSet은 이진 탐색 트리라는 자료 구조 형태로 데이터를 저장하는 컬렉션 클래스이다. 이진 탐색 트리는 정렬, 검색, 범위 검색(range search)에 높은 성능을 보이는 자료 구조이며 TreeSet은 이진 탐색 트리의 성능을 향상시킨 레드-블랙 트리(Red-Black tree)로 구현되어 있다. Set 인터페이스를 구현했으므로 데이터를 중복으로 저장하지 않고 값을 정렬하여 저장하므로 저장 순서를 유지하지도 않는다.
이진 트리(binary tree)는 연결 리스트처럼 여러 개의 노드가 서로 연결된 구조로, 각 노드에 최대 2개의 노드를 연결할 수 있으며 루트(root)라고 불리는 하나의 노드에서부터 시작해 계속 확장해 나간다. 위 아래로 연결된 두 노드를 부모-자식 관계에 있다고 하며 위의 노드를 부모 노드, 아래 노드를 자식 노드라 한다. 부모-자식 관계는 상대적이며 하나의 부모는 최대 2개의 자식 노드와 연결될 수 있다. 이진 트리의 노드를 코드로 표현하면 다음과 같다.
class TreeNode {
TreeNode left; // 왼쪽 자식 노드
Object element; // 객체를 저장하기 위한 참조 변수
TreeNode right; // 오른쪽 자식 노드
}
이진 탐색 트리(binary search tree)
이진 탐색 트리는 부모 노드의 왼쪽에는 부모 노드의 값보다 작은 값의 자식 노드를, 오른쪽에는 큰 값의 자식 노드를 저장하는 이진 트리이다.
예를 들어 데이터를 5, 1, 7의 순서로 저장한 이진 탐색 트리의 구조는 아래와 같이 표현할 수 있다.
왼쪽 마지막 값에서부터 오른쪽 값까지 값을 ‘왼쪽 노드 → 부모 노드 → 오른쪽 노드’ 순으로 읽어오면 오름차순으로 정렬된 순서를 얻을 수 있다. TreeSet은 이처럼 정렬된 상태를 유지하기 때문에 단일 값 검색과 범위 검색(range search, 예를 들어 3과 7사이의 범위에 있는 값을 검색)이 매우 빠르다. 저장된 값의 개수에 비례해서 검색 시간이 증가하긴 하지만 값의 개수가 10배 증가해도 특정 값을 찾는데 필요한 비교횟수가 3~4번만 증가할 정도로 검색 효율이 뛰어난 자료 구조이다.
트리는 데이터를 순차적으로 저장하는 것이 아니라 저장 위치를 찾아서 저장해야 하고, 삭제하는 경우 트리의 일부를 재구성해야 하므로 연결 리스트보다 데이터의 추가 / 삭제 시간은 더 걸린다. 대신 배열이나 연결 리스트에 비해 검색과 정렬 기능이 더 뛰어나다.
- 특징
- 모든 노드는 최대 2개의 자식 노드를 가질 수 있음.
- 왼쪽 자식 노드의 값은 부모 노드의 값보다 작고 오른쪽 자식 노드의 값은 부모 노드의 값보다 커야 함.
- 노드의 추가, 삭제에 시간이 걸림(순차적으로 저장하지 않으므로).
- 검색(범위 검색)과 정렬에 유리.
- 중복된 값을 저장하지 못함.
이진 탐색 트리의 저장 과정
예를 들어 이진 탐색 트리에 7, 4, 9, 1, 5의 순서로 값을 저장한다고 가정하면 다음과 같은 순서로 진행된다.
- 첫 번째로 저장되는 값은 루트가 됨.
- 두 번째 값은 트리의 루트부터 시작해 값의 크기를 비교하면서 트리를 따라 내려감.
- 작은 값은 왼쪽에 큰 값은 오른쪽에 저장.
- 이렇게 트리를 구성하면, 왼쪽 마지막 레벨이 제일 작은 값이 되고 오른쪽 마지막 레벨의 값이 제일 큰 값이 됨.
public static void main(String[] args) {
Integer[] ints = {7, 4, 9, 1, 5};
TreeSet set = new TreeSet(Arrays.asList(ints));
for (Object o : set) {
System.out.print(o + " ");
}
// 실행 결과
// 1 4 5 7 9
}TreeSet에 저장되는 객체가 Comparable을 구현하든지 Comparator를 제공해서 두 객체를 비교할 방법을 알려주지 않으면 TreeSet에 객체를 저장할 때 예외가 발생한다. 다음과 같은 Menu 클래스 있고 이 Menu 클래스의 객체를 TreeSet에 추가하려는 경우 에러가 발생한다.
public class Menu {
private String menuName;
private int price;
public Menu(String menuName, int price) {
this.menuName = menuName;
this.price = price;
}
...
@Override
public String toString() {
return "<" + menuName + ": " + price + ">";
}
}public static void main(String[] args) {
Menu[] menus = {
new Menu("coffee", 3000),
new Menu("tea", 3500),
new Menu("ade", 4500)
};
TreeSet set = new TreeSet(Arrays.asList(menus));
for (Object o : set) {
System.out.print(o + " ");
}
}Exception in thread "main" java.lang.ClassCastException: collection_framework.Menu cannot be cast to java.lang.Comparable발생
따라서 Comparable을 구현하여 비교할 수 있도록 해주어야 한다.
public class Menu implements Comparable<Menu> {
...
@Override
public int compareTo(Menu menu) {
return this.getPrice() - menu.getPrice();
}
}public static void main(String[] args) {
Menu[] menus = {
new Menu("coffee", 3000),
new Menu("tea", 3500),
new Menu("ade", 4500)
};
TreeSet set = new TreeSet(Arrays.asList(menus));
for (Object o : set) {
System.out.print(o + " ");
}
// 실행 결과
// <coffee: 3000> <tea: 3500> <ade: 4500>
}References
- 자바의 정석 CHAPTER 11
