카테고리 없음

[자료구조개론] 4. 트리 완벽 설명

설화님 2024. 9. 24. 10:11
트리(Tree) 자료구조

4. 트리 (Tree)

트리(Tree)는 비선형 자료구조로, 노드(Node)와 노드를 연결하는 간선(Edge)으로 구성됩니다. 트리는 계층적 구조를 가지며, 루트 노드(Root Node)부터 시작하여 여러 자식 노드로 분기됩니다. 트리는 주로 데이터의 계층 구조를 나타내거나 탐색, 정렬, 우선순위 큐 등의 문제를 해결하는 데 사용됩니다.

4.1 트리의 기본 개념

트리 자료구조는 루트 노드에서 시작하여 각 노드가 자식 노드를 가질 수 있는 구조를 가지고 있습니다. 트리는 다음과 같은 기본 용어로 구성됩니다:

  • 루트 노드(Root Node): 트리의 시작점이 되는 노드입니다.
  • 자식 노드(Child Node): 부모 노드에서 분기되는 하위 노드입니다.
  • 부모 노드(Parent Node): 자식 노드를 가지는 상위 노드입니다.
  • 리프 노드(Leaf Node): 자식이 없는 마지막 노드입니다.
  • 레벨(Level): 루트에서 특정 노드까지의 거리 또는 깊이를 의미합니다.
트리 구조

4.2 이진 트리(Binary Tree)

이진 트리는 각 노드가 최대 두 개의 자식 노드(왼쪽 자식과 오른쪽 자식)를 가지는 트리입니다. 이진 트리는 탐색과 정렬 알고리즘의 기본 자료구조로 자주 사용됩니다. 트리의 순회 방식(중위 순회, 전위 순회, 후위 순회)에 따라 데이터를 처리하는 방법이 달라집니다.

예제: 이진 트리 구현

class Node:
    def __init__(self, data):
        self.data = data  # 노드에 저장된 데이터
        self.left = None  # 왼쪽 자식 노드
        self.right = None  # 오른쪽 자식 노드

class BinaryTree:
    def __init__(self):
        self.root = None  # 트리의 루트 노드

    # 트리에 데이터를 삽입하는 함수
    def insert(self, data):
        if self.root is None:
            self.root = Node(data)  # 루트 노드가 없으면 생성
        else:
            self._insert_recursive(data, self.root)

    # 재귀적으로 데이터를 삽입하는 헬퍼 함수
    def _insert_recursive(self, data, node):
        if data < node.data:  # 현재 노드보다 작은 데이터는 왼쪽에 삽입
            if node.left is None:
                node.left = Node(data)
            else:
                self._insert_recursive(data, node.left)
        else:  # 큰 데이터는 오른쪽에 삽입
            if node.right is None:
                node.right = Node(data)
            else:
                self._insert_recursive(data, node.right)

    # 이진 트리를 중위 순회하며 출력하는 함수
    def inorder_traversal(self, node):
        if node:
            self.inorder_traversal(node.left)
            print(node.data, end=' ')
            self.inorder_traversal(node.right)

# 이진 트리 생성 및 데이터 삽입
tree = BinaryTree()
tree.insert(50)
tree.insert(30)
tree.insert(70)
tree.insert(20)
tree.insert(40)
tree.insert(60)
tree.insert(80)

# 트리의 중위 순회 출력
print("이진 트리 중위 순회 결과:")
tree.inorder_traversal(tree.root)  # 출력: 20 30 40 50 60 70 80

4.3 이진 탐색 트리(Binary Search Tree, BST)

이진 탐색 트리(BST)는 이진 트리의 한 종류로, 노드의 왼쪽 자식은 부모 노드보다 작은 값을, 오른쪽 자식은 부모 노드보다 큰 값을 갖는 특성을 가집니다. 이진 탐색 트리는 효율적인 탐색, 삽입, 삭제 연산을 제공하며, 평균적으로 O(log n)의 시간 복잡도를 가집니다.

예제: 이진 탐색 트리에서 값 검색

# 이진 탐색 트리에서 특정 값을 검색하는 함수
def search(node, key):
    # 트리가 비어있거나 값을 찾으면 해당 노드 반환
    if node is None or node.data == key:
        return node
    
    # 찾는 값이 현재 노드보다 작으면 왼쪽 하위 트리를 검색
    if key < node.data:
        return search(node.left, key)
    
    # 찾는 값이 현재 노드보다 크면 오른쪽 하위 트리를 검색
    return search(node.right, key)

# 60 값 검색
result = search(tree.root, 60)
if result:
    print(f"찾은 값: {result.data}")  # 출력: 찾은 값: 60
else:
    print("값을 찾을 수 없습니다.")

4.4 트리의 응용

트리 자료구조는 다양한 응용 분야에서 사용됩니다. 대표적인 응용 사례는 다음과 같습니다:

  • 파일 시스템: 파일 시스템은 트리 구조를 사용하여 디렉토리와 파일을 관리합니다. 루트 디렉토리는 트리의 루트 노드 역할을 하며, 각 파일과 폴더는 자식 노드로 연결됩니다.
  • 게임 AI: 트리는 게임에서 가능한 모든 경로를 탐색하고 최적의 결정을 내리는 데 자주 사용됩니다.
  • 이진 힙(Binary Heap): 이진 힙은 우선순위 큐를 구현하는 데 사용되며, 힙 정렬에서도 중요한 역할을 합니다.
이진 탐색 트리 예시