[자료구조] 트리 구조와 이진 트리

목차

• 트리 구조
• 트리 관련 주요 용어
• 트리 구조의 특징
• 이진 트리
• 형태에 따른 이진 트리의 종류

 

트리

 

트리는 여러 개의 노드(node)로 이루어진 자료 구조이며, 각 노드는 부모와 자식 간의 관계를 가진다.

트리 구조는 비선형 자료 구조로, 여러 개의 데이터를 계층적으로 표현할 수 있는 형태이다.

트리는 루트 노드를 기준으로 하위 노드가 가지(branch)를 뻗어나가는 구조로 형성되며, 각 노드가 하나의 부모와 연결된다.

트리에서는 순환(cycle)이 발생하지 않으며, 노드는 하나의 부모 노드만을 가질 수 있다.

---

트리 관련 주요 용어

 

간선

• 노드와 노드를 연결하는 선
• 링크나, 브렌치라고 불리기도 한다.

루트 노드

• 최상단에 있는 노드
• 트리의 시작점
• 2

자녀 노드

• 모든 노드는 0개 이상의 자녀 노드를 가진다.

부모 노드

• 자녀 노드를 가지는 노드
• 2, 5, 9, 6, 11

형제 노드

• 같은 부모를 가지는 노드
• {8, 1, 4}, {6, 7}. {5, 9}

조상 노드

• 부모 노드를 따라 루트 노드까지 올라가며 만나는 모든 노드
• 8의 조상 노드: 11, 9, 2

자손 노드

• 자녀 노드를 따라 내려가며 만날 수 있는 모든 노드
• 9의 자손 노드: 11, 8, 1, 4

내부 노드

• 자녀 노드를 가지는 노드
• 2, 5, 9, 6, 11

외부 노드

• 자녀 노드가 없는 노드
• 리프 노드라고도 부른다.
• 3, 7, 8, 1, 4

경로(path)

• 한 노드에서 다른 노드 사이의 노드들의 시퀀스
• 출발 노드에서 도착 노드까지 포함
• 2에서 7로의 경로: 2 ➔ 5 ➔ 7

경로 길이

• 경로에 있는 노드들의 수
• 2에서 7으로의 경로 길이: 3
• 2에서 3으로의 경로 길이: 4

노드의 높이

• 노드의 자기 자손부터 리프 노드까지의 가장 긴 경로의 간선 수
• 가장 긴 경로의 간선 수
• 5의 높이: 2
• 리프 노드의 높이: 0

트리의 높이

• 루트 노드의 높이
• 트리 높이: 3

노드의 깊이

• 루트 노드에서 해당 노드까지 경로의 간선 수
• 11의 깊이: 2
• 루트 노드의 깊이: 0

트리의 깊이

• 트리에 있는 노드들의 깊이 중 가장 긴 깊이
• 트리 깊이: 3
• 트리 높이 = 트리 깊이

노드의 차수

• 노드의 자녀 노드의 수 
• 11의 차수: 3
• 3의 차수: 0

트리의 차수(degree)

• 트리에 있는 노드들의 차수 중 가장 큰 차수
• 가장 큰 차수: 3
• 트리 차수: 3

두 노드 사이의 거리(distance)

• 두 노드의 최단 경로의 간선 수
• distance(9, 8): 2
• distance(3, 8): 6

노드의 레벨(level)

• 노드와 루트 노드 사이의 경로에서 간선의 수
• 루트 노드의 레벨: 0 or 1
• 문서마다 루트 노드의 레벨부터가 1로 보는 경우가 있다.

width

• 임의의 레벨에서 노드의 수
• level 2의 width: 3
• level 3의 width: 4

노드의 크기(size)

• 자신을 포함한 자손 노드의 수
• 9의 크기: 5
• 5의 크기: 4

트리의 크기(size)

• 트리의 모든 노드의 수
• 트리의 크기: 10

서브 트리(subtree)

• 각 노드의 자녀 노드들을 재귀적으로 서브 트리를 구성한다.

---

트리 구조의 특징

 

1. 루트 노드는 하나만 존재

• 트리는 항상 하나의 루트 노드(root node)를 가진다.
• 이 루트 노드는 트리의 최상단에 위치하며, 모든 다른 노드는 루트로부터 시작되는 경로를 따라 연결된다.

2. 사이클이 존재하지 않음

• 트리에서는 사이클(cycle)이 존재하지 않는다.
• 즉, 어떤 노드도 자기 자신을 참조하거나 다시 부모 노드로 되돌아가는 경로를 가질 수 없다.

 

3. 자녀 노드는 하나의 부모만 존재

• 트리에서 각 자식 노드(Child Node)는 하나의 부모 노드(Parent Node)와 연결된다.
• 한 노드가 여러 부모 노드를 가질 수 없기 때문에, 트리는 명확한 계층 구조를 유지한다.

 

4. 데이터를 순차적으로 저장하지 않는 비선형 구조

• 트리는 배열이나 리스트처럼 순차적으로 데이터를 저장하지 않는 비선형 구조이다.
• 따라서 데이터는 계층적으로 조직되며, 빠른 탐색, 삽입, 삭제 연산에 유리하다.

 

5. 서브 트리가 있는 재귀적 구조

• 트리에서 각 노드는 그 자체로 하나의 트리로 취급될 수 있는 서브 트리(Subtree)를 가진다.
• 이 재귀적 구조 덕분에 트리 알고리즘을 재귀적으로 구현하는 것이 용이하다.

 

6. 계층적 구조

• 트리는 루트 노드를 기준으로 하위 노드로 확장되는 계층적 구조를 가진다.
• 상위 레벨의 노드는 하위 레벨 노드보다 더 높은 계층에 위치하며, 이러한 계층적 구조 덕분에 데이터의 조직화와 탐색이 직관적이다.

 

 

---

이진 트리

이진 트리(binary tree)는 트리의 한 종류로, 각 노드가 최대 두 개의 자식 노드를 가질 수 있는 구조이다.

즉, 부모 노드가 최대 두 개의 자식 노드를 가지며, 이 자식 노드는 왼쪽 자식(left child)과 오른쪽 자식(right child)으로 구분된다. 

정리해서 말하면 각 노드의 자녀 노드 수가 최대 두 개인 트리이다.

이진 트리는 다양한 형태로 활용되며, 특히 탐색 및 정렬에서 효율적으로 사용된다.

---

형태에 따른 이진 트리의 종류

출처: https://towardsdatascience.com/5-types-of-binary-tree-with-cool-illustrations-9b335c430254

 

1. full binary tree(정 이진 트리)

• 모든 노드는 자녀 노드가 없거나 두 개인 트리
• 즉, 자녀 노드가 한 개인 노드는 없다.

2. complete binary tree(완전 이진 트리)

• 마지막 레벨을 제외한 모든 레벨에서 노드가 빠짐없이 채워져 있고 마지막 레벨은 왼쪽부터 빠짐없이 노드가 채워져 있는 트리

3. degenerate binary tree(변질 이진 트리)

• 모든 부모 노드는 하나의 자녀 노드만 가지고 있는 트리
• pathological binary tree 라고도 불림
• left skewed binary tree: 모든 부모 노드는 왼쪽 자녀 노드만 가지는 트리
• right skewed binary tree: 모든 부모 노드는 오른쪽 자녀 노드만 가지는 트리

4. perfect binary tree(포화 이진 트리)

• 모든 레벨에서 노드가 빠짐없이 채워져 있는 트리

5. balanced binary tree(균형 이진 트리)

• 모든 노드에서 왼쪽 서브 트리와 오른쪽 서브 트리의 높이 차이가 최대 1인 트리

---