자료구조_비선형구조 ① 트리 - 트리셋 TreeSet

 

[1] TreeSet

---

(1) Tree Set 특징

 

 

• 중복 허용 안됨
• 정렬된 순서에 의해 반복
• TreeMap을 이용하여 구현된 형태이다
• 인덱스 위치를 통해 저장과 접근을 하는것이 아닌 key를 이용하고 싶을 경우 사용한다 
• 저장되는 데이터의 갯수가 몇개인지 예상되지 않는 경우 사용한다
• 정렬된 값이 필요할때 사용한다 
• 삽입 삭제가 빈번하지 않을때 사용한다
• 객체의 정렬에 사용하는 클래스

• Set 인터페이스를 구현하여 중복을 허용하지 않고, 오름차순이나 내림차순으로 객체를 정렬할 수 있음
• 내부적으로 이진검색트리(binary search tree)로 구현됨
• 이진검색트리에 저장하기 위해 각 객체를 비교해야 함
• 비교 대상이 되는 객체에 Comparable이나 Comparator 인터페이스를 구현 해야 TreeSet에 추가 될 수 있음

 

 

[2] TreeSet 메서드

---

(1) TreeSet 선언하기 

import java.util.TreeSet;

TreeSet<String> set = new TreeSet<>();

List<String> arr = Arrays.asList("1","2","3");
TreeSet<String> set =new TreeSet<>(arr);

 

(2) TreeSet 메소드

add(데이터)	데이터 넣기
	a.add(1); a,add("아름")
size()	집합 크기 반환
	a.size();
contains(데이터)	집합 안에 객체가 있다면 true 반환
	a.contains(2);
remove(데이터)	데이터 삭제
	a.remove(1);
retainAll()	교집합 데이터 반환
	a.retainAll(b); return a;
addAll()	합집합 데이터 반환
	a.addAll(b); return a;
removeAll()	차집합 데이터 반환
	a.removeAll(b); return a;
containsAll()	부분집합 ; a 집합안에 b 집합이 있을때 b집합은 a집합의 부분집합이면true 반환
	return a.containsAll(b);

 

 

[3] TreeSet 예시 -1 

---

• String, Integer등 JDK의 많은 클래스들이 이미 Comparable을 구현했음

public class Member {
	
	private int memberId;        //회원 아이디
	private String memberName;   //회원 이름

	public Member(int memberId, String memberName){ //생성자
		this.memberId = memberId;
		this.memberName = memberName;
	}
	
	public int getMemberId() {  //
		return memberId;
	}
	public void setMemberId(int memberId) {
		this.memberId = memberId;
	}
	public String getMemberName() {
		return memberName;
	}
	public void setMemberName(String memberName) {
		this.memberName = memberName;
	}
	
	@Override
	public String toString(){   //toString 메소드 오버로딩
		return memberName + " 회원님의 아이디는 " + memberId + "입니다";
	}
    
    
    @Override
	public int hashCode() {
		return memberId;
	}

	@Override
	public boolean equals(Object obj) {
		if( obj instanceof Member){
			Member member = (Member)obj;
			if( this.memberId == member.memberId )
				return true;
			else 
				return false;
		}
		return false;
	}

}

 

멤버회원을 HashSet 자료구조를 이용하여 멤버를 추가하고 삭제한다 

public class MemberTreeSet {
	private TreeSet<Member> TreeSet;

	public MemberTreeSet(){
		TreeSet = new TreeSet<Member>();
	}
	
	public void addMember(Member member){
		TreeSet.add(member);
	}
	
	public boolean removeMember(int memberId){

		Iterator<Member> ir = TreeSet.iterator();
		
		while( ir.hasNext()){
			Member member = ir.next();
			int tempId = member.getMemberId();
			if( tempId == memberId){
				TreeSet.remove(member);
				return true;
			}
		}
		
		System.out.println(memberId + "가 존재하지 않습니다");
		return false;
	}
	
	public void showAllMember(){
		for(Member member : TreeSet){
			System.out.println(member);
		}
		System.out.println();
	}
}

실행클래스 

import java.util.TreeSet;

public class TreeSetTest {

	public static void main(String[] args) {

		TreeSet<String> treeSet = new TreeSet<String>();
		treeSet.add("홍길동");
		treeSet.add("강감찬");
		treeSet.add("이순신");
		
		for(String str : treeSet) {
			System.out.println(str);
		}
	}
}

 

[4] TreeSet 예시 -2

---

• 멤버회원을 트리세트 자료구조 형태로 회원을 추가하거나 삭제한다 
• get(i) 메서드를 사용할수 없으므로 Iterator를 사용하여 참조하여 비교 및 삭제한다 

public class MemberTreeSet {

	private TreeSet<Member> treeSet;

	public MemberTreeSet(){
		treeSet = new TreeSet<Member>();
	}
	
	public void addMember(Member member){
		treeSet.add(member);
	}
	
	public boolean removeMember(int memberId){
		
		Iterator<Member> ir = treeSet.iterator();
		
		while( ir.hasNext()){
			Member member = ir.next();
			int tempId = member.getMemberId();
			if( tempId == memberId){
				treeSet.remove(member);
				return true;
			}
		}
		
		System.out.println(memberId + "가 존재하지 않습니다");
		return false;
	}
	
