컬렉션 프레임 워크는 검색 기능을 강화시킨 TreeSet과 TreeMap을 제공하고 있다. 이 컬렉션들은 이진 트리(binary tree)를 이용해서 계층적 구조(Tree 구조)를 가지면서 객체를 저장한다.
이진 트리 구조
여러개의 노드가 트리 형태로 연결된 구조로, 루트 노드라고 불리는 하나의 노드에서부터 시작해 각 노드에 최대 2개의 노드를 연결할 수 있는 구조를 가지고 있다.
첫번째로 저장되는 값은 루트 노드가 되고, 두번째 부터는 값의 크기를 비교해 트리를 만들며 내려간다. 작은 값은 왼쪽에, 큰 값은 오른쪽에 저장한다.
-> 이진 트리가 범위 검색을 쉽게 할 수 있는 이유는 값들이 정렬되어 있어 그룹핑이 쉽기 때문!
TreeSet
이진 트리를 기반으로한 Set 컬렉션이다. 객체를 저장하면 자동으로 정렬되는데 부모값과 비교해서 낮은 것은 왼쪽 자식 노드에, 높은 것은 오른쪽 자식 노드에 저장한다.
// 생성시 저장할 객체 타입을 파라미터로 표기하고,
// 기본 생성자를 호출하면 된다
TreeSet<E> treeSet = new TreeSet<E>();
사용해보기
TreeSet<Integer> num = new TreeSet<Integer>();
// set 값 넣기
num.add(10);
num.add(8);
num.add(9);
num.add(20);
num.add(45);
num.add(0);
int number = num.first();
System.out.println("제일 낮은 객체(숫자)를 리턴 : " + number);
System.out.println("---------------------------");
number = num.last();
System.out.println("제일 높은 객체(숫자)를 리턴 : " + number);
System.out.println("---------------------------");
number = num.lower(30);
System.out.println("30점보다 작은 점수 중 가장 가까운 수를 리턴 : " + number);
// 만약 가장 작은수를 lower로 넣으면? = 에러남
//number = num.lower(0);
//System.out.println("0점 보다 작은 값 있어? : " + number);
System.out.println("----------------------------");
number = num.higher(20);
System.out.println("20점보다 높은 점수 : " + number);
// 만약에 가장 높은 수를 higher에 넣으면? = 에러남
//number = num.higher(45);
//System.out.println("45점보다 높은 점수 있어? : " + number);
System.out.println("----------------------------");
number = num.floor(20);
System.out.println("20이랑 똑같은 수가 있으면 그거 가져오고, 아니면 바로 아래의 값 리턴 : " + number);
System.out.println("----------------------------");
number = num.ceiling(0);
System.out.println("0이랑 똑같은 수 있으면 그거 가져오고, 아니면 바로 위 값 리턴 : " + number);
System.out.println("----------------------------");
System.out.println("현재 num의 사이즈 : " + num.size());
number = num.pollFirst();
System.out.println("가장 높은 값을 읽고 제거.제거한 값 : " + number);
System.out.println("제거하고 난 뒤 num 사이즈 : " + num.size());실행 모습
1. .descendingIterator()
2. .descendingSet() -> 두번하면 올림차순이 됨
NavigableSet은 TreeSet과 마찬가지로 first(), last(), lower(), higher(), floor(), ceiling() 메소드를 제공하고, 정렬 순서르 바꾸는 descendingSet(0메소드도 제공한다.
정렬 관련 메소드 사용해보기
TreeSet<Integer> num = new TreeSet<Integer>();
// set 값 넣기
num.add(10);
num.add(8);
num.add(9);
num.add(20);
num.add(45);
num.add(0);
// 내림차순으로 출력합시다 1
Iterator<Integer> it = num.descendingIterator();
while(it.hasNext()) {
Integer ss = it.next();
System.out.println(ss);
}
System.out.println("-----------");
// 내림차순으로 출력합시다 2
NavigableSet<Integer> ds = num.descendingSet();
it = ds.iterator();
while(it.hasNext()) {
Integer ss = it.next();
System.out.println(ss);
}
System.out.println("-----------");
// 올림차순은 내림차순을 두번 하면 됨?? - 되네 뭐냐
ds = ds.descendingSet();
it = ds.iterator();
while(it.hasNext()) {
Integer ss = it.next();
System.out.println(ss);
}
System.out.println("-----------");실행 모습
45 20 10 9 8 0 ----------- 45 20 10 9 8 0 ----------- 0 8 9 10 20 45 -----------
범위 검색 관련 메소드 사용해보기
TreeSet<Integer> ts = new TreeSet<Integer>();
ts.add(100);
ts.add(95);
ts.add(85);
ts.add(90);
ts.add(80);
// x < 90
// 90 보다 작은 객체 모두 나와라
SortedSet<Integer> a90 = ts.headSet(90);
Iterator<Integer> it = a90.iterator();
while (it.hasNext()) {
System.out.print(it.next() + " ");
}
System.out.println("\n--------------------------");
// x <= 90
// 90 도 포함해서 90보다 작은 객체들 모두
SortedSet<Integer> b90 = ts.headSet(90, true);
it = b90.iterator();
while(it.hasNext()) {
System.out.print(it.next() + " ");
}
System.out.println("\n--------------------------");
// 85 < x
SortedSet<Integer> a85 = ts.tailSet(85);
it = a85.iterator();
while(it.hasNext()) {
System.out.print(it.next() + " ");
}
System.out.println("\n--------------------------");
// 85 <= x
SortedSet<Integer> b85 = ts.tailSet(85,true);
it = b85.iterator();
while(it.hasNext()) {
System.out.print(it.next() + " ");
}
System.out.println("\n--------------------------");
// 85 < x < 95
SortedSet<Integer> a8595 = ts.subSet(85, false, 95, false);
it = a8595.iterator();
while(it.hasNext()) {
System.out.print(it.next() + " ");
}
System.out.println("\n--------------------------");
// 85 <= x <= 95
SortedSet<Integer> b8595 = ts.subSet(85, true, 95, true);
it = b8595.iterator();
while(it.hasNext()) {
System.out.print(it.next() + " ");
}
System.out.println("\n--------------------------");실행 모습
TreeMap
TreeSet과의 차이점은 키와 값이 저장된 Map.Entry를 저장한다는 점이다.
TreeMap에 객체 저장하면 자동으로 정렬되는데, 기본적으로 부모 키값과 비교해서 키 값이 낮은 것은 왼쪽 자식 노드에, 키 값이 높은 것은 오른쪽 자식 노드에 Map.Entry 객체를 저장한다.
다음은 TreeMap이 가지고 있는 검색 관련 메소드들이다
검색관련 메소드 사용해보기
값 입력은 .put
new Integer(10) == int 10
// 키로 점수를 넣고
// 값으로 이름을 넣었음
TreeMap<Integer, String> scores = new TreeMap<Integer, String>();
// TreeMap은 값 넣어줄때
// add ㄴㄴ put ㅇㅇ
// 값은 중복될 수 있지만, 키는 중복 xxx
scores.put(new Integer(87), "홍길동");
scores.put(new Integer(98), "이동수");
scores.put(new Integer(75), "박길순");
scores.put(new Integer(95), "신용권");
scores.put(new Integer(80), "김자바");
// firstEntry 해보기
// 제일 낮은 Map.Entry를 리턴
Entry<Integer, String> result1 = scores.firstEntry();
System.out.println("가장 낮은 점수 : " + result1.getKey() + "점\t\t학생명 : " + result1.getValue());
// lastEntry()
// 제일 높은 Map.Entry를 리턴
Entry<Integer, String> result2 = scores.lastEntry();
System.out.println("가장 높은 점수 : " + result2.getKey() + "점\t\t학생명 : " + result2.getValue());
// lowerEntry(K Key)
// 주어진 키보다 바로 아래 Map.Entry를 리턴
// x < 90
Entry<Integer, String> result3 = scores.lowerEntry(90);
System.out.println("90 보다 바로 아래 점수 : " + result3.getKey() + "점\t학생명 : " + result3.getValue());
// higherEntry(K Key)
// 주어진 키보다 바로 위 Map.Entry를 리턴
// x > 80
Entry<Integer, String> result4 = scores.higherEntry(80);
System.out.println("80보다 바로 위 점수 : " + result4.getKey() + "점\t학생명 : " + result4.getValue());
// floorEntry(K Key)
// 주어진 키와 동등한 키 있으면 해당 Map.Entry를 리턴, 없다면 바로 아래의 Map.Entry리턴
// x <= 90
Entry<Integer, String> result5 = scores.floorEntry(90);
System.out.println("x <= 90 : " + result5.getKey() + "점\t\t학생명 : " + result5.getValue());
// ceilingEntry(K Key)
// 주어진 키와 동등한 키 있으면 해당 Map.Entry리턴 없다면 바로 위 Map.Entry 리턴
// x >= 80
Entry<Integer, String> result6 = scores.ceilingEntry(90);
System.out.println("x >= 90 : " + result6.getKey() + "점\t\t학생명 : " + result6.getValue());사용 모습
가장 낮은 점수 : 75점 학생명 : 박길순 가장 높은 점수 : 98점 학생명 : 이동수 90 보다 바로 아래 점수 : 87점 학생명 : 홍길동 80보다 바로 위 점수 : 87점 학생명 : 홍길동 x <= 90 : 87점 학생명 : 홍길동 x >= 90 : 95점 학생명 : 신용권
정렬관련 메소드 사용해보기
TreeMap<Integer, String> scores = new TreeMap<Integer, String>();
scores.put(new Integer(87), "홍길동");
scores.put(new Integer(98), "이동수");
scores.put(new Integer(75), "박길순");
scores.put(new Integer(95), "신용권");
scores.put(new Integer(80), "김자바");
// 키값으로 내림차순해서 출력하는 코드 1
NavigableMap<Integer, String> deMap = scores.descendingMap();
Set<Map.Entry<Integer, String>> des = deMap.entrySet();
for (Entry<Integer, String> entry : des) {
System.out.println("학생 : " + entry.getValue() + "\t" + entry.getKey() + "점");
}
System.out.println();
// 키값으로 내림차순해서 출력하는 코드 2
NavigableSet<Integer> keyset = scores.descendingKeySet();
Iterator<Integer> it = keyset.iterator();
while (it.hasNext()) {
Integer key = it.next();
String value = scores.get(key);
System.out.println("학생 : " + value + "\t" + key + "점");
}
System.out.println();
// 키값으로 올림차순해서 출력하는 코드 1
// descendingMap() 을 두 번 사용하면 올림차순이 된다
deMap = deMap.descendingMap();
des = deMap.entrySet();
for (Entry<Integer, String> entry : des) {
System.out.println("학생 : " + entry.getValue() + "\t" + entry.getKey() + "점");
}
System.out.println();사용 모습
범위 검색관련 메소드 사용해보기
TreeMap<String, Integer> treeMap = new TreeMap<String, Integer>();
treeMap.put("apple", new Integer(10));
treeMap.put("forever", new Integer(60));
treeMap.put("description", new Integer(40));
treeMap.put("ever", new Integer(50));
treeMap.put("zoo", new Integer(10));
treeMap.put("base", new Integer(20));
treeMap.put("guess", new Integer(70));
treeMap.put("cherry", new Integer(30));
System.out.println("[c~f 사이의 단어 검색]");
// c부터 f까지라서
// 시작이 f로 된 거 까지만 (뒤에 덧붙여진 내용이 있는 forever는 출력되지 x
NavigableMap<String, Integer> reangeMap = treeMap.subMap("c", true, "f", true);
for(Map.Entry<String, Integer> entry : reangeMap.entrySet()) {
System.out.println(entry.getKey() + "-" + entry.getValue() + "페이지");
}사용 모습
[c~f 사이의 단어 검색] cherry-30페이지 description-40페이지 ever-50페이지
Comparable과 Comparator
TreeSet의 객체와 TreeMap의 키는 저장과 동시에 자동 오름차순 정렬된다
: 숫자타입일 경우 값으로
: 문자열 타입일 경우 유니코드로 정렬
트리셋과 트리맵은 정렬을 위해 java.lang.Comparable 구현 객체를 요구한다
(implements Comparable 하라는 말)
: 인티져, 더블, 스트링 모두 Comparable 인터페이스 구현
Comparable에는 compareTo()메소드가 정의 되어 있기 때문에 사용자 정의 클래스에서는 이 메소드를 오버라이딩하여 다음과 같이 리턴 값을 만들어 내야 한다.
사용해보기
public class ComparableEx {
public static void main(String[] args) {
// 트리로 달아줄 것이다 Person이라는 클래스를
TreeSet<Person> treeSet = new TreeSet<Person>();
// 트리에 노드로 달것이다 = 자료를 트리에 달아주기
treeSet.add(new Person("홍길동", 45));
treeSet.add(new Person("김자바", 25));
treeSet.add(new Person("박지원", 31));
// 출력해보기
// index로 출력할 수 없기 때문에 Iterator사용
Iterator<Person> it = treeSet.iterator();
while(it.hasNext()) {
Person p = it.next();
System.out.println(p.name + " : " + p.age);
}
System.out.println("--------------------------------");
// 트리는 저장과 동시에 자동 오름차순으로 정렬되는데
// 내림차순으로 하고 싶다면 Person 의 비교 혹은 리턴값을 반대로 바꾸면 된다
TreeSet<Person1> treeSet2 = new TreeSet<Person1>();
treeSet2.add(new Person1("홍길동", 45));
treeSet2.add(new Person1("김자바", 25));
treeSet2.add(new Person1("박지원", 31));
Iterator<Person1> it2 = treeSet2.iterator();
while(it2.hasNext()) {
Person1 p = it2.next();
System.out.println(p.name + " : " + p.age);
}
System.out.println("--------------------------------");
// 나이순으로 내림차순 정렬하고
// 나이가 같으면 이름으로 오름차순 정렬하기
TreeSet<Person2> treeSet3 = new TreeSet<Person2>();
treeSet3.add(new Person2("홍길동", 45));
treeSet3.add(new Person2("김자바", 25));
treeSet3.add(new Person2("박지원", 31));
treeSet3.add(new Person2("고길동", 45));
treeSet3.add(new Person2("이이것", 25));
treeSet3.add(new Person2("김둘리", 31));
Iterator<Person2> it3 = treeSet3.iterator();
while(it3.hasNext()) {
Person2 p = it3.next();
System.out.println(p.name + " : " + p.age);
}
System.out.println("--------------------------------");
}
}
// Tree에 달아줄 객체는 Comparable 구현 객체로 만들어야 에러가 없다
// implements Comparable<만들어줄 객체>
class Person implements Comparable<Person> {
public String name;
public int age;
public Person(String name, int age) {
this.name = name;
this.age = age;
}
// 비교 기준을 정의하는 메소드
// 1. 비교자료1 < 비교자료 2 ==> 음수
// 2. 비교자료1 == 비교자료2 ==> 0
// 3. 비교자료1 > 비교자료 2 ==> 양수
// 저장된 나이와 새로 들어온 나이를 비교해서 트리 달기
@Override
public int compareTo(Person o) {
if(age < o.age) {
return -1;
} else if(age == o.age) {
return 0;
} else {
return 1;
}
}
}
class Person1 implements Comparable<Person1> {
public String name;
public int age;
public Person1(String name, int age) {
this.name = name;
this.age = age;
}
// 이름을 내림차순으로
@Override
public int compareTo(Person1 o) {
if(name.compareTo(o.name) > 0) {
return -1;
} else if(name.compareTo(o.name) == 0) {
return 0;
} else {
return 1;
}
}
}
class Person2 implements Comparable<Person2>{
public String name;
public int age;
public Person2(String name, int age) {
this.name = name;
this.age = age;
}
@Override
public int compareTo(Person2 o) {
if(age < o.age) {
return 1;
} else if(age == o.age && name.compareTo(o.name) > 0) {
return 1;
} else if(age == o.age && name.compareTo(o.name) == 0) {
return 0;
} else {
return -1;
}
}
}실행 모습
김자바 : 25 박지원 : 31 홍길동 : 45 -------------------------------- 홍길동 : 45 박지원 : 31 김자바 : 25 -------------------------------- 고길동 : 45 홍길동 : 45 김둘리 : 31 박지원 : 31 김자바 : 25 이이것 : 25 --------------------------------
정렬자를 사용해보기
TreeSet의 객체와 TreeMap의 키가 Comparable을 구현하고 있지 않을 경우, 저장하는 순간 ClassCastException이 발생한다. TreeSet 또는 TreeMap 생성자의 매개값으로 정렬자(Comparator)를 제공하면 Comparable 비구현 객체도 정렬 시킬 수 있다.
정렬자를 사용해보고, 내림차순 올림차순으로 정렬한다.
public class DescendingComparator {
public static void main(String[] args) {
// Fruit에 만들어 주지 않고
// 아예 따로 비교 클래스를 만드는 방법
TreeSet<Fruit> treeSet = new TreeSet(new DescendingComparator());
treeSet.add(new Fruit("포도", 3000));
treeSet.add(new Fruit("수박", 10000));
treeSet.add(new Fruit("딸기", 6000));
treeSet.add(new Fruit("바나나", 4000));
treeSet.add(new Fruit("체리", 5000));
treeSet.add(new Fruit("수박", 7000));
// 가격을 내림차순으로 정렬
Iterator<Fruit> it = treeSet.iterator();
while(it.hasNext()) {
Fruit fruit = it.next();
System.out.println(fruit.name + "\t" + fruit.price);
}
System.out.println("-------------------------");
// 과일명으로 오름차순 정렬
TreeSet<Fruit> treeSet1 = new TreeSet(new DescendingComparator1());
treeSet1.add(new Fruit("포도", 3000));
treeSet1.add(new Fruit("수박", 10000));
treeSet1.add(new Fruit("딸기", 6000));
treeSet1.add(new Fruit("바나나", 4000));
treeSet1.add(new Fruit("체리", 5000));
// set계열이기때문에(이름기준) 중복은 달릴 수 없다.
// treeSet1.add(new Fruit("수박", 7000));
Iterator<Fruit> it2 = treeSet1.iterator();
while (it2.hasNext()) {
Fruit fruit1 = it2.next();
System.out.println(fruit1.name + "\t" + fruit1.price);
}
System.out.println("-------------------------");
// 익명 구현 객체로
TreeSet<Fruit> treeSet2 = new TreeSet<Fruit>(new Comparator<Fruit>() {
@Override
public int compare(Fruit o1, Fruit o2) {
// 근데 어차피 중복이 안들어가는데 이렇게 이중으로 하는게 의미가 있나..?
if(o1.price < o2.price) {
return -1;
} else if(o1.price == o2.price && o1.name.compareTo(o2.name) < 0) {
return 0;
} else if(o1.price == o2.price && o1.name.compareTo(o2.name) > 0) {
return 0;
} else {
return 1;
}
}
});
treeSet2.add(new Fruit("포도", 3000));
treeSet2.add(new Fruit("수박", 10000));
treeSet2.add(new Fruit("딸기", 6000));
treeSet2.add(new Fruit("바나나", 4000));
treeSet2.add(new Fruit("체리", 5000));
// set계열이기때문에 중복은 달릴 수 없다.
// treeSet1.add(new Fruit("수박", 7000));
Iterator<Fruit> it3 = treeSet2.iterator();
while (it3.hasNext()) {
Fruit fruit2 = it3.next();
System.out.println(fruit2.name + "\t" + fruit2.price);
}
System.out.println("-------------------------");
}
}
// DescendingComparator<비교 대상자>
class DescendingComparator implements Comparator<Fruit> {
@Override
public int compare(Fruit o1, Fruit o2) {
// 가격으로 내림차순
if (o1.price < o2.price) {
return 1;
} else if (o1.price == o2.price) {
return 0;
} else {
return -1;
}
}
}
class DescendingComparator1 implements Comparator<Fruit> {
@Override
public int compare(Fruit o1, Fruit o2) {
// 과일명 오름차순
if (o1.name.compareTo(o2.name) > 0) {
return 1;
} else if (o1.name.compareTo(o2.name) == 0) {
return 0;
} else {
return -1;
}
}
}
class Fruit {
String name;
int price;
public Fruit(String name, int price) {
this.name = name;
this.price = price;
}
}실행 모습
수박 10000 수박 7000 딸기 6000 체리 5000 바나나 4000 포도 3000 ------------------------- 딸기 6000 바나나 4000 수박 10000 체리 5000 포도 3000 ------------------------- 포도 3000 바나나 4000 체리 5000 딸기 6000 수박 10000 -------------------------
연습하기 01
배열을 설정하고 리스트로 바꿔 정렬하기
// example 배열 설정
String[] example = {"Nice", "to", "meet", "you", "!" };
// 배열을 리스트로 바꾸기
// Arrays.asList()
List<String> list = Arrays.asList(example);
// 정렬
Collections.sort(list);
System.out.println(list);
// 작은 수부터 큰 수로 정렬(올림차순)
Integer[] ex1 = { 10, 90, 0, -9, 30 };
List<Integer> list1 = Arrays.asList(ex1);
Collections.sort(list1);
System.out.println(list1);
// 내림차순을(사용자 정의를) 하고 싶다면 익명 구현 객체로 실행 내용을 지정
Integer[] ex2 = { 10, 90, 0, -9, 30 };
List<Integer> list2 = Arrays.asList(ex2);
Collections.sort(list2, new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
if(o1 < o2) {
return 1;
} else if(o1==o2) {
return 0;
} else {
return -1;
}
}
});
System.out.println(list2);실행 모습
[!, Nice, meet, to, you] [-9, 0, 10, 30, 90] [90, 30, 10, 0, -9]
연습해보기 02
- 학번 순으로 비교해서 출력
- 배열을 내림차순 정리해서 출력
- 반대로 뒤집어 출력할때 꼭 descending을 두번 사용하지 않아도 된다. revers()를 사용해도 된다
// 학변을 비교해서 출력한다
public class Test2 {
public static void main(String[] args) {
// Student 객체 생성
Student[] st = {new Student(02, "김자바"), new Student(03, "이곡길"), new Student(01, "한태주"), new Student(04, "한옥자")};
// 배열을 컬렉션의 list로 변경하기
List<Student> list = Arrays.asList(st);
// 배열 정렬
Collections.sort(list, new Comparator<Student>() {
@Override
public int compare(Student o1, Student o2) {
// if 로 썼던 내용을 이렇게 적어도 됨
return o1.num - o2.num;
}
});
System.out.println(list);
System.out.println("--------------------------------");
// Collections.sort(리스트, Collections.reverseOrder())
// 사용시 알아서 내림차순 정렬
String[] ex = {"Nice", "to", "meet", "you", "!" };
List<String> elist = Arrays.asList(ex);
Collections.sort(elist, Collections.reverseOrder());
System.out.println(elist);
System.out.println("--------------------------------");
// Collections.revers() 를 사용해도 됨!
List<String> elist2 = Arrays.asList(ex);
Collections.reverse(elist2);
System.out.println(elist2);
}
}
class Student {
int num;
String name;
public Student(int num, String name) {
this.num = num;
this.name = name;
}
@Override
public String toString() {
return name + " " + num;
}
}실행 모습
[한태주 1, 김자바 2, 이곡길 3, 한옥자 4] -------------------------------- [you, to, meet, Nice, !] -------------------------------- [!, Nice, meet, to, you]
연습해보기 03 - .shuffle
: 리스트에 존재하는 정렬을 파괴해 원소들의 순서를 랜덤하게 만듦
: 정렬과는 반대 동작
: 주로 게임 구현시 유용하게 쓰인다 (ex. 게임에서 카드 섞기, 사다리 게임)
ArrayList<Integer> shffle = new ArrayList<Integer>();
// 0번부터 10번 카드까지 넣어주기
for(int i=0; i<11; i++) {
shffle.add(i);
}
// 섞기
Collections.shuffle(shffle);
System.out.println(shffle);실행 모습
1.[8, 4, 2, 6, 3, 10, 7, 1, 9, 5, 0]
2.[4, 2, 0, 8, 10, 5, 6, 9, 1, 3, 7]
3.[9, 10, 8, 2, 4, 1, 7, 3, 5, 0, 6]
실행 할때마다 출력 모습이 바뀌는 것을 볼 수 있다.
