JAVA - 컬렉션 : TreeSet (트리구조)

TreeSet

---

개요 

---

• 이진 트리를 기반으로 한 Set 컬렉션이다.
• 이진 검색 트리(binary search tree)라는 자료구조의 형태로 데이터를 저장하는 컬렉션 클래스이다.
• 원리는 부모 노드의 왼쪽에는 부모 노드의 값보다 작은 값의 자식 노드를, 오른쪽 에는 큰 값의 자식노드를 저장한다.
• 정렬, 검색, 범위 검색에 높은 성능을 보이는 자료 구조이며, TreeSet은 이진 검색트리의 성능을 향상 시킨 컬렉션이다.
• Set 인터페이스를 구현 했으므로 중복된 데이터의 저장을 허용하지 않으면 정렬된 위치에 저장하므로 저장 순서를 유지하지도 않는다.

 

이진트리의 코드는 데이터를 저장하기 위한 Object 타입의 참조 변수 하나와 양쪽의 노드를 참조하기 위한 2개의 참조 변수가 선언되어 있다.  부모 Left 에는  작은 값의 자식, -> 부모 Right에는 자식이 더 큰 값을 가지는 모습을 볼 수 있다. 

 

만약 이진 검색 트리에 [ 7, 4, 9, 1, 5] 순서대로 값을 저장하면 위의 그림과 같은 순서대로 진행된다.

 

첫 번째로 저장되는 값은 루트가 되고 두 번째 값은 트리의 루트부터 시작해서 값의 크기를 비교하면서 트리를 따라 내려간다. 자식 노드가 없을 경우 기준이 되는 값(초록색) 보다 작은 값은 왼쪽 노드(파란색), 큰 값은 오른쪽 노드(빨간색)에 배치된다. 이런 식으로 값을 채워나가면 최종 트리에서 왼쪽 마지막 레벨이 제일 작은 값(1)이 되고, 오른쪽 마지막 레벨의 값이 가장 큰 값(9)이 된다.

 

위의 예시는 숫자라서 비교가 쉽지만, 객체(Class,Object) 간의 비교 시에는 비교 기준이 필요하다. TreeSet에 저장되는 객체가 Comparable을 구현하던가 Comparator를 제공해서 두 객체를 비교할 방법을 알려줘야 한다. 그렇지 않으면 TreeSet에 객체를 저장할 때 예외가 발생한다.

 

특징

---

• 모든 노드는 최대 2개의 자식 노드를 가질 수 있다. (이진 트리)
• 부모노드를 기준으로 왼쪽 자식노드의 값은 부모노드의 값보다 작고, 오른쪽 자식 노드의 값은 부모노드의 값보다 커야한다.
• 순차적으로 저장하지 않으므로 노드의 추가/삭제에 시간이 걸린다.
• 검색(범위검색)과 정렬에 유리하다. 
• 중복된 값을 정리하지 못한다.

단점 : 삽입, 삭제할 때 다른 트리구조도 변경해야 함. 처리시간이 많이 걸린다.

삽입, 삭제 빈번히 일어난다. < == > LinkedHashSet (LinkedHashSet과 대조된다.)

 

객체 비교 CompareTo (Class object) 

---

ComparaTo() 메소드는 주어진 객체와 같으면 0을 리턴, 주어진 객체보다 적으면 음수를 리턴, 주어진 객체보다 크면 양수를 리턴한다. -1, 0, 1

 

Comparable과 Comparator 사용자 정의 정렬 기준

TreeSet의 객체의 키는 저장과 동시에 자동 오름차순으로 정렬된다.

숫자(Integer, Double) 타입일 경우에는 값으로 정렬한다.

문자열(String) 타입일 경우에는 유니코드로 정렬한다.

 

방법 1) Comparable 인터페이스를 구현하여 사용자 정의 클래스가 정의되어 있기 때문에 사용자 정의 클래스에서는 이 메소드를 오버라이딩하여 리턴 값을 만들어 낸다.

 

