Tree - Normal

나무를 형상화한 자료구조로

 

뿌리부터 가지, 나뭇잎으로 세분화되는 구조에서 착안된 구조.

 

그래프 구조의 특별한 타입이기도 하다.

 

루트 : 트리의 최상위 노드. 
리프 : 트리의 최하위 노드.
엣지 : 부모자식노드사이를 연결하는 선.

노드 : 트리의 구성요소. 자식과 연결될 포인터와 데이터를 저장할 공간을 가짐.

 

차수 : 같은 부모에 최다 연결된 노드의 수.

깊이 : 루트에서 해당 노드까지의 직선 엣지수

형제 노드 : 부모가 같은 노드들.

조상 노드 : 부모부터 루트까지의 모든 노드

자손 노드 : 자식에서 리프 노드까지의 모든 노드.

레벨 : 루트를 기준으로 1부터 깊이에 따른 노드집합.

 

트리의 특수한 타입으로 이진트리, 이진 탐색트리, AVL 트리, Red-Black 트리, B 트리, B+ 트리, 최소 신장 트리 등등이 있다. 

 

하나씩 차근차근 살펴보자

 

트리의 속성

 

1. 노드 사이의 cycle이 존재하지 않음.

2. 노드 사이의 연결은 단 하나만 존재.

3. 엣지 하나를 끊으면 트리가 둘로 나뉨.

4. 엣지 수는 노드 수 - 1.

5. 임의 노드에서 다른 노드로의 경로는 유일. 

 

트리의 순회

1. 전위순회 (preorder) : 노드 - 왼 - 오 순서로 순회. 깊이 우선 순회 (depth first traversal)

 

2. 중위 순회 (inorder) : 왼 - 노드 - 오 순서로 순회. 대칭 순회 (symmetric traversal)

 

3. 후위 순회 (postorder) : 왼 - 오 - 노드 순서로 순회.

 

4. 레벨 순서 순회 (level order) : 트리의 레벨순서대로 순회. 너비 우선 순회(breadth first traversal)