포스트

트리(Tree)

게시
By 신건우 9 분읽는 시간

트리의 기본 개념

트리(Tree)

undefined

트리는 노드들이 간선(edge)로 연결된 계층적인 데이터 구조이다. 사이클이 없으며, 어떤 두 노드 간에도 유일한 경로가 존재한다.

트리와 그래프의 차이

트리(Tree)

  1. 계층적 구조: 트리는 계층적 관계를 표현하는 데 사용됩니다. 예를 들어, 파일 시스템의 디렉토리 구조는 트리로 표현할 수 있다.
  2. 사이클 없음: 트리에서는 어떤 노드로부터 출발하여 같은 노드로 돌아오는 경로(사이클)가 없다.
  3. 루트 노드 존재: 모든 트리에는 하나의 루트 노드가 있으며, 모든 자식 노드는 하나의 부모 노드를 가진다.
  4. N개의 노드가 있을 때, 항상 N-1개의 에지가 존재: 이는 트리가 연결된 구조임을 의미한다.
  5. 경로의 유일성: 트리 내의 어떤 두 노드 간에도 정확히 하나의 경로만 존재한다.

그래프(Graph)

  1. 일반적인 구조: 그래프는 노드들 간의 임의의 관계를 모델링하는 데 사용된다. 예를 들어, 소셜 네트워크의 사용자 관계, 도로망 등이 있다.
  2. 사이클 허용: 그래프에서는 노드들 사이의 사이클이 존재할 수 있다.
  3. 루트 노드의 개념이 없음: 그래프에는 루트 노드와 같은 특정 시작점이 없을 수 있다. 모든 노드가 동등한 관계를 가질 수 있다.
  4. 에지의 수에 특정한 제한이 없음: 노드의 수에 관계없이 에지의 수는 제한이 없다. 이는 그래프가 더 복잡할 수 있음을 의미한다.
  5. 방향성의 유무: 그래프는 방향성이 있는 유향 그래프(Directed Graph)와 방향성이 없는 무향 그래프(Undirected Graph)로 나뉜다.

용어 설명

  • 루트 노드(Root Node): 트리의 최상위에 위치하는 노드이다. 부모가 없는 유일한 노드이다.
  • 자식 노드(Child Node): 다른 노드로부터 직접 연결된 하위 노드이다.
  • 형제 노드(Sibling Node): 같은 부모 노드를 공유하는 두 개 또는 그 이상의 노드이다.
  • 부모 노드(Parent Node): 다른 노드로부터 직접 연결된 상위 노드이다.
  • 잎 노드(리프 노드, Leaf Node): 자식이 없는 노드로, 트리의 말단에 위치한다.
  • 레벨(Level): 루트 노드에서 특정 노드에 이르기까지 필요한 간선의 수이다. 깊이라고 생각하면 된다. 보통 루트 노드의 레벨은 0이다.
  • 높이(Height): 트리에서 가장 높은 레벨의 값이다.

트리의 종류

  • 이진 트리(Binary Tree): 각 노드가 최대 두 개의 자식을 가질 수 있는 트리이다.
  • 이진 탐색 트리(Binary Search Tree, BST): 왼쪽 자식 노드는 부모 노드보다 작고, 오른쪽 자식 노드는 부모 노드보다 큰 값을 가지는 이진 트리이다.
  • 균형 트리(Balanced Tree): 트리의 높이를 최소로 유지하여 연산의 최악 시간 복잡도를 개선한 트리이다. AVL 트리와 레드-블랙 트리가 대표적이다.
  • B-트리: 데이터베이스와 파일 시스템에서 사용되는 트리로, 노드당 자식의 수가 많을 수 있는 구조이다.

다음에는 간단하게 이진 트리와 이진 탐색 트리를 다룬다.

트리의 순회

전위 순회(Preorder Traversal)

루트를 먼저 방문한 후, 왼쪽 서브트리와 오른쪽 서브트리를 순서대로 방문한다.

중위 순회(Inorder Traversal)

왼쪽 서브트리를 방문한 후, 루트를 방문하고, 그 다음 오른쪽 서브트리를 방문한다. 이진 탐색 트리에서 중위 순회를 하면, 노드의 값을 오름차순으로 방문할 수 있다.

후위 순회(Postorder Traversal)

왼쪽 서브트리와 오른쪽 서브트리를 방문한 후, 마지막으로 루트를 방문한다. 서브트리를 먼저 처리해야 하는 상황에서 사용된다.

레벨 순회 / 너비 우선 탐색(BFS)

트리의 레벨 별로 왼쪽에서 오른쪽으로 노드를 방문한다. 큐(Queue)를 사용하여 구현할 수 있으며, 트리의 레벨 별 노드를 탐색할 때 유용하다.

레벨 순회는 queue로 구현하는 반면에 나머지 순회는 stack으로 구현할 수 있다.

괄호에 따른 우선순위 연산 기능이 들어간 계산기 프로그램을 작성하는데에 순회 알고리즘이 사용된다.

파이썬으로 구현한 트리의 순회 예제

직관적인 이해를 위해 Node class를 정의하여 구현했다.

각 순회 방식은 보통 재귀함수로 구현된다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

class Node:
    def __init__(self, key):
        self.left = None
        self.right = None
        self.val = key

# 전위 순회(Preorder Traversal)
def preorderTraversal(root):
    if root:
        print(root.val, end=' ')  # 루트 방문
        preorderTraversal(root.left)  # 왼쪽 서브트리 순회
        preorderTraversal(root.right)  # 오른쪽 서브트리 순회

# 중위 순회(Inorder Traversal)
def inorderTraversal(root):
    if root:
        inorderTraversal(root.left)  # 왼쪽 서브트리 순회
        print(root.val, end=' ')  # 루트 방문
        inorderTraversal(root.right)  # 오른쪽 서브트리 순회

# 후위 순회(Postorder Traversal)
def postorderTraversal(root):
    if root:
        postorderTraversal(root.left)  # 왼쪽 서브트리 순회
        postorderTraversal(root.right)  # 오른쪽 서브트리 순회
        print(root.val, end=' ')  # 루트 방문
        
# 이진 트리 생성
#       1
#     /   \
#    2     3
#   / \   / \
#  4   5 6   7

root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
root.right.left = Node(6)
root.right.right = Node(7)

print("전위 순회(Preorder Traversal):", end=' ')
preorderTraversal(root)  # 결과: 1 2 4 5 3 6 7

print("\n중위 순회(Inorder Traversal):", end=' ')
inorderTraversal(root)  # 결과: 4 2 5 1 6 3 7

print("\n후위 순회(Postorder Traversal):", end=' ')
postorderTraversal(root)  # 결과: 4 5 2 6 7 3 1

트리의 탐색

  • 이진 탐색 트리에서의 탐색

  • 깊이 우선 탐색(DFS)과 그 응용
  • 너비 우선 탐색(BFS)과 그 응용

트리의 수정과 삭제

  • 이진 탐색 트리에서의 삽입과 삭제

  • 균형 트리의 삽입과 삭제 과정

  • B-트리와 다른 고급 트리 구조에서의 수정과 삭제

고급 트리 구조

  • 세그먼트 트리(Segment Tree)
  • 펜윅 트리(Fenwick Tree, 이진 인덱스 트리)
  • 트라이(Trie, 접두사 트리)
  • k-d 트리, R-트리 등의 공간 탐색 구조

참고자료

Algorithm, Structure
Algorithm Tree Traversal
이 기사는 저작권자의 CC BY 4.0 라이센스를 따릅니다.