트리란?

1. 트리란?

트리

• 데이터의 계층적 관계를 저장하는 자료 구조
• 여러 개의 노드로 이루어져 있다.
  • 노드(Node): 데이터를 저장하는 하나의 단위
• 루트 노드(root node): 트리의 시작 노드, 부모 노드가 없다.
• 부모 노드(parent node): 특정 노드의 직속 상위 노드
• 자식 노드(child node): 특정 노드의 직속 하위 노드
• 형제 노드(sibling node): 같은 부모를 갖는 노드
• leaf 노드: 자식 노드를 갖고 있지 않는 노드
• 깊이(depth): 해당 노드로 가기 위해서 root 노드에서 몇 번 아래로 내려와야 하는지를 나타내는 거리
• 레벨(level): 깊이에 1을 더한 값
• 높이(height): 트리에서 가장 깊은 노드의 깊이
• 부분 트리(sub-tree): 현재 트리의 일부분을 이루고 있는 더 작은 트리

2. 트리의 활용

• 계층적 관계가 있는 데이터를 컴퓨터에서 사용할 수 있게 해준다.
• 컴퓨터 과학의 다양한 문제를 효율적으로 해결할 수 있게 해준다.
  • 정렬 문제(sorting problem): 주어진 데이터를 순서대로 재배치시키는 것
  • 압축 문제(compression problem):용량이 큰 파일을 더 작은 용량으로 저장하는 것
• 다양한 추상 자료형을 구현할 수 있게 해준다.
  • 딕셔너리, 세트, 우선순위 큐(Priority Queue) 등

3. 이진 트리

이진 트리(Binary tree)

• 각 노드가 최대 2개의 자식 노드를 갖을 수 있는 트리
• 2개의 자식 노드를 각각 왼쪽 자식 노드, 오른쪽 자식 노드라고 한다.

이진 트리 구현 (Python)

class Node:
    """이진 노드 클래스"""

    def __init__(self, data):
        """데이터와 두 자식 노드에 대한 레퍼런스를 갖는다"""
        self.data = data
        self.left_child = None
        self.right_child = None


# 노드 인스턴스 생성
root_node = Node(2)
node_B = Node(3)
node_C = Node(5)
node_D = Node(7)
node_E = Node(11)

# B와 C를 root 노드의 자식으로 지정
root_node.left_child = node_B
root_node.right_child = node_C

# D와 E를 B의 자식으로 지정
node_B.left_child = node_D
node_B.right_child = node_E

# root 노드에서 왼쪽 자식 노드 받아오기
test_node_1 = root_node.left_child

print(test_node_1.data)  # B 노드의 데이터 출력

3

4. 이진 트리 종류

정 이진 트리(Full binary tree)

• 모든 노드가 2개 또는 0개의 자식을 갖는 이진 트리
  

완전 이진 트리(Complete binary tree)

• 마지막 레벨 직전의 레벨까지는 모든 노드들이 다 채워진 이진 트리
• 마지막 레벨의 노드는 왼쪽에서 오른쪽 방향으로 채워야 한다.
• n이 노드의 갯수일 때 완전 이진 트리의 높이는 [lg(n)]이다. (O(log(n))
  

포화 이진 트리(Perfect binary tree)

• 모든 레벨이 빠짐없이 다 노드로 채워져 있는 이진 트리
  

5. 트리 순회

순회(Traversal)

• 자료 구조에 저장된 모든 데이터를 하나씩 도는 것

트리 순회의 기본 동작

1. 재귀적으로 왼쪽 부분 트리를 순회한다.
2. 재귀적으로 오른쪽 부분 트리를 순회한다.
3. 현재 노드 데이터로 출력 등과 같은 원하는 동작을 한다.

• 기본 동작의 순서에 따라 순회 방식이 달라진다.
• 트리 순회 방식에 따라 트리에도 선형적 관계를 사용할 수 있다.

6. 트리 순회 방식

pre-order 순회

1. 현재 노드 데이터를 출력한다.
2. 재귀적으로 왼쪽 부분 트리를 순회한다.
3. 재귀적으로 오른쪽 부분 트리를 순회한다.

• 부분 트리 순회 전에(pre) 현재 노드를 출력하는 방식

post-order 순회

1. 재귀적으로 왼쪽 부분 트리를 순회한다.
2. 재귀적으로 오른쪽 부분 트리를 순회한다.
3. 현재 노드 데이터를 출력한다.

• 부분 트리 순회 후에(post) 현재 노드를 출력하는 방식

in-order 순회

1. 재귀적으로 왼쪽 부분 트리를 순회한다.
2. 현재 노드 데이터를 출력한다.
3. 재귀적으로 오른쪽 부분 트리를 순회한다.

• 부분 트리 순회 사이에(in-order) 현재 노드를 출력하는 방식

참고 자료

• What are the different types of Nodes in a Tree - GeeksforGeeks
• 트리 - 알고리즘 · 자료구조 강의 | 코드잇