	public void showAllMember(){
		for(Member member : treeSet){
			System.out.println(member);
		}
		System.out.println();
	}
}
public class MemberTreeSetTest {

	public static void main(String[] args) {

		MemberTreeSet memberTreeSet = new MemberTreeSet();
		
		Member memberKim = new Member(1003, "김유신");
		Member memberLee = new Member(1001, "이순신");
		Member memberKang = new Member(1002, "강감찬");
		
		memberTreeSet.addMember(memberKim);
		memberTreeSet.addMember(memberLee);
		memberTreeSet.addMember(memberKang);
		memberTreeSet.showAllMember();
		
	}
}

 

• 실행 클래스 
• String 클래스는 Comprable 인터페이스가 구현되어있어 
• add로 값을 넣었을때 
• 출력진행하면 오름차순으로 정렬되어서 출력한다 

public class MemberTreeSetTest {

	public static void main(String[] args) {

		MemberTreeSet memberTreeSet = new MemberTreeSet();
		
		Member memberKim = new Member(1003, "김유신");
		Member memberLee = new Member(1001, "이순신");
		Member memberKang = new Member(1002, "강감찬");
		
		memberTreeSet.addMember(memberKim);
		memberTreeSet.addMember(memberLee);
		memberTreeSet.addMember(memberKang);
		memberTreeSet.showAllMember();
		
	}
}

 

 

[5] TreeSet 예시 -3

---

• Member클래스가 아이디 오름차순으로 정렬되게 하기 위해 Comparable 인터페이스를 구현
• Comparator의 활용 : 이미 Comparable이 구현된 경우 Comparator로 비교하는 방식을 다시 구현할 수 있음
   

public class Member implements Comparable<Member> {
	
	private int memberId;        //회원 아이디
	private String memberName;   //회원 이름
	
    
    public Member() {} 
    
	public Member(int memberId, String memberName){ //생성자
		this.memberId = memberId;
		this.memberName = memberName;
	}
	
	public int getMemberId() {  //
		return memberId;
	}
	public void setMemberId(int memberId) {
		this.memberId = memberId;
	}
	public String getMemberName() {
		return memberName;
	}
	public void setMemberName(String memberName) {
		this.memberName = memberName;
	}
	
	@Override
	public String toString(){   //toString 메소드 오버로딩
		return memberName + " 회원님의 아이디는 " + memberId + "입니다";
	}
    
    
    @Override
	public int hashCode() {
		return memberId;
	}

	@Override
	public boolean equals(Object obj) {
		if( obj instanceof Member){
			Member member = (Member)obj;
			if( this.memberId == member.memberId )
				return true;
			else 
				return false;
		}
		return false;
	}
    
    //멤버변수가 하나일때 비교대상 : 나 
    @Override
	public int compareTo(Member member) {
		
		//return (this.memberId - member.memberId);   //오름차순
		return (this.memberId - member.memberId) *  (-1);   //내림 차순
	}
    
    //멤버변수가 2개일때 비교대상 : 너와 나 
    @Override
	public int compareTo(Member Member1, Member Member2) {
		
		//return (this.memberId - member.memberId);   //오름차순
		return (this.memberId - member.memberId) *  (-1);   //내림 차순
	}


}

public class MemberTreeSet {

	private TreeSet<Member> treeSet;

	public MemberTreeSet(){
		treeSet = new TreeSet<Member>(new Member());
	}
	
	public void addMember(Member member){
		treeSet.add(member);
	}
	
	public boolean removeMember(int memberId){
		
		Iterator<Member> ir = treeSet.iterator();
		
		while( ir.hasNext()){
			Member member = ir.next();
			int tempId = member.getMemberId();
			if( tempId == memberId){
				treeSet.remove(member);
				return true;
			}
		}
		
		System.out.println(memberId + "가 존재하지 않습니다");
		return false;
	}
	
	public void showAllMember(){
		for(Member member : treeSet){
			System.out.println(member);
		}
		System.out.println();
	}
}
public class MemberTreeSetTest {

	public static void main(String[] args) {

		MemberTreeSet memberTreeSet = new MemberTreeSet();
		
		Member memberKim = new Member(1003, "김유신");
		Member memberLee = new Member(1001, "이순신");
		Member memberKang = new Member(1002, "강감찬");
		
		memberTreeSet.addMember(memberKim);
		memberTreeSet.addMember(memberLee);
		memberTreeSet.addMember(memberKang);
		memberTreeSet.showAllMember();
		
	}
}

이미 오름차순으로 되어있는데 내림차순으로 바꾸고 싶을때 

class MyCompare implements Comparator<String>{

	@Override
	public int compare(String s1, String s2) {
		return (s1.compareTo(s2)) *-1 ;
	}
}

public class ComparatorTest {
	
	public static void main(String[] args) {
		
		Set<String> set = new TreeSet<String>(new MyCompare());
		set.add("aaa");
		set.add("ccc");
		set.add("bbb");
				
		System.out.println(set);
	}
}