[자바의 정석 2권] TreeSet

1) TreeSet이란?

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

  이진 검색 트리는 정렬, 검색, 범위 검색(range search)에 높은 성능을 보이는 자료구조이며,

  TreeSet은 이진 검색 트리의 성능을 향상시킨 '레드-블랙 트리(Red-black tree)'로 구현되어 있다.

 

- 그리고 Set 인터페이스를 구현했으므로, 중복된 데이터의 저장을 허용하지 않으며 

  정렬된 위치에 저장하므로 저장순서를 유지하지도 않는다. 

 

- 이진 트리(binary tree)는 링크드 리스트처럼 여러 개의 노드(node)가 서로 연결된 구조로,

  각 노드에 최대 2개의 노드를 연결할 수 있으며,

  루트(root)라고 불리는 하나의 노드에서부터 시작해서 계속 확장해나갈 수 있다. 

 

- 위 아래로 연결된 두 노드를 '부모-자식관계'에 있다고 하며

  위의 노드를 부모 노드, 아래의 노드를 자식 노드라 한다.

  부모-자식 관계는 상대적인 것이며, 

  하나의 부모 노드는 최대 두 개의 자식 노드와 연결될 수 있다. 

 

- 이진 검색 트리(binary search tree)는 부모노드의 왼쪽에는 부모노드의 값보다 작은 값의 자식 노드를

  오른쪽에는 큰 값의 자식노드를 저장하는 이진 트리이다. 

 

- 트리는 데이터를 순차적으로 저장하는 것이 아니라 저장위치를 찾아서 저장해야 하고,

  삭제하는 경우 트리의 일부를 재구성해야하므로

  링크드 리스트보다 데이터의 추가/삭제 시간은 더 걸린다. 

  

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