CF_10_이진 트리, TreeSet 클래스

charl hi·2021년 9월 21일

JAVA_CF

목록 보기

10/12

이진 트리(binary tree)

맨 위의 첫요소가 루트(root)
요소 하나하나가 TreeNode
모든 노드가 최대 2개(0~2)의 하위 노드를 갖는다.
상위노드-하위노드의 상속관계 : 상위노드는 하위노드의 부모

이진 탐색 트리(binary search tree)

이진 트리의 한 종류
✨✨부모보다 작은 값은 왼쪽, 큰 값은 오른쪽에 저장
- ✨새 요소가 들어올 때마다 계속 루트부터 비교하여 아래로 내려온다.
단점 : HashSet보다 데이터 추가, 삭제에 시간이 더 걸림(반복적인 비교 후 저장)

TreeSet

✨이진 탐색 트리로 구현
범위 탐색(from~to)과 ✨✨정렬에 유리하다.
각 노드가 나무형태로 연결(LinkedList의 변형)

사실 표현하면

데이터 저장과정

add(Object o)

boolean add(Object o)
HashSet과 달리 저장할 때마다 ✨✨compare()를 호출해서 비교
✨새 요소가 들어올 때마다 계속 루트부터 비교하여 아래로 내려온다.
-> 작으면 왼쪽, 크면 오른쪽에 저장

생성자

1. `TreeSet()`

3번 생성자처럼 내가 정렬기준을 안 주면, ✨✨저장하려는 객체의 comparaeTo()을 사용하여 비교한다.

1) 💖💖 클래스 implements Comparable{}

2) 💖💖 public int compareTo(Object o) 로 구현부 완성

0 : 어떤 걸 add해도 하나만 생성됨

1 :

[Test@1f32e575, Test@279f2327]

-1 :

[Test@1f32e575, Test@279f2327]

0 :

[Test@279f2327]

2. `TreeSet(Collectoin c)`

컬렉션 c에 있는 객체들 저장하는 TreeSet 생성

3. ✨`TreeSet(Comparator comp)`

1번 생성자가 아니면
(필수)주어진 정렬기준으로 정렬하는 TreeSet 생성

1) 💖💖 클래스 implements Comparator{}

2) 💖💖 public int compare(Object o1, Object o2) 로 구현부 완성

0 : 어떤 걸 add해도 하나만 생성됨

3) 💖✨ 선언 : TreeSet(new 클래스명())

1 :

[TestCom@28a418fc, TestCom@5305068a, 1z, 1]

-1 :

[1, 1z, TestCom@28a418fc, TestCom@5305068a]

0 :

[TestCom@28a418fc]

메소드

추가

boolean add(Object o)

HashSet과 달리 저장할 때마다 ✨✨compare()를 호출해서 비교
✨새 요소가 들어올 때마다 계속 루트부터 비교하여 아래로 내려온다.
-> 작으면 왼쪽, 크면 오른쪽에 저장

객체 반환(하나)

첫번째 / 마지막

Object first()

정렬된 순서에서 첫번째 객체 반환

Object last()

정렬된 순서에서 마지막 객체 반환

올림 / 버림

Object ceiling(Object o)

객체 o와 같거나 큰 값을 가진 가장 가까운 값의 객체를 반환. 없으면 null

Object floor(Object o)

객체 o와 같거나 작은 값을 가진 가장 가까운 값의 객체를 반환. 없으면 null

큰 / 작은

Object higher(Object o)

객체 o보다 큰 값을 가진 가장 가까운 값의 객체를 반환. 없으면 null

Object lower(Object o)

객체 o보다 작은 값을 가진 가장 가까운 값의 객체를 반환. 없으면 null

SortedSet 반환(여러개)

✨범위검색

SortedSet subSet(Object fromElement, Object toElement)

fromElement부터~ toElement-1 까지의 범위 검색의 결과를 반환

