[자료구조] 트리 Tree

출처

ChatGPT

---

트리(Tree) 구조는 컴퓨터 과학에서 계층적인 데이터를 표현하는 중요한 자료 구조 중 하나이다. 트리는 하나의 루트 노드(root node)에서 시작하여, 여러 자식 노드를 연결하여 계층적 관계를 나타내는 방식으로 데이터를 관리한다. 트리는 그래프의 한 종류로, 사이클이 없는 무방향 그래프라고 볼 수 있다. 즉, 트리는 한 방향으로만 흐르는 계층적 관계를 가지며, 노드 간의 순환이 없다.

트리의 기본 개념

1. 노드(Node)

트리의 기본 구성 요소로, 데이터를 담고 있다. 각 노드는 부모 노드나 자식 노드와 연결된다.

2. 루트 노드(Root Node)

트리의 최상위 노드로, 트리의 시작점이 된다. 트리는 루트 노드를 기준으로 계층을 형성한다.

3. 자식 노드(Child Node)

특정 노드에서 아래로 연결된 노드이다. 트리에서 부모 노드와 연결된 모든 노드를 자식 노드라고 한다.

4. 부모 노드(Parent Node)

자식 노드를 가지는 노드입니다. 자식 노드와 연결된 상위 노드를 부모 노드라고 한다.

5. 잎(리프) 노드(Leaf Node)

자식 노드가 없는 노드로, 트리의 끝부분을 나타낸다.

6. 서브트리(Subtree)

트리의 특정 노드를 루트로 가지는 작은 트리이다.

7. 간선(Edge)

트리의 노드 간을 연결하는 선입니다. 부모 노드와 자식 노드 간의 관계를 나타냅니다.

8. 레벨(Level)

트리의 깊이(depth)를 나타내며, 루트 노드에서 특정 노드까지의 거리를 의미합니다.

트리의 특징

1. 계층 구조

트리는 계층적인 구조를 가지며, 각 노드는 부모와 자식의 관계로 연결된다.

2. 루트 노드

트리에는 반드시 하나의 루트 노드가 존재하며, 루트에서부터 자식 노드로 연결됩니다.

3. 사이클 없음

트리 구조는 사이클이 없는 그래프입니다. 즉, 어떤 노드도 자식 노드나 하위 노드를 통해 다시 자기 자신으로 돌아올 수 없다.

4. 자식 노드 개수

트리의 각 노드는 여러 개의 자식 노드를 가질 수 있지만, 특정 트리에서는 자식 노드의 수를 제한하기도 합니다(예: 이진 트리에서는 각 노드가 최대 두 개의 자식 노드를 가질 수 있음).

트리의 종류

1. 일반 트리 General Tree

각 노드가 자식 노드를 여러 개 가질 수 있는 트리이다. 자식 노드의 수에 제한이 없다.

2. 이진 트리 Binary Tree

각 노드가 최대 두 개의 자식 노드를 가지는 트리이다. 자식 노드는 왼쪽 자식과 오른쪽 자식으로 나뉜다.

3. 포화 이진 트리 Full Binary Tree

모든 노드가 0개 또는 2개의 자식 노드를 가지는 이진 트리이다.

4. 완전 이진 트리 Complete Binary Tree

마지막 레벨을 제외한 모든 레벨이 꽉 차 있으며, 마지막 레벨의 노드가 왼쪽에서 오른쪽 순으로 차례대로 채워져 있는 트리이다.

5. 이진 탐색 트리 Binary Search Tree, BST

이진 트리의 한 종류로, 왼쪽 자식 노드는 부모 노드보다 작은 값, 오른쪽 자식 노드는 부모 노드보다 큰 값을 가지는 트리이다.

6. 균형 트리 Balanced Tree

트리의 모든 노드가 좌우 균형을 이루도록 유지되는 트리이다. 균형 트리에서는 삽입과 삭제가 이루어질 때도 트리의 균형이 자동으로 유지된다. 레드-블랙 트리, AVL 트리 등이 여기에 속한다.

7. 힙(Heap)

우선순위 큐를 구현하는 데 사용되는 트리로, 각 부모 노드가 자식 노드보다 크거나(최대 힙) 또는 작거나(최소 힙) 하는 특성을 가지는 완전 이진 트리이다.

8. 트라이(Trie)

문자열이나 키(key)를 저장하고 빠르게 검색하는 데 사용되는 트리이다. 주로 텍스트 검색 엔진이나 사전 구현에 사용된다.

트리 순회 Tree Traversal

트리에서 모든 노드를 방문하는 순서를 트리 순회라고 한다. 순회 방식에 따라 트리의 노드를 차례로 처리할 수 있다.

1. 전위 순회 Pre-order Traversal

• 루트 노드를 먼저 방문한 후, 왼쪽 서브트리, 오른쪽 서브트리 순서로 방문한다.
• 순서: 루트 → 왼쪽 자식 → 오른쪽 자식.

2. 중위 순회 In-order Traversal

• 왼쪽 서브트리를 먼저 방문한 후, 루트 노드, 오른쪽 서브트리 순서로 방문한다.
• 순서: 왼쪽 자식 → 루트 → 오른쪽 자식.
• 이진 탐색 트리에서 중위 순회를 하면 정렬된 순서의 값을 얻을 수 있다.

3. 후위 순회 Post-order Traversal

• 왼쪽 서브트리, 오른쪽 서브트리를 먼저 방문한 후 루트 노드를 방문한다.
• 순서: 왼쪽 자식 → 오른쪽 자식 → 루트.

4. 레벨 순회 Level-order Traversal

• 트리의 각 레벨을 왼쪽에서 오른쪽으로 순서대로 방문합니다.

 

트리의 응용

1. 파일 시스템

운영 체제의 파일 시스템에서 파일과 디렉토리는 트리 구조로 저장된다. 최상위에 루트 디렉토리가 있고, 그 아래에 자식 디렉토리와 파일이 계층적으로 저장된다.

2. 데이터베이스 인덱스

트리는 데이터베이스에서 인덱스를 구성하는 데 사용된다. 특히 B-트리, B+ 트리와 같은 구조는 대용량 데이터를 효율적으로 검색하는 데 사용된다.

3. 이진 탐색

이진 탐색 트리는 데이터를 정렬된 상태로 저장하고, 탐색을 빠르게 수행할 수 있도록 한다.

4. 컴파일러

컴파일러는 소스 코드를 분석하여 구문 트리(Syntax Tree)또는 추상 구문 트리(AST, Abstract Syntax Tree)를 생성하고, 이를 기반으로 코드의 구문 분석과 최적화를 수행한다.

• 관련 글 -> [자료구조] 구문 트리 Syntax Tree, 추상 구문 트리 AST, Abstract Syntax Tree

 

결론

트리는 다양한 문제를 해결하기 위해 계층적 구조를 사용하며, 데이터의 효율적인 탐색과 처리를 가능하게 한다. 특히 이진 탐색 트리, 균형 트리, 힙과 같은 다양한 트리 구조는 각각의 문제를 해결하는 데 특화되어 있다. 트리는 현대의 많은 소프트웨어 시스템에서 중요한 자료 구조로 사용된다.