Language/JAVA

[JAVA] 검색 기능을 강화시킨 컬렉션

IT수정 2024. 10. 18. 10:52

TreeSet

TreeSet은 이진트리를 기반으로 한 Set 컬렉션이다. 이진트리는 여러 개의 노드가 트리 형태로 연결된 구조로, 루트 노드라고 불리는 하나의 노드에서 시작해 각 노드에 최대 2개의 노드를 연결할 수 있는 구조를 가지고 있다. TreeSet은 객체에 저장하면 부모 노드의 객체와 비교해서 낮은 것은 왼쪽 자식 노드에, 높은 것은 오른쪽 자식 노드에 저장한다.

TreeSet<E> treeSet = new TreeSet<E>();
TreeSet<E> treeSet = new TreeSet<>();

 

Set 타입 변수에 대입해도 되지만 TreeSet 타입으로 대입한 이유는 검색 관련 메서드가 TreeSet에만 정의되어 있기 때문이다. 다음은 TreeSet이 가지고 있는 검색 관련 메서드들이다.

리턴 타입  메서드 설명
E first() 제일 낮은 객체를 리턴
E last() 제일 높은 객체를 리턴
E lower(E e) 주어진 객체보다 바로 아래 객체를 리턴
E higher(E e) 주어진 객체보다 바로 위 객체를 리턴
E floor(E e) 주어진 객체와 동등한 객체가 있으면 리턴, 만약 없다면 주어진 객체의 바로 아래의 객체를 리턴
E celling(E e) 주어진 객체와 동등한 객체가 있으면 리턴, 만약 없다면 주어진 객체의 바로 위의 객체를 리턴
E pollFirst() 제일 낮은 객체를 꺼내오고 컬렉션에서 제거함
E pollLast() 제일 높은 객체를 꺼내오고 컬렉션에서 제거함
Iterator<E> descendingIterator() 내림차순으로 정렬된 Iterator를 리턴
NavigableSet<E> descendingSet() 내림차순으로 정렬된 NavigableSet을 리턴
NavigableSet<E> headSet(
E toElement,
boolean inclusive
)		 주어진 객체보다 낮은 객체들을 NavigableSet으로 리턴
주어진 객체 포함 여부는 두 번째 매개값에 따라 달라짐
NavigableSet<E> taildSet(
E fromElement,
boolean inclusive
) 		주어진 객체보다 높은 객체들을 NavigableSet으로 리턴
주어진 객체 포함 여부는 두 번째 매개값에 따라 달라짐
NavigableSet<E> subSet(
E fromElement,
boolean fromInclusive,
E toElement,
boolean toInclusive
)		 시작과 끝으로 주어진 객체 사이의 객체들을 NavigableSet으로 리턴
시작과 끝 객체의 포함 여부는 두 번째, 네 번째 매개값에 따라 달라짐

 

예제 코드

package ch15;

import java.util.NavigableSet;
import java.util.TreeSet;

public class TreeSetExample {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		TreeSet<Integer> scores = new TreeSet<>();
		
		scores.add(87);
		scores.add(98);
		scores.add(75);
		scores.add(95);
		scores.add(80);
		
		for(Integer s : scores) {
			System.out.print(s + " ");
		}
		System.out.println("\n");
		
		System.out.println("가장 낮은 점수: " + scores.first());
		System.out.println("가장 높은 점수: " + scores.last());
		System.out.println("95점 아래 점수: " + scores.lower(95));
		System.out.println("95점 위의 점수: " + scores.higher(95));
		System.out.println("95점이거나 바로 아래 점수: " + scores.floor(95));
		System.out.println("85점이거나 바로 위의 점수: " + scores.ceiling(85) + "\n");
		
		NavigableSet<Integer> descendingScores = scores.descendingSet();
		for(Integer s : descendingScores) {
			System.out.print(s + " ");
		}
		System.out.println("\n");
		
		NavigableSet<Integer> rangeSet = scores.tailSet(80, true);
		for(Integer s : rangeSet) {
			System.out.print(s + " ");
		}
		System.out.println("\n");
		