SortedSet headSet(Object toElement)

객체 toElement보다 작은 값의 객체들을 반환
toElement의 왼쪽가지 아래

SortedSet tailSet(Object fromElement)

객체 fromElement보다 큰 값의 객체들을 반환
fromElement의 오른쪽가지 아래

ex11_13

import java.util.Collections;
import java.util.Comparator;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Set;
import java.util.TreeSet;

public class Ex11_13 {

	public static void main(String[] args) {
		Set setHash = new HashSet();
		Set setTree = new TreeSet();
		
		for(int i=0; setHash.size()<6; i++) {
			int num = (int)(Math.random()*45 +1);	//1<= x <46
			setHash.add(new Integer(num));	//setHash.add(num)도 가능
		}
		System.out.println("=== 기본 HashSet ===");
		System.out.println(setHash);	//정렬X
		//정렬하려면 list에 저장하기!!
		
		System.out.println("=== 정렬 후 HashSet ===");
		List list = new LinkedList(setHash);
		Collections.sort(list);
		System.out.println(list);

		for(int i=0; setTree.size()<6; i++) {
			int num = (int)(Math.random()*45 +1);	//1<= x <46
			setTree.add(new Integer(num));	//setHash.add(num)도 가능
		}
		System.out.println("=== 이미 정렬된 TreeSet ===");
		System.out.println(setTree);	//정렬O	
		//정렬이 따로 해줄 필요가 없다!
		
		Set set = new TreeSet(new TestCom());	//비교기준을 넣어야함
		set.add(new TestCom());
		set.add(new TestCom());
		set.add("1z");
		set.add(new Integer(1));
		System.out.println(set);
		
		Set set2 = new TreeSet();	
		set2.add(new Test());
		set2.add(new Test());
//		set2.add("1z");	신기하게 이런것들은 안되나보다
//		set2.add(new Integer(1));
		System.out.println(set2);
	}

}

class Test implements Comparable{

	@Override
	public int compareTo(Object o) {
		// TODO Auto-generated method stub
		return 0;
	}
	
}


class TestCom implements Comparator{

	@Override
	public int compare(Object o1, Object o2) {
		// TODO Auto-generated method stub
		return 1;
	}
	
}

=== 기본 HashSet ===
[1, 18, 36, 4, 10, 11]
=== 정렬 후 HashSet ===
[1, 4, 10, 11, 18, 36]
=== 이미 정렬된 TreeSet ===
[8, 18, 21, 27, 34, 41]
[TestCom@28a418fc, TestCom@5305068a, 1z, 1]
[Test@279f2327]

ex11_14

import java.util.TreeSet;

public class Ex11_14 {

	public static void main(String[] args) {
		TreeSet set = new TreeSet();
		
		String from = "b";
		String to = "d";
		
		set.add("abc");      set.add("alien");    set.add("bat");
		set.add("car");      set.add("Car");      set.add("disc");
		set.add("dance");    set.add("dZZZZ");    set.add("dzzz");
		set.add("elephant"); set.add("elevator"); set.add("fan");
		set.add("flower");	 set.add("dzzy");	  set.add("dzzzz"); 
		set.add("dzzY");
		
		System.out.println(set);
		System.out.println("range search : "+from+" to "+to);
		System.out.println("result1 : "+set.subSet(from, to));	//b~c
		System.out.println("range search : "+from+" to "+to+"zzy");
		System.out.println("result2 : "+set.subSet(from, to+"zzy"));
		System.out.println("range search : "+from+" to "+to+"zzzY");
		System.out.println("result3 : "+set.subSet(from, to+"zzzY"));
		System.out.println("range search : "+from+" to "+to+"zzzz");
		System.out.println("result4 : "+set.subSet(from, to+"zzzz"));

	}

}

