개요

• 트리는 그래프의 일종으로 계층형 자료구조다.
• 트리는 데이터가 저장된 노드와 노드 간 관계를 표현하는 간선으로 구성된다.
  

용어

• 트리에는 여러 가지 용어가 있다. 아래의 그림을 참고하자.
  

• Root : 트리의 시작 노드이다.

• Parent Node : 부모 노드이다.

• Child Node : 자식 노드이다.

• Siblings : 형제 노드이다.

• Sub-tree : 하나의 트리를 구성하는 왼쪽과 오른쪽의 작은 트리이다.

1. 서브 트리 역시 서브 트리로 이루어짐
2. 그 서브 트리 또한 다른 서브 트리로 이루어짐
3. 즉, 트리는 재귀적

• Leaf Node : 제일 마지막 끝 노드이다.
• 이 외의 용어는 아래와 같다.

1. 조상 노드 : 한 노드에서 간선을 따라 루트 노드까지 이르는 경로에 있는 모든 노드
2. 자손 노드 : 조상 노드의 반대
3. 차수 : 한 노드가 가지는 서브 트리의 수. 노드의 차수 중 최댓값을 트리의 차수라 함
4. 내부 노드 : 단말 노드를 제외한 나머지 노드
5. 포레스트 : 트리의 집합

순회

• 트리에 대한 순회는 전위 순회 / 중위 순회 / 후위 순회 / 레벨 순회가 있다.
• 위의 이미지를 토대로 순회 순서를 나타내면 아래와 같다.

1. 전위 순회 : A - B - D - H - I - E - J - C - F - G
2. 중위 순회 : H - D - I - B - J - E - A - F - C - G
3. 후위 순회 : H - I - D - J - E - B - F - G - C - A
4. 레벨 순회 : A - B - C - D - E - F - G - H - I - J

이진 검색 트리

• 이진 검색 트리는 한 노드를 기준으로 왼쪽 서브 트리는 모두 그 노드보다 작은 값을 가지고 있으며, 오른쪽 서브 트리는 모두 그 노드보다 큰 값을 가지고 있는 이진 트리이다.

1. 이진 트리 : 트리의 차수가 2 이하인 트리

• 수식으로 표현하자면 왼쪽 자식 노드의 값 <= 부모 노드의 값 <= 오른쪽 자식 노드의 값이 된다.
• 이진 검색 트리를 중위 순회하면 정렬된 데이터를 얻을 수 있다.
  

트리의 균형

• 이진 탐색 트리는 데이터의 삽입 순서에 따라 형태가 달라지는데, 이에 따라 트리의 균형도가 결정된다.
• 트리의 균형도는 왼쪽 서브 트리의 높이와 오른쪽 서브 트리의 높이의 차이를 말하는데, 균형도의 절댓값이 2이상이면 트리가 편향되었다고 표현한다.
• 트리의 균형도는 트리의 연산에 영향을 미친다.

1. 트리가 균형잡혀 있다면 모든 연산이 O(logN)
2. 편향되어 있다면 O(N)에 가까워짐
   

• 트리의 균형을 유지하는 방법으로, 자가 균형 이진 검색 트리가 생겨나게 되었다.
  

사용법

• C#에서는 SortedSet과 SortedDictionary로 구현되어 있다.

1. 둘 다 레드 블랙 트리
2. SortedDictionary는 SortedSet과는 다르게 데이터를 저장할 때 키와 값의 쌍으로 저장. 비교의 경우 키에 대해서 연산
   

• SortedSet
  
• SortedDictionary