		rangeSet = scores.subSet(80, true, 90, false);
		for(Integer s : rangeSet) {
			System.out.print(s + " ");
		}
		
	}

}

 

출력 결과

75 80 87 95 98 

가장 낮은 점수: 75
가장 높은 점수: 98
95점 아래 점수: 87
95점 위의 점수: 98
95점이거나 바로 아래 점수: 95
85점이거나 바로 위의 점수: 87

98 95 87 80 75 

80 87 95 98 

80 87

 

TreeMap

TreeMap은 이진 트리를 기반으로 한 Map 컬렉션이다. TreeSet과 차이점은 키와 값이 저장된 Entry를 저장한다는 점이다. TreeMap에 엔트리를 저장하면 키를 기준으로 자동 정렬되는데, 부모키 값과 비교해서 낮은 것은 왼쪽, 높은 것은 오른쪽 자식 노드에 Entry 객체를 저장한다.

TreeMap<K, V> treeMap = new TreeMap<K, V>();
TreeMap<K, V> treeMap = new TreeMap<>();

 

Map 타입 변수에 대입해도 되지만 TreeMap 타입으로 대입하는 이유는 검색 관련 메서드가 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> ceilingEntry(K key) 주어진 키와 동등한 키가 있으면 해당 Map.Entry를 리턴, 없다면 주어진 키 바로 위의 Map.Entry를 리턴
Map.Entry<K, V> pollFirstEntry() 제일 낮은 Map.Entry를 꺼내오고 컬렉션에서 제거함
Map.Entry<K, V> pollLastEntry() 제일 높은 Map.Entry를 꺼내오고 컬렉션에서 제거함
NavigableSet<K, V> descendingKeySet() 내림차 순으로 정렬된 키의 NavigableSet을 리턴
NavigableMap<K, V> descendingMap() 내림차순으로 정렬된 Map.Entry의 NavigableMap을 리턴
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 포함 여부는 두 번째, 네 번째 매개값에 따라 달라짐

 

예제 코드

package ch15;

import java.util.Map.Entry;
import java.util.*;

public class TreeMapExample {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		TreeMap<String, Integer> treeMap = new TreeMap<>();
		
		treeMap.put("apple", 10);
		treeMap.put("forever", 60);
		treeMap.put("description", 40);
		treeMap.put("ever", 50);
		treeMap.put("zoo", 80);
		treeMap.put("base", 20);
		treeMap.put("guess", 70);
		treeMap.put("cherry", 30);
		
		Set<Entry<String, Integer>> entrySet = treeMap.entrySet();
		for(Entry<String, Integer> entry : entrySet) {
			System.out.println(entry.getKey() + "-" + entry.getValue());
		}
		System.out.println();
		
		Entry<String, Integer> entry = null;
		entry = treeMap.firstEntry();
		System.out.println("제일 앞 단어: " + entry.getKey() + "-" + entry.getValue());
		entry = treeMap.lastEntry();
		System.out.println("제일 뒤 단어: " + entry.getKey() + "-" + entry.getValue());
		entry = treeMap.lowerEntry("ever");
		System.out.println("ever 앞 단어: " + entry.getKey() + "-" + entry.getValue() + "\n");
		
		NavigableMap<String, Integer> descendingMap = treeMap.descendingMap();
		Set<Entry<String, Integer>> descendingEntrySet = descendingMap.entrySet();
		for(Entry<String, Integer> e : descendingEntrySet) {
			System.out.println(e.getKey() + "-" + e.getValue());
		}
		System.out.println();
		
		System.out.println("[c~h 사이의 단어 검색]");
		NavigableMap<String, Integer> rangeMap = treeMap.subMap("c", true, "h", false);
		for(Entry<String, Integer> e : rangeMap.entrySet()) {
			System.out.println(e.getKey() + "-" + e.getValue());
		}
	}

}

 

출력 결과

apple-10
base-20
cherry-30
description-40
ever-50
forever-60
guess-70
zoo-80

제일 앞 단어: apple-10
제일 뒤 단어: zoo-80
ever 앞 단어: description-40

zoo-80
guess-70
forever-60
ever-50
description-40
cherry-30
base-20
apple-10