[Car, abc, alien, bat, car, dZZZZ, dance, disc, dzzY, dzzy, dzzz, dzzzz, elephant, elevator, fan, flower]
range search : b to d
result1 : [bat, car]
range search : b to dzzy
result2 : [bat, car, dZZZZ, dance, disc, dzzY]
range search : b to dzzzY
result3 : [bat, car, dZZZZ, dance, disc, dzzY, dzzy, dzzz]
range search : b to dzzzz
result4 : [bat, car, dZZZZ, dance, disc, dzzY, dzzy, dzzz]

ex11_15

import java.util.TreeSet;

public class Ex11_15 {

	public static void main(String[] args) {
		TreeSet set = new TreeSet();
		int[] score = {80,95,50,35,45,65,10,100};
		
		for(int i=0; i<score.length; i++) {
			set.add(new Integer(score[i]));
		}
		
		System.out.println("50보다 작은 값 : "+set.headSet(new Integer(50)));
		System.out.println("50보다 큰 값 : "+set.tailSet(new Integer(50)));
		System.out.println("40과 80사이의 값 : "+set.subSet(new Integer(40), new Integer(80)));

	}

}

50보다 작은 값 : [10, 35, 45]
50보다 큰 값 : [50, 65, 80, 95, 100]
40과 80사이의 값 : [45, 50, 65]

Q) 👀👀여기서 맨 윗줄 TreeSet -> Set 으로 바꿔도 될까??

A) NOPE!!!

headSet, tailSet, subSet 은 TreeSet에만 있는 메소드이기 때문이다!!

트리 순회(tree traversal)

트리 순회 : 이진 트리의 모든 노드를 한번씩 읽는 것
종류
- 전위 순회(pre order) : 부모 먼저 - 자식 나중에
- 후위 순회(post order) : 자식 먼저 - 부모 나중에
- ✨중위 순회(in order) : 부모를 가운데에 놓고, 왼쪽 자식 - 부모 - 오른쪽 자식
- 레벨 순회(level order) : root - 그 다음 층 - 그 다음 층 ...

중위 순회

중위 순회하면 ✨오름차순을 정렬된다.
-> 그래서 TreeSet이 정렬에 유리하다는 것!

Ref

charl hi

이전 포스트

CF_09_HashSet 클래스

다음 포스트

CF_10_이진 트리, TreeSet 클래스

JAVA_CF

이진 트리(binary tree)

이진 탐색 트리(binary search tree)

TreeSet

데이터 저장과정

add(Object o)

생성자

1. `TreeSet()`

2. `TreeSet(Collectoin c)`

3. ✨`TreeSet(Comparator comp)`

메소드

추가

객체 반환(하나)

첫번째 / 마지막

올림 / 버림

큰 / 작은

SortedSet 반환(여러개)

✨범위검색

Q) 👀👀여기서 맨 윗줄 TreeSet -> Set 으로 바꿔도 될까??

A) NOPE!!!

트리 순회(tree traversal)

중위 순회

Ref

CF_09_HashSet 클래스

CF_11_HashMap, TreeMap 클래스

0개의 댓글

CF_10_이진 트리, TreeSet 클래스

JAVA_CF

이진 트리(binary tree)

이진 탐색 트리(binary search tree)

TreeSet

데이터 저장과정

add(Object o)

생성자

1. TreeSet()

2. TreeSet(Collectoin c)

3. ✨TreeSet(Comparator comp)

메소드

추가

객체 반환(하나)

첫번째 / 마지막

올림 / 버림

큰 / 작은

SortedSet 반환(여러개)

✨범위검색

Q) 👀👀여기서 맨 윗줄 TreeSet -> Set 으로 바꿔도 될까??

A) NOPE!!!

트리 순회(tree traversal)

중위 순회

Ref

CF_09_HashSet 클래스

CF_11_HashMap, TreeMap 클래스

0개의 댓글

1. `TreeSet()`

2. `TreeSet(Collectoin c)`

3. ✨`TreeSet(Comparator comp)`