[C++] 트리

 

 

 

 

트리

그래프의 일종으로 계층형 자료구조 (Hierarchical Data Structure)

방향이 있고 사이클이 없는 그래프이다

 

트리는 노드(Node : 그래프에서의 정점)과 간선으로 구성된다.

set / map / multiset / multimap 으로 구현되어 있다.

트리의 자식은 트리로 구성되어 재귀적인 구조로 되어 있다.

 

용어

Root	트리의 시작 노드를 뿌리(Root)라 한다.
Leaf Node	자식이 없는 노드 (가장 아래 있는 노드), 단말 노드
Parent Node	부모 노드
Child Node	자식 노드
Sibling Node	같은 부모 노드를 갖는 형제 노드
Level	Root에서부터 트리의 깊이
높이	Root에서 가장 깊은 노드까지의 깊이
조상 (Ancestor) 노드	간선을 따라 Root까지 경로의 모든 노드
자손 (Descendant) 노드	조상 노드의 반대
서브트리 (Sub-Tree)	트리의 자식은 트리
차수 (Degree)	노드가 가지는 서브 트리의 수. 노드 차수 중 최대값을 트리의 차수라 한다.
내부 (Internal) 노드	단말 노드를 제외한 모든 노드
포레스트 (Forest)	트리의 집합

 

순회

전위 순회 ( A - B - D - H - I - E - J - C - F - G )

- 자기 자신을 첫 번째로 방문한다. 

- 깊이 우선 탐색 (DFS) 과 같은 구조로 작용

 

중위 순회 ( H - D - I - B - J - E - A - F - C - G )

- 자기 자신을 중간에 방문한다. (왼쪽 - 나 - 오른쪽)

- 왼쪽이 없으면 ( 나 - 오른쪽 )

 

후위 순회 ( H - I - D - J - E - B - F - G - C - A )

- 자기 자신을 마지막에 방문한다

- 자식 노드를 다 방문하고 자신을 방문

 

레벨 순회 ( A - B - C - D - E - F - G - H - I - J )

- 레벨에 있는 노드부터 순서대로 방문

 

 

이진 검색 트리

이진트리 : 트리의 차수(Sub-tree)가 2 이하인 트리

 

이진트리를 중위순회하면 정렬된 데이터를 얻을 수 있다.

 

연산

트리가 균형잡혀 있다면 이진 검색과 동일하게 O(log n)의 시간이 걸리지만,

트리가 편향되어 있다면 O(n)의 시간이 소요된다.

* 편향되지 않도록 주의해야 한다.

 

자가 균형 이진 탐색 트리

1) AVL 트리

문제되는 상황을 4가지로 나누고 회전을 통해 트리를 개선한다.

LL문제 (왼쪽으로 편향된 상태) , RR문제 (오른쪽으로 편향된 상태), LR문제 ( < ) , RL 문제 ( > )

 

참고 자료 : https://code-lab1.tistory.com/61?category=1213002 

[자료구조] AVL트리란?| AVL트리 쉽게 이해하기 | AVL트리 시뮬레이터

 

2) 레드블랙 트리

AVL을 업그레이드한 트리구조. STL에 구현된 트리는 레드블랙 트리다

 

참고 자료 : https://code-lab1.tistory.com/62

[자료구조] 레드-블랙 트리(Red-Black Tree)란? | 레드-블랙 트리 쉽게 이해하기

 

 

한 노드를 기준으로 왼쪽 서브 트리는 모두 그 노드보다 작은 값을 가지고 있으며,

오른쪽 서브 트리는 모드 그 노드보다 큰 값을 가지고 있는 구조

STL에 구현된 트리는 모두 이진 검색 트리

 

데이터 삽입 순서가 중요

 

균형이 맞아야 효율적이다

{ 1, 2, 3, 4, 5 } : 편향적인 구조로 들어가서 비효율적

그래서 균형을 맞춰주는 AVL 트리, 레드블랙 트리라는걸 만들었음

 

STL

STL에서는 std::set / std::map / std::multiset / std::multimap (multi는 중복을 허용한다.)

 

C#에서는 SortedDictionary