[c~h 사이의 단어 검색]
cherry-30
description-40
ever-50
forever-60
guess-70

 

Comparable과 Comparator

TreeSet에 저장되는 객체와  TreeMap에 저장되는 키 객체는 저장과 동시에 오름차순으로 정렬되는데, 어떤 객체든 정렬될 수 있는 것은 아니고 객체게 Comparable 인터페이스를 구현하고 있어야 가능하다. Integer, Double, String 타입은 모두 Comparable 인터페이스를 구현하고 있기 때문에 상관없지만, 사용자 정의 객체를 저장할 때에는 반드시 Comparable을 구현하고 있어야 한다. Comparable 인터페이스에는 compareTo() 메서드가 정의되어 있다. 따라서 사용자 정의 클래스에서 이 메서드를 재정의해서 비교 결과를 정수 값으로 리턴해야 한다.

리턴 타입 메서드 설명
int compareTo(T o) 주어진 객체와 같으면 0을 리턴
주어진 객체보다 적으면 음수를 리턴
주어진 객체보다 크면 양수를 리턴

 

예제 코드

package ch15;

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;
	}
}
package ch15;

import java.util.TreeSet;

public class ComparableExample {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		TreeSet<Person> treeSet = new TreeSet<Person>();
		
		treeSet.add(new Person("홍길동", 45));
		treeSet.add(new Person("김자바", 25));
		treeSet.add(new Person("박지원", 31));
		
		for(Person person : treeSet) {
			System.out.println(person.name + ":" + person.age);
		}
	}

}

 

출력 결과

김자바:25
박지원:31
홍길동:45

 

비교 기능이 있는 Comparable 구현 객체를 TreeSet에 저장하거나 TreeMap의 키로 저장하는 것이 원칙이지만, 비교 기능이 없는 Comparable 비구현 객체를 저장하고 싶다면 방법은 없진 않다. TreeSet과 TreeMap을 생성할 때 비교자를 다음과 같이 제공하면 된다.

TreeSet<E> treeSet = new TreeSet<E>(new ComparatorImpl());
TreeMap<K, V> treeSet = new TreeMap<K, V>(new ComparatorImpl());

 

비교자는 Comparator 인터페이스를 구현한 객체를 말하는데, Comparator 인터페이스에는 compare() 메서드가 정의되어 있다. 비교자는 이 메서드를 재정의해서 비교 결과를 정수 값으로 리턴하면 된다.

리턴 타입 메서드 설명
int compare(T o1, T o2) o1과 o2가 동등하다면 0을 리턴
o1이 o2보다 앞에 오게 하려면 음수를 리턴
o1이 o2보다 뒤에 오게 하려면 양수를 리턴

 

예제 코드

package ch15;

public class Fruit {
	public String name;
	public int price;
	
	public Fruit(String name, int price) {
		this.name = name;
		this.price = price;
	}
}
package ch15;

import java.util.Comparator;

public class FruitComparator 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;
	}
}
package ch15;

import java.util.TreeSet;

public class ComparatorExample {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		TreeSet<Fruit> treeSet = new TreeSet<Fruit>(new FruitComparator());
		
		treeSet.add(new Fruit("포도", 3000));
		treeSet.add(new Fruit("수박", 10000));
		treeSet.add(new Fruit("딸기", 6000));
		
		for(Fruit fruit : treeSet) {
			System.out.println(fruit.name + ":" + fruit.price);
		}
	}	

}

 

출력 결과

포도:3000
딸기:6000
수박:10000

'Language > JAVA' 카테고리의 다른 글

[JAVA] 동기화된 컬렉션  (0) 2024.10.18
[JAVA] LIFO와 FIFO 컬렉션  (1) 2024.10.18
[JAVA] Map 컬렉션  (0) 2024.10.18
[JAVA] Set 컬렉션  (0) 2024.10.18
[JAVA] List 컬렉션  (0) 2024.10.17

'Language/JAVA'의 다른글

  • 현재글[JAVA] 검색 기능을 강화시킨 컬렉션

관련글

티스토리툴바