TreeSet (1)

TreeSet - 범위 탐색, 정렬

• 이진 탐색 트리 (binary search tree)로 구현, 범위 탐색과 정렬에 유리.
• 이진 트리는 모든 노드가 최대 2개의 하위노드를 갖음
• 각 요소(node)가 나무(tree)형태로 연결(LinkedList의 변형)

TreeSet은 이진 탐색 트리(binary search tree)로 구현 되어있고, 범위 탐색(from~to)과 정렬에 유리하다.

이진트리(birary tree)는 하나의 노드가 최대 2개의 하위노드를 갖을 수 있다

노드하나를 TreeNode라고 부른다.

그래서 TreeNode 클래스에는
저장할 객체를 가지고 있고,
자신의 왼쪽과 오른쪽 자식을 각각 가리킬 수 있게 되어있다.

TreeNode는 LinkedLIst와 비슷하다. LinkedList의 변형이라고도 할 수 있다.
다만, 링크드리스트는 해당 노드의 다음 요소만 가리킬 수 있는데,
트리노드는, 왼쪽 자식노드와 오른쪽 자식노드를 가리킬 수 있게 되어있다.

 

---

 

이진 탐색 트리(binary search tree)

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

이진 트리는 어떤 한 노드에 최대 2개의 자식노드를 가질 수 있는 트리를 말하는데,
그중에서, 부모보다 작은 값은 왼쪽에 저장하고, 부모보다 큰 값은 오른쪽에 저장한 트리를 이진 탐색 트리라고 한다.

 

그림을 좀더 자세히 그려보면, 아래와 같다.

좀 전에 배운 것처럼 이진 탐색 트리는 이진 트리의 노드와 구성이 같다.
노드는 저장할 객체가 있고,
왼쪽과 오른쪽을 가리키기 위한 참조변수가 있는 것은 동일하다.
다만, 이진 탐색 트리의 경우, 부모보다 작은 값은 왼쪽자식에 저장하고, 부모보다 큰 값은 오른쪽 자식에 저장한다.

 

 

• 데이터가 많아질 수록 추가, 삭제에 시간이 더 걸림 (비교 횟수 증가)

 

이진 탐색 트리의 단점으로는, 데이터가 많아질 수록 비교 횟수가 증가되어 추가, 삭제에 시간이 더 걸린다는 것이 있다.

데이터가 많아질 수록 트리가 커지는데,
요소를 하나 저장할 때마다, 부모보다 큰지 작은지 계속 비교해야 한다.

만약에  5를 저장하려고 하면 root부터 계속 비교해야 한다.
root와 비교후 계속 노드를 타고타고 비교를 해야한다.
위 그림에서는 2번 비교했지만,
트리가 커지면 커질수록 비교횟수가 증가한다. 그러면 추가/삭제에 시간이 더 걸린다.

 

---

 

TreeSet - 데이터 저장 과정 bollean add(Object o)

 

TreeSet에 데이터를 저장할 때는, add(Object o) 메서드를 사용한다. 매개변수로는 저장할 객체를 주면 된다.

HashSet에서는 add(Object o)메서드를 호출하면,
1. equals()
2. hashCode()
이런 메서드를 호출했다.
왜냐하면, Set은 중복을 허용하지 않기 때문에, 같은게 있는지 확인해야 한다.  같은게 있으면 저장이 실패한다.

그런데, TreeSet은 compare()를 호출해서 비교한다.

 

만약에, TreeSet에 7, 4, 9, 1, 5의 순서로 데이터를 저장하면, 아래의 과정을 거친다.
(루트부터 트리를 따라 내려가며 값을 비교, 작으면 왼쪽, 크면 오른쪽에 저장)

처음에 7은 그냥 저장된다.(비교횟수:0)
4는 루트부터 비교를 해서 4가 루트인 7보다 작으므로 왼쪽에 저장한다.(비교횟수:1)
9는 루트인 7과 비교했을 때  7보다 크므로 오른쪽에 저장한다.(비교횟수:1번)
그다음에 1을 루트부터 비교를 하는데, 7보다 작으므로 왼쪽으로 갔는데, 이미 4가 저장되있으므로  4와 또 비교를 했을 때, 4보다 작으므로 4의 왼쪽 자식노드에 저장한다.(비교횟수:2번)
그리고 5는 7보다 작으므로 왼쪽으로 갔는데, 4가있으므로 4와 비교하는데, 4보다 5가 크므로 오른쪽으로 가서 4의 오른쪽 자식노드에 비교한다.(비교횟수:2번)

요소를 저장해감에 따라  비교횟수가 늘어나서 저장하는데 시간이 많이 걸린다.