[CS] 자료구조 - 트리 (Tree)

트리는 비선형 자료구조 중 하나로 노드로 이루어져있으며 데이터들이 계층적으로 연결되어 저장된다.

또한 트리 내에 다른 하위 트리가 있고 그 하위 트리 안에는 또 다른 하위 트리가 있는 재귀적 자료구조 이기도 하다.

 

트리 구조에서 사용되는 기본 용어

 

노드 (Node)

• 트리를 구성하고 있는 기본 요소
• 루트 노드 : 트리에서 부모가 없는 최상위 노드, 트리의 시작점
• 부모 노드 : 루트 노드 방향으로 직접 연결된 노드
• 자식 노드 : 루트 노드 반대 방향으로 직접 연결된 노드
• 형제 노드 : 같은 부모 노드를 갖는 노드들
• 리프 노드 : 루트 노드를 제외하고 차수가 1인 정점. 자식이 없는 노드

간선 (Edge)

• 노드와 노드 간의 연결선

레벨 (level)

• 루트에서 기준 노드까지 연결된 간선 수의 합

깊이 (depth)

• 루트에서 기준 노드까지의 간선 수

높이 (height)

• 기준 노드에서 리프 노드까지 가장 긴 경로의 간선 수

차수 (degree)

• 각 노드의 자식 노드의 개수

트리의 차수 (degree of tree)

• 트리의 최대 차수

너비 (width)

• 가장 많은 노드를 갖고 있는 레벨의 크기

---

이진트리 - Binary Tree

이진트리는 각 노드가 최대 두 개의 자식 노드를 갖는 트리를 말한다. 각 노드는 자식 노드가 없거나, 한 개 또는 두 개 만을 갖는다.

 

이진트리에는 다음과 같은 종류가 있다.

 

 

포화 이진 트리 (Full binary tree)

• 모든 레벨의 노드가 자식 노드를 가지고 있는 이진 트리
• 모든 리프 노드의 높이가 같다.
• 트리의 노드 개수가 2^h-1개 여야 한다. (h = 트리의 높이)

완전 이진 트리 (Complete binary tree)

• 마지막 레벨을 제외하고 모든 레벨이 완전히 채워져 있다.
• 노드가 왼쪽에서 오른쪽으로 순차적으로 채워져야 한다.

편향 이진 트리 (Skewed binary tree)

• 부모 노드의 왼쪽이나 오른쪽 한 곳만 노드가 존재하는 트리
• 같은 높이의 이진 트리 중에서 최소 개수의 노드 개수를 가진다.