[Java] 컬렉션 프레임윅 (TreeSet)

• TreeSet

• 이진 트리

TreeSet

: 이진 검색 트리라는 자료구조의 형태로 데이터를 저장하는 컬렉션의 클래스이다.

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

 

 

이진 트리

: 링크드리스트(LinkedList) 처럼 여러 개의 노드가 서로 연결된 구조로, 각 노드에 최대 2개의 노드를 연결할 수 있으며

  루트(root) 라고 불리는 하나의 노드에서부터 시작해서 계속 확장 가능

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

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

 

* 이진 검색 트리는

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