컬렉션 프레임워크는 검색 기능을 강화시킨 TreeSet과 TreeMap을 제공하고 있다.
이름에서 알 수 있듯이 TreeSet은 Set 컬렉션이고, TreeMap은 Map 컬렉션이다.
이컬렉션들은 이진 (binary tree)를 이용해서 계층적 구조(Tree 구조)를 가지면서 객체를 저장한다.
이진트리 구조
이진 트리(Binary tree)는 여러 개의 노드(node)가 트리 형태로 연결된 구조로,
루트 노드(root node) 라고 불리는 하나의 노드에서 부터 시작해서 각 노드에 최대 2개의 노드를 연결할 수 있는 구조를 가지고 있다.
위 아래로 연결된 두 노드를 부모-자식 관계에 있다고 하며 위의 노드를 부모 노드, 아래의 노드를 자식 노드라고 한다.
하나의 부모 노드는 최대 두개의 자식 노드와 연결 될 수 있다.
그림에서 보면 A노드는 B, C 노드의 부모 노드이고, B,C 노드는 A노드의 자식 노드이다
이진 트리는 부모노드의 값보다 작은 노드는 왼쪽에 위치 시키고, 부모 노드의 값보다 큰 노드는 오른쪽에 위치 시킨다.
첫 번째로 저장되는 값은 루토 노드가 되고, 두번째 값은 루트 노드부터 시작해서 값의 크기를 비교하면서 트리를 따라 내려간다.
작은 값은 왼쪽에, 큰 값은 오른쪽 저장한다.
숫자가 아닌 문자를 저장할 경우에는 문자의 유니코드 값으로 비교한다.
이렇게 트리를 구성하면, 왼쪽 마지막 노드가 제일 작은 값이 되고, 오른쪽 마지막 노드가 가장 큰 값이 된다.
왼쪽 마지막 노드에서부터 오른쪽 마지막 노드까지 [왼쪽 노드 -> 부모노드 -> 오른쪽 노드]순으로 값을면
오름차순으로 정렬된 값을 얻을 수 있고 반대로 오른쪽 마지막노드에서부터 왼쪽 마지막 노드까지 [오른쪽 노드 -> 부모노드 -> 왼쪽 노드] 순으로 값을 읽으면 내림차순으로 정렬된 값을 얻을 수 있다.
이진 트리가 범위 검색을 쉽게 할 수 있는 이유는 그림에서 보는것과 같이 값들이 정렬되어 있어 그룹핑이 쉽기때문이다.
TreeSet
TreeSet은 이진 트리(binary tree)를 기반으로한 Set 컬렉션이다.
하나의 노드는 노드값인 value 와 왼쪽과 오른쪽 자식 노드를 참조하기 위한 두개의 변수로 구성된다.
TreeSet에 객체를 저장하면 자동으로 정렬되는데
부모 값과 비교해서 낮은 것은 왼쪽 자식 노드에 높은것은 오른쪽 자식 노드에 저장한다.
TreeSet을 생성하기 위해서는 저장될 객체 타입을 파라미터로 표기하고 기본 생성자를 호출하면 된다.
TreeSet<E> treeSet = new TreeSet<E>();
String 객체를 저장하는 TreeSet은 다음과 같이 생성할 수 있다.
TreeSet<String> treeSet = new TreeSet<String>();
Set 인터페이스 타입 변수에 대입해도 되지만 TreeSet 클래스 타입으로 대입한 이유는 객체를 찾거나
범위 검색과 관련된 메소드를 사용하기 위해서 이다.
다음은 TreeSet이 가지고 있는 검색 관련 메소드들이다.
| 리턴 타입 | 메소드 | 설명 |
| E | first() | 제일 낮은 객체를 리턴 |
| E | last() | 제일 높은 객체를 리턴 |
| E | lower(E e) | 주어진 객체 보다 바로 아래 객체를 리턴 |
| E | higher(E e) | 주어진 객체보다 바로 위 객체를 리턴 |
| E | floor(E e) | 주어진 객체와 동등한 객체가 있으면 리턴, 만약 없다면 주어진 객체의 바로 아래의 객체를 리턴 |
| E | ceiling(E e) | 주어진 객체와 동등한 객체가 있으면 리턴, 만약 없다면 주어진 객체의 바로 위의 객체를 리턴 |
| E | pollFirst() | 제일 낮은 객체를 꺼내오고 컬렉션에서 제거함 |
| E | pollLast | 제일높은 객체를 꺼내오고 컬렉션에서 제거함 |
package CollectionFrameWork;
import java.util.TreeSet;
public class TreeSetExample {
public static void main(String[] args) {
TreeSet<Integer> scores = new TreeSet<>();
scores.add(new Integer(90));
scores.add(new Integer(80));
scores.add(new Integer(70));
scores.add(new Integer(60));
scores.add(new Integer(50));
scores.add(new Integer(40));
scores.add(new Integer(30));
scores.add(new Integer(203));
System.out.println("TreeSet: " + scores);
System.out.println("TreeSet: " + scores.first());
System.out.println("TreeSet: " + scores.last());
// System.out.println("TreeSet: " + scores.pollFirst());
// System.out.println("TreeSet: " + scores.pollLast());
System.out.println("TreeSet: " + scores.lower(new Integer(50)));
System.out.println("TreeSet: " + scores.higher(new Integer(50)));
System.out.println("TreeSet: " + scores.floor(new Integer(50)));
System.out.println("TreeSet: " + scores.ceiling(new Integer(50)));
System.out.println("TreeSet: " + scores.headSet(new Integer(50)));
while (scores.size() > 0) {
System.out.println("TreeSet: " + scores.pollFirst());
}
System.out.println("TreeSet: " + scores);
}
}
다음은 TreeSet이 가지고 있는 정렬과 관련된 메소드들이다
| 리턴 타입 | 메소드 | 설명 |
| Iterator<E> | descendingIterator() | 내림차순으로 정렬된 Iterator를 리턴 |
| NavigableSet<E> | descendingSet() | 내림차순으로 정련된 NavigableSet을 반환 |
descendingIterator() 메소드는 내림차순으로 정렬된 Iterator 객체를 리턴
descendingSet() 메소드는 내림차순으로 정려된 NavigableSet 객체를 리턴하는데
NavigableSet은 TreeSet과 마찬가지로 first(), last(), lower(), higher(), floor, ceiling() 메소드를 제공하고
정렬순서를 바꾸는 descendingSet() 메소드도 제공한다.
오름차순으로 정렬하고 싶다면 다음과 같이 descendingSet() 메소드를 두번 호출하면 된다.
NavigableSet<E> descendingSet = treeSet.descendingSEt();
NavigableSet<E> ascendingSet = descendingSet.descendingSet();
package CollectionFrameWork;
import java.util.NavigableSet;
import java.util.TreeSet;
public class TreeSetExample2 {
public static void main(String[] args) {
TreeSet<Integer> ts = new TreeSet<>();
ts.add(10);
ts.add(20);
ts.add(30);
ts.add(40);
ts.add(50);
ts.add(15);
NavigableSet<Integer> ns = ts.descendingSet();
for (Integer i : ns) {
System.out.println(i);
}
System.out.println("-------------------------------");
NavigableSet<Integer> ns2 = ts.subSet(10, true, 40, true);
for (Integer i : ns2) {
System.out.println(i);
}
System.out.println("-------------------------------");
NavigableSet<Integer> ns1 = ns.descendingSet();
for (Integer i : ns1) {
System.out.println(i);
}
System.out.println("-------------------------------");
NavigableSet<Integer> ns3 = ts.headSet(40, true);
for (Integer i : ns3) {
System.out.println(i);
}
System.out.println("-------------------------------");
NavigableSet<Integer> ns4 = ts.tailSet(40, true);
for (Integer i : ns4) {
System.out.println(i);
}
}
}
다음은 TreeSet이 가지고 있는 범위 검색과 관련된 메소드들이다.
| 리턴타입 | 메소드 | 설명 |
| NavigableSet<E> | headSet(E toElement, boolean inclusive) | 주어진 객체 보다 낮은 객체들을 NavigableSet으로 리턴, 주어진 객체 포함 여부는 두번째 매개값에 따라 달라짐 |
| NavigableSet<E> | tailSet(E fromElement, boolean inclusive) | 주어진 객체 보다 높은 객체들을 NavigableSet으로 리턴, 주어진 객체 포함 여부는 두번째 매개값에 따라 달라짐 |
| NavigableSet<E> | subSet(E fromElement, boolean fromInclusive, E toElement, boolean toInclusive) |
시작과 끝으로 주어진 객체 사이의 객체를 NavigableSet으로 리턴, 시작과 끝 객체의 포함 여부는 두 번째, 네 번째 매개값에 따라 달라짐 |
세가지 메소드 중에서 subSet() 메소드의 사용 방법을 자세히 살펴보기로 하자,
subSet() 메소드는 네개의 매개 변수가 있는데,
시작 객체와 끝 객체, 그리고 이 객체들을 포함할지 여부의 boolean 값을 받는다.
시작 객체 < 찾는 객체 < 끝 객체
시작 객체 <= 찾는 객체 <= 끝 객체
NavigableSet<E> set = treeSet.subSet(E fromElement, boolean froInclusive, E toElement, boolean toInclusive)
TreeMap
TreeMap은 이진 트리를 기반으로 한 Map 컬렉션이다.
TreeSet 과의 차이점은 키와 값이 저장된 Map.Entry를 저장한다는 점이다.
TreeMap에 객체를 저장하면 자동으로 정렬되는데,
기본적으로 부모 키값과 비교해서 키값이 낮은 것은 왼쪽 자식 노드에,
키 값이 높은 것은 오른쪽 자식 노드에 Map.Entry 객체를 저장한다.
TreeMap을 생헝하기 위해서는 키로 저장할 객체 타입과 값으로 저장할 객체 타입을 타입 파라미터로 주고 기본 생성자를 호출하면 된다.
TreeMap<K, V> treeMap = new TreeMap<K, V>();
키타입, 값타입 키타입, 값타입
Map 인터페이스 타입 변수에 대입해도 되지만 TreeMap클래스 타입으로 대입한 이유는 특정 객체를 찾거나 범위 검색과 관련된 메소드를 사용하기 위해서 이다.
다음은 TreeMap이 가지고 있는 검색 관련 메소드 들이다.
| 리턴 타입 | 메소드 | 설명 |
| Map.Entry<K,V> | firstEntry() | 제일 낮은 Map.Entry를 리턴 |
| Map.Entry<K,V> | lastEntry() | 제일 높은 Map.Entry를 리턴 |
| Map.Entry<K,V> | lowerEntry(K key) | 주어진 키보다 바로 아래 Map.Entry를 리턴 |
| Map.Entry<K,V> | higherEntry(K key) | 주어진 키보다 바로 위 Map.Entry를 리턴 |
| Map.Entry<K,V> | floorEntry(K key) | 주어진 키와 동등한 키가 있으면 해당 Map.Entry를 리턴, 없다면 주어진 키 바로 아래의 Map.Entry를 리턴 |
| Map.Entry<K,V> | cellingEntry(K key) | 주어진 키와 동등한 키가 있으면 해당 MapEntry를 리턴, 없다면 주어진 키 바로 위의 Map.Entry를 리턴 |
| Map.Entry<K,V> | pollFirstEntry() | 제일 낮은 Map.Entry를 꺼내오고 컬렉션에서 제거함 |
| Map.Entry<K,V> | pollLastEntry() | 제일 높은 Map.Entry를 꺼내오고 컬렉션에서 제거함 |
package CollectionFrameWork;
import java.util.Map;
import java.util.TreeMap;
public class TreeMapExample1 {
public static void main(String[] args) {
TreeMap<Integer, String> score = new TreeMap<Integer, String>();
score.put(new Integer(18), "길동");
score.put(new Integer(30), "g하이");
score.put(new Integer(340), "gf하이");
score.put(new Integer(310), "g하fd이");
score.put(new Integer(3320), "g하e2e2이");
score.put(new Integer(350), "g하r이");
score.put(new Integer(20), "g하gg이");
Map.Entry<Integer,String> entry = null;
entry = score.firstEntry();
System.out.println("가장 낮은 점수 " + entry.getKey() + "-" + entry.getValue());
entry = score.lastEntry();
System.out.println("가장 높은 점수 " + entry.getKey() + "-" + entry.getValue());
entry = score.lowerEntry(new Integer(30));
System.out.println("30보다 낮은 점수 " + entry.getKey() + "-" + entry.getValue());
entry = score.higherEntry(new Integer(30));
System.out.println("30보다 높은 점수 " + entry.getKey() + "-" + entry.getValue());
entry = score.floorEntry(new Integer(30));
System.out.println("30보다 낮은 점수 " + entry.getKey() + "-" + entry.getValue());
entry = score.ceilingEntry(new Integer(30));
System.out.println("30보다 높은 점수 " + entry.getKey() + "-" + entry.getValue());
entry = score.pollFirstEntry();
System.out.println("가장 낮은 점수 " + entry.getKey() + "-" + entry.getValue());
entry = score.pollLastEntry();
System.out.println("가장 높은 점수 " + entry.getKey() + "-" + entry.getValue());
for (Map.Entry<Integer, String> e : score.entrySet()) {
System.out.println(e.getKey() + "-" + e.getValue());
}
}
}
| 리턴 타입 | 메소드 | 설명 |
| NavigableSet(K) | descendingKeySet() | 내림차순으로 정렬된 키의 NavigableSet 을 리턴 |
| NavigableMap<K,V> | descendingMap() | 내림차순으로 정렬된 Map.Entry의 NavigableMap을 리턴 |
descendingKeySet() 메소드는 내림차순으로 정렬된 키의 NavigableSet 객체를 리턴,
descendingMap() 메소드는 내림차순으로 정렬된 NavigableMap 객체를 리턴한다,
firstEntry(), lastEntry(), lowerEntry(), higherEntry(), floorEntry(), ceilingEntry() 메소드를 제공하고
오름차순과 내림차순을 번갈아가며 정렬 순서를 바꾸는 descendingMap() 메소드도 제공한다, 오름 차순으로 정렬하고 싶다면,
descendingMap() 메소드를 두번 호출하면 된다
package CollectionFrameWork;
import java.util.NavigableMap;
import java.util.TreeMap;
public class TreeMapExample2 {
public static void main(String[] args) {
TreeMap<Integer, String> tm = new TreeMap<Integer, String>();
tm.put(1, "A");
tm.put(2, "B");
tm.put(3, "C");
tm.put(4, "D");
tm.put(5, "E");
NavigableMap<Integer, String> ntm = tm.descendingMap();
System.out.println("Descending Map");
System.out.println(ntm);
NavigableMap<Integer, String> ntm1 = ntm.descendingMap();
System.out.println("Ascending Map");
System.out.println(ntm1);
}
}
다음은 TreeMap이 가지고 있는 범위 검색과 관련된 메소드 들이다.
| 리턴 타입 | 메소드 | 설명 |
| NavigableMap<K,V> | headMap( K toKey, boolean inclusive ) |
주어진 키보다 낮은 Map.Entry들을 NavigableMap으로 리턴, 주어진 키의 Map.Entry 포함 여부는 두번째 매개값에 따라 달라짐 |
| NavigableMap<K,V> | tailMap( K fromKey, boolean inclusive ) |
주어진 객체보다 높은 Map.Entry들을 NavigableMap으로 리턴, 주어진 객체 포함 여부는 두 번째 매개값에 따라 달라짐 |
| NavigableMap<K,V> | subMap( K fromKey, boolean fromInclusive, K toKey, boolean toInclusive ) |
시작과 끝으로 주어진 키 사이의 Map.Entry들을 NavigableMap 컬렉션으로 반환, 시작과 끝 키의 Map.Entry 포함 여부는 두 번째 , 네 번째 매개값에 따라 달라짐 |
세 가지 메소드 중에서 subMap() 메소드의 사용 방법을 자세히 살펴보면
시작 Map.Entry < 찾는 Map.Entry < 끝 Map.Entry
시작 Map.Entry <= 찾는 Map.Entry <= 끝 Map.Entry
NavigableMap<K,V> subMap = treeMap.subMap(K fromKey, boolean fromInclusive, K toKey, boolean toInclusive);
package CollectionFrameWork;
import java.util.NavigableMap;
import java.util.TreeMap;
public class TreeMapExample3 {
public static void main(String[] args) {
TreeMap<String, Integer> treeMap = new TreeMap<>();
treeMap.put("apple", new Integer(10));
treeMap.put("cd", new Integer(30));
treeMap.put("bar", new Integer(40));
treeMap.put("fire", new Integer(20));
treeMap.put("danger", new Integer(14));
System.out.println("c-f 사이의 단어 검색");
NavigableMap<String, Integer> reangeMap = treeMap.subMap("c", true, "f", true);
System.out.println(reangeMap);
}
}Comparable 과 Comparator
TreeSet 객체와 TreeMap 의 키는 저장과 동시에 자동 오름차순으로 정렬되는데
숫자(Integer, Double) 타입일 경우에는 값으로 정렬 하고,
문자열(String), 타입일 경우에는 유니코드로 정렬한다.
TreeSet과 TreeMap은 정렬을 위해 java.lang.Comparable 을 구현한 객체를 요구하는데
Integer, Double String 모두 Comparable 인터페이스를 구현하고 있다.
사용자 정의 클래스도 Comparable 구현한다면 자동 정렬이 가능하다.
Comparable에는 compareTo() 메소드가 정의되어 있기 때문에 사용자 정의 클래스에서는 이메소드를 오버라이딩하여 다음과같이
리턴 값을 만들어내야 한다
| 리턴 타입 | 메소드 | 설명 |
| int | compareTo(T o) | 주어진 객체와 같으면 0을 리턴 주어진 객체보다 적으면 음수를 리턴 주어진 객체보다 크면 양수를 리턴 |
나이를 기준으로 Person 객체를 오름차순으로 정렬하기 위해 Comparable 인터페이스를 구현한 것이다.
나이가 적을 경우는 -1을, 동일한 경우는 0을, 클 경우는 1을 리턴하도록 compareTo() 메소드를 재정의하였다
package CollectionFrameWork;
import java.util.Iterator;
import java.util.TreeSet;
public class ComparableExample {
public static void main(String[] args) {
TreeSet<Person> treeSet = new TreeSet<>();
treeSet.add(new Person("홍길동", 45));
treeSet.add(new Person("감자바", 25));
treeSet.add(new Person("박지원", 31));
Iterator<Person> iterator = treeSet.iterator();
while(iterator.hasNext()){
Person person = iterator.next();
System.out.println(person.name + ":" + person.age);
}
}
}package CollectionFrameWork;
public class Person implements Comparable<Person> {
public String name;
public int age;
public Person(String name, int age) {
this.name = name;
this.age = age;
}
@Override
public int compareTo(Person o) {
if (age < o.age) return -1;
else if (age == o.age) return 0;
else return 1;
}
}
TreeSet의 객체와 TreeMap의 키가 Comparable 을 구현하고 있지 않으면
저장하는 순간 ClassCastException이 발생한다.
그렇다면 Comparable 비구현 객체를 정렬하는 방법은 없을까?
=> TreeSet또는 TreeMap 생성자의 매개값으로 정렬자(Comparator)를 제공하면
Comparable 비구현 객체도 정렬시킬 수 있다.
TreeSet<E> treeSet = new TreeSet<E>(new AscendingCompator());
TreeMap<K,V> treeMap = new TreeMap<K,V>(new DescendingComparotor());4
정렬자 compare() 메소드는 비교하는 두 객체가 동등하면 0, 비교하면 값보다 앞에 오게 하려면 음수
뒤에 오게 하려면 양수를 리턴하도록 구현하면 된다
package Chapter14;
public class Fruit {
private int price;
private String name;
public Fruit(String name, int price) {
this.name = name;
this.price = price;
}
public String getName() {
return name;
}
public int getPrice() {
return price;
}
}package CollectionFrameWork;
import Chapter14.Fruit;
public class DescendingCompartor implements java.util.Comparator<Fruit> {
@Override
public int compare(Fruit o1, Fruit o2) {
if(o1.getPrice() > o2.getPrice()) return -1;
else if(o1.getPrice() < o2.getPrice()) return 1;
else return 0;
}
}package CollectionFrameWork;
import Chapter14.Fruit;
import java.util.TreeSet;
public class CompatorExample {
public static void main(String[] args) {
TreeSet<Fruit> treeSet = new TreeSet<>(new DescendingCompartor());
treeSet.add(new Fruit("Apple", 200));
treeSet.add(new Fruit("Banana", 305));
treeSet.add(new Fruit("Orange", 100));
for (Fruit fruit : treeSet) {
System.out.println(fruit.getName() + ":" + fruit.getPrice());
}
}
}
정렬자를 주지 않고 TreeSet에 저장 하면 ClassCastException 예외가 발생하지만, 정렬자를 TreeSet의 생성자에 주면 예외가 발생하지 않고 자동적으로 내림차순 정렬되는 것을 볼수 있다.
'Back-end > 이것이 자바다[신용권 한빛미디어]' 카테고리의 다른 글
| 동기화된 컬렉션 (0) | 2022.05.21 |
|---|---|
| LIFO 와 FIFO 컬렉션 (0) | 2022.05.21 |
| Map 컬렉션 (0) | 2022.05.15 |
| Set 컬렉션 (0) | 2022.05.01 |
| List 컬렉션 (0) | 2022.04.24 |