[자바의 정석] 11. 컬렉션 프레임웍 - HashSet / TreeSet

1.8 HashSet

Set인터페이스를 구현한 가장 대표적인 컬렉션. 중복된 요소를 저장하지 않는다.

HashSet의 특징을 이용하면 컬렉션 내의 중복 요소들을 쉽게 제거 가능

저장순서를 유지하지 않음. → 저장순서 유지하는 LinkedHashSet 사용

 

 

Set을 구현한 컬렉션 클래스는 List를 구현한 컬렉션 클래스와 달리 순서를 유지하지 않기 때문에 저장된 순서와 다를 수있다.

중복제거와 동시에 저장순서를 유지하고싶다면 LinkedHashSet을 사용

import java.util.*;

class HashSet{
	public static void main(String[] args){
    	Object[] objArr = {"1", new Integer(1), "2", "2", "3", "3", "4", "4", "4"}
        Set set = new HashSet();
        
        for(int i=0; i<objArr.length; i++){
        	set.add(objArr[i]);
        }
        
        System.out.println(set); //[1, 1, 2, 3, 4]
    }
}

*1 ,1 => String인스턴스와 Integer인스턴스로 서로 다른 객체이므로 중복으로 간주하지 않음

 

 

1.9 TreeSet

TreeSet은 이진 검색 트리(binary search tree)라는 자료구조의 형태로 데이터를 저장하는 컬렉션 클래스이다.

이진 검색 트리는 정렬, 검색, 범위검색(range search)에 높은 성능을 보이는 자료구조이며, TreaaSet은 이진 검색 트리의 성능을 향상시킨 ’레드-블랙 트리(Red-Black tree)’로 구현되어 있다.

 

Set인터페이스를 구현했으므로 중복된 데이터의 저장을 허용하지 않으며 정렬된 위치에 저장하므로 저장순서를 유지하지도 않는다.

 

이진트리(binary tree)는 링크드리스트처럼 여러 개의 노드(node)가 서로 연결된 구조로, 각 노드에 최대 2개의 노드를 연결할 수 있으며, ‘루트(root)’라고 불리는 하나의 노드에서부터 시작해서 계속 확장해 나갈 수 있다.

 

부모-자식관계는 상대적인 것이며 하나의 부모 노드는 최대 두 개의 자식 노드와 연결될 수 있다.

 

이진트리의 노드를 코드로 표현하면
class TreeNode {
	TreeNode left; //왼쪽 자식노드
	Object   element; //데이터(객체)를 저장하기 위한 Object타입의 참조변수 하나 선언
	TreeNode right; //오른쪽 자식노드
	//두 개의 노드를 참조하기 위한 두 개의 참조변수 선언
}

 

이진 검색 트리는 부모노드의 왼쪽에는 부모노드의 값보다 작은 값의 자식노드를 오른쪽에는 큰 값의 자식노드를 저장하는 이진 트리이다.

*TreeSet은 정렬된 상태를 유지함. 범위 값을 검색할 때 빠름

 

트리는 데이터를 순차적으로 저장하는 것이 아니라 저장위치를 찾아서 저장해야하고, 삭제하는 경우 트리의 일부를 재구성해야하므로 링크드 리스트보다 데이터의 추가/삭제 시간은 더 걸린다. 대신 배열이나 링크드 리스트에 비해 검색과 정렬기능이 더 뛰어나다.

 

이진 검색 트리(binary serach tree)는

• -모든 노드는 최대 두 개의 자식노드를 가질 수 있다.
• -왼쪽 자식노드의 값은 부모노드의 값보다 작고 오른쪽 자식노드의 값은 부모노드의 값보다 커야한다.
• -노드의 추가 삭제에 시간이 걸린다.(순차적으로 저장하지 않으므로)
• -검색(범위검색)과 정렬에 유리하다.
• -중복된 값을 저장하지 못한다.

 

✏️-이진 트리의 모든 노드를 한번씩 읽는 것을 트리 순회 라고 한다.

-전위, 중위, 후위 순회법이 있으며, 중위 순외하면 오름차순으로 정렬된다.

 

 

 

출처 : 남궁성. 「자바의 정석」. 도우출판. 2016