활용

---

public class TreeSetEx02 {
	public static void main(String[] args) {
		
		Set<Person> set = new TreeSet<Person>();
		set.add(new Person("홍길동",30));
		set.add(new Person("홍길동",20));
		set.add(new Person("이길동",10));
		set.add(new Person("박길동",30));
		set.add(new Person("장길동",10));
		System.out.println(set);
		// 런타임 오류가 나는 이유.
		// 기준이 없다. CompareTo를 해줘야한다.
	}
}
class Person implements Comparable<Person>{
	String name;
	int age;
	
	public Person(String name, int age) {
		this.name=name; this.age=age;
	}

	@Override
	public String toString() {
		return "Person [name=" + name + ", age=" + age + "]";
	}
	/*
	@Override
	public int compareTo(Person p) { // 오름차순 정렬 
		if(age<p.age) return -1; // age가 매개변수 age보다 낮으면 음수 리턴 (낮은 가지) 
		else if(age == p.age) return 0; // age와 매개변수 age와 같으면 0 (동등한 가지)
		else return 1; //  age가 매개변수 age보다 높으면 양수 리턴 (높은 가지)
		/*
		       1
		       0
		      -1
		 /
	} */
	/*
	@Override
	public int compareTo(Person p) { // 반대로하면 내림차순 정렬 
		if(age<p.age) return 1;
		else if(age == p.age) return 0;
		else return -1; 
	}
	*/
	/*
	@Override
	public int compareTo(Person p) { // 이름으로 정렬  
		if(name.hashCode() < p.name.hashCode()) return -1;
		else if(name.hashCode() == p.name.hashCode()) return 0;
		else return 1;
	} 
	*/
	@Override
	public int compareTo(Person p) { // 이름과 나이순으로 정렬  
		if(name.hashCode() < (p.name.hashCode() + p.age ) ) return -1;
		else if(name.hashCode() == (p.name.hashCode() + p.age) ) return 0;
		else return 1;
	}
 
	
	
}

---

 

public class StudentEx {

	public static void main(String[] args) {
		Set<Student> stu = new TreeSet<Student>();
		
		stu.add(new Student("아주대","홍길동","김학생",85));
		stu.add(new Student("중앙대","박길동","박학생",75));
		stu.add(new Student("고려대","박길순","유학생",95));
		stu.add(new Student("고려대","박길순","추학생",95));
		stu.add(new Student("아주대","홍길순","한학생",80));
		stu.add(new Student("서울대","홍길순","한학생",100));
		for(Student s : stu ) {
			System.out.println(s);
		}
	}

}

class Student implements Comparable<Student>{
	String school;
	String teacher;
	String name;
	int score;

	public Student(String school,String teacher, String name, int score) {
		this.school=school; this.teacher=teacher; this.name=name; this.score=score;
	}
//	@Override
//	public int compareTo(Student s) { // 학교명 오름차순
//		if(school.hashCode() < s.school.hashCode()) return -1;
//		else if(school.hashCode() == s.school.hashCode()) return 0;
//		else return 1;
//	}
//	@Override
//	public int compareTo(Student s) { // 점수순 내림차순
//		if(score < s.score )return 1;
//		else if(score == s.score ) return 0;
//		else return -1;
//	}
//	@Override
//	public int compareTo(Student s) { // 이름순 오름차순 
//		if(name.hashCode() < s.name.hashCode() )return -1;
//		else if(name.hashCode() == s.name.hashCode() ) return 0;
//		else return 1;
//	}
	@Override
	public int compareTo(Student s) { // 이름+점수 오름차순 
		if(name.hashCode()+score < s.name.hashCode()+s.score )return -1;
		else if(name.hashCode()+score == s.name.hashCode()+s.score ) return 0;
		else return 1;
	}
	

	@Override
	public String toString() {
		return "Student [school=" + school + ", teacher=" + teacher + ", name=" + name + ", score=" + score + "]";
	}
	
	
}

---

 

---

 

 

---