TreeSet (1)

11 - 39 TreeSet >> 범위 탐색 / 정렬

 

-

이진 탐색 트리 (binary search tree) 로 구현.

범위 탐색 ( from ~ to ) & 정렬에 유리 하다.

 

-

이진 트리는 모든 노드가 최대 2개의 하위 노드를 갖는다.

각 요소 (node) 가 나무 (tree) 형태로 연결 되어 있다 (LinkedList 의 변형)

 

 

 

 

이진 트리 (binary tree)

 

최대 2개라는 의미는 0개 부터 2개 까지의 하위 노드를 가질 수 있다는 것을 의미 한다.

 

이진 트리에서 첫번 째 요소를 루트 == root 라고 한다.

 

위의 이미지를 보면, 루트의 자식으로는 2개가 있다.

 

또 A의 자식으로 하위 자식이 2개가 있다.

 

B와 C의 부모는 A가 된다.

 

각각의 요소 하나 하나를 "노드" 라고 한다.

 

>>

각 "노드" 가 부모와 자식 관계로 이루어져 있는 것을 "이진 트리 == binary tree" 라고 한다.

 

class TreeNode {

    TreeNode left;	//	왼쪽 자식 노드
    Object element;	//	저장할 객체
    TreeNode right;	//	오른쪽 자식 노드
    
}

 

노드는 왼쪽 오른쪽 노드를 모두 가리 킬 수 있다.

 

참고로 LinkedList 의 노드는 한개의 요소만 가리 킬 수 있었다.

 

하지만, 트리 노드는 두개의 요소를 가리 킬 수 있다.

 

 

 

11 - 40 이진 탐색 트리 (binary search tree)

 

- 부모 보다 작은 값은 왼쪽, 큰 값은 오른쪽에 저장 한다.

 

 

최대 2개의 요소를 갖기 때문에 이진 트리 이다.

 

위를 보면 부모 노드의 값이 5 이고, 작은 값 자식인 1 은 왼쪽, 큰 값 자식인 7 은 오른쪽에 있다.

 

이진 트리는 종류가 굉장히 다양 하고, 그 중 하나가 "이진 탐색 트리" 이다.

 

원래 이진 트리는 그냥 "부모 노드의 자식으로 최대 2개의 관계를 유지" 라는 조건만 있으면 되는데,

 

이진 탐색 트리는 조건이 하나 더 붙어서 "부모 노드 보다 작은 값이 왼쪽에, 부모 노드 보다 큰 값이 오른쪽에" 이다.

 

이진 트리의 단점이 존재 한다.

 

- 데이터가 많아질 수록 추가 / 삭제에 시간이 훨씬 증가 하게 된다 (비교 횟수 증가)

 

요소를 추가 (저장) / 삭제 할 때마다 루트 부터 계속 ~~~ 숫자를 비교 하면서 가야 한다.

 

 

부모 노드 보다 숫자가 작은지 ~ 큰지 ~ 를 계속 비교 해야 한다.

 

 

 

11 - 41 TreeSet - 데이터 저장 과정 ( boolean add(Object o) )

 

HashSet 은 equals() 와 hashCode() 메서드를 호출 해서 비교 한다. 

 

반면에

 

TreeSet 은 compare() 메서드를 호출 해서 비교 한다.

 

만약, TreeSet에 7, 4, 9, 1, 5 의 순서로 데이터를 저장 하면, 아래의 과정을 거치게 된다.

>>

루트 부터 트리를 따라 내려가며 값을 비교 한다. 작으면 왼쪽에 저장, 크면 오른쪽에 저장 한다.

 

 

 

위와 같이, TreeSet은 이진 트리의 한 종류인 이진 탐색 트리로 구성 되어 있기 때문에,

 

처음에는 비교 하지 않아서 연산 속도가 빠르지만, 가면 갈수록 비교 횟수가 증가 하게 되서,

 

데이터가 많아질 수록 추가 / 삭제에 시간이 훨씬 증가 하게 된다.