JAVA - 컬렉션 프레임웍(Collections Framework) (7)

jodbsgh·2022년 4월 2일
0

💡"JAVA"

목록 보기
34/67

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

이진 검색 트리는 정렬, 검색, 범위 검색에 높은 성능을 보이는 자료구조이며 TreeSet은 이진 검색 트리의 성능을 향상시킨 '레드-블랙 트리'로 구현되어 있다.

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

이진 트리의 노드를 코드로 표현한 코드

class TreeNode{
	TreeNode left;		//왼쪽 자식 노드.
    Object element;		//객체를 저장하기 위한 참조변수
    TreeNode right;		//오른쪽 자식 노드
}

데이터를 저장하기 위한 Object타입의 참조변수 하나와 두 개의 노드를 참조하기 위한 두 개의 참조변수를 선언했다.

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

이진검색트리에 7, 4, 9, 1, 5 순서로 값을 저장과정

왼쪽 마지막 값에서부터 오른쪽 값까지 값을 '왼쪽노드 -> 부모노드 -> 오른쪽노드'순으로 읽어오면 오름차순으로 정렬된 순서를 얻을 수 있다.

TreeSet은 정렬된 상태를 유지하기 때문에 단일 값 검색과 범위검색이 매우 빠르다.

저장된 값의 개수가 비례해서 검색시간이 증가하긴 하지만 값의 개수가 10배 증가해도 특정 값을 찾는데 필요한 비교횟수가 3~4번만 증가할 정도로 검색효율이 뛰어난 자료구조이다.

트리는 데이터를 순차적으로 저장하는 것이 아니라 저장위치를 찾아서 저장해야하고, 삭제하는 경우 트리의 일부를 재구성해야하므로 링크드 리스트보다 데이터의 추가/삭제 시간은 더 걸린다.

대신 배열이나 링크드 리스트에 비해 검색과 정렬 기능이 더 뛰어나다.

이진 검색 트리는

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

0개의 댓글