[Java] TreeSet

TreeSet은 이진 검색 트리(binary search tree)라는 자료구조의 형태로 데이터를 저장하는 컬렉션 클래스이다. 이진 검색 트리는 정렬, 검색, 범위검색에 높은 성능을 보이는 자료구조이며 TreeSet은 이진 검색 트리의 성능을 향상 시킨 '레드-블랙 트리'로 구현되어 있다.

 

TreeSet : Set인터페이스를 구현했다.(중복x, 순서x)
- 내부적으로 Red - Black Tree로 구현되어 있다.(균형잡힌 Binary Search Tree, BST)

- 균형 이진 트리기 때문에 검색, 삽입, 삭제하는 효율이 높아진다.
- 보통의 경우 HashSet을 쓰지만 범위 검색 시 TreeSet 사용한다.

 

 

TreeSet예시

public class _01_TreeSet {//검색이 유리함
	
	public static void main(String[] args) {
		TreeSet<Integer> ts = new TreeSet<>();
		ts.add(3);
		ts.add(4);
		ts.add(5);
		ts.add(6);
		ts.add(3);
		ts.add(12);
		ts.add(13);
		ts.add(16);
		ts.add(24);
		ts.add(33);
		ts.add(23);
	
		System.out.println("Tree Set : " + ts);
		
		System.out.println("Tree Set : " + ts.subSet(3, 15));//subSet[from포함, to)미포함
	}
}

 

 

comparable은 자기 자신과 매개변수 객체를 비교하는 것이다. Fruit객체와 또 다른 Fruit객체를 비교하기 위해 사용했다.

compareTo는 값을 비교해서 정수를 반환한다.(1, 0, -1)

import java.util.TreeSet;

class Fruit implements Comparable<Fruit>{
	
	public Fruit(String name, int price){
		mName = name;
		mPrice = price;
	}
	
	@Override//object class
	public String toString() {
		return mName + " => " + mPrice + "원";//문자열을 만들어서 리턴
	}
	
	@Override//compareble 인터페이스//정렬기준
	public int compareTo(Fruit other) {
		if(mPrice == other.mPrice) {//값이 같으면 0
			return 0;
		}else if(mPrice < other.mPrice){//비교값이 크면 음수
			return -1;
		}else {//비교값이 작다면 양수
			return 1;
		}
	}
	
	private String mName;
	private int mPrice;
}

public class _04_FruitPriceSort {

	public static void main(String[] args) {
//		Fruit f1 = new Fruit("사과", 1200);
//		Fruit f2 = new Fruit("배", 2300);
//		Fruit f3 = new Fruit("귤", 600);
//		Fruit f4 = new Fruit("딸기", 3600);
		
		TreeSet<Fruit> ts = new TreeSet<>();
//		ts.add(f1);
//		ts.add(f2);
//		ts.add(f3);
//		ts.add(f4);
		ts.add(new Fruit("사과", 1200));
		ts.add(new Fruit("배", 2300));
		ts.add(new Fruit("귤", 600));
		ts.add(new Fruit("딸기", 3600));
		
		System.out.println("TreeSet : " + ts);
		System.out.println("\n* 가격 순 과일 메뉴 출력*");
		for(Fruit fru : ts) {
			System.out.println(fru);
		}
	}

}