트리(Tree)란 무엇일까요?

트리(Tree)는 계층적 데이터 구조를 표현하는 자료구조입니다.

트리는 루트(root)라고 불리는 하나의 노드에서 시작하여 여러 자식 노드로 확장되며, 각 노드는 다시 자식 노드를 가질 수 있습니다.

트리는 파일 시스템, 검색 알고리즘 등 다양한 분야에 활용됩니다.

트리는 노드(Node)와 간선(Edge)으로 구성됩니다.

노드는 데이터를 저장하는 단위이며, 간선은 노드 간의 관계를 나타냅니다.

트리에서 최상위에 있는 노드를 루트(Root)라고 부르며, 이 루트에서 시작해 여러 자식 노드로 뻗어 나갑니다.

• 루트 노드(Root Node): 트리의 최상위 노드입니다.

• 자식 노드(Child Node): 루트 노드에서 연결된 하위 노드입니다.

• 부모 노드(Parent Node): 자식 노드를 가진 노드입니다.

• 리프 노드(Leaf Node): 자식 노드가 없는 노드로, 트리의 끝에 위치합니다.

• 서브트리(Subtree): 트리 내의 하나의 노드를 루트로 하는 부분 트리입니다.

• 깊이(Depth): 루트 노드에서 특정 노드까지의 경로 길이입니다.

• 높이(Height): 트리의 루트에서 가장 깊은 리프 노드까지의 길이입니다.

트리를 구현하는 여러 가지 방법이 있지만, 이번 수업에서는 가장 간단한 구조인 이진 트리(Binary Tree)를 소개합니다.

이진 트리는 각 노드가 최대 2개의 자식 노드를 갖는 트리입니다.

아래 이진 트리는 루트 노드가 10이고, 왼쪽 자식 노드는 5, 오른쪽 자식 노드는 15인 구조입니다.

Copy
       10
      /  \
     5    15

아래 코드는 루트 노드보다 작은 데이터는 왼쪽 서브트리에, 같거나 큰 데이터는 오른쪽 서브트리에 삽입하는 이진 트리를 구현한 코드입니다.

Copy
class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

class BinaryTree:
    def __init__(self, root_data):
        # 루트 노드를 설정합니다.
        self.root = Node(root_data)

    def insert(self, current_node, data):
        # 루트보다 작은 데이터는 왼쪽 서브트리에 삽입
        if data < current_node.data:
            if current_node.left is None:
                current_node.left = Node(data)
                print(f"{data}가 {current_node.data}의 왼쪽에 추가되었습니다.")
            else:
                self.insert(current_node.left, data)
        # 루트와 같거나 큰 데이터는 오른쪽 서브트리에 삽입
        else:
            if current_node.right is None:
                current_node.right = Node(data)
                print(f"{data}가 {current_node.data}의 오른쪽에 추가되었습니다.")
            else:
                self.insert(current_node.right, data)

    def display(self, node, indent="", position="Root"):
        # 현재 노드를 출력
        if node is not None:
            print(indent + position + ": " + str(node.data))
            # 왼쪽 자식 노드를 먼저 출력 (아래쪽에 위치)
            self.display(node.left, indent + "   ", "L")
            # 오른쪽 자식 노드를 출력 (아래쪽에 위치)
            self.display(node.right, indent + "   ", "R")

# 이진 트리 사용 예시
bt = BinaryTree(10)  # 루트 노드로 10을 설정

bt.insert(bt.root, 5)  # 5는 10보다 작으므로 왼쪽에 추가

bt.insert(bt.root, 15)  # 15는 10보다 크므로 오른쪽에 추가

bt.insert(bt.root, 3)  # 3은 5보다 작으므로 5의 왼쪽에 추가

bt.insert(bt.root, 7)  # 7은 5보다 크므로 5의 오른쪽에 추가

bt.insert(bt.root, 13)  # 13은 15보다 작으므로 15의 왼쪽에 추가

bt.insert(bt.root, 17)  # 17은 15보다 크므로 15의 오른쪽에 추가

bt.display(bt.root)

위 코드를 실행하면 아래와 같이 이진 트리가 생성되고, 각 노드의 위치에 데이터가 추가됩니다.

Copy
Root: 10
   L: 5
      L: 3
      R: 7
   R: 15
      L: 13
      R: 17

이렇게 이진 트리는 루트 노드를 시작으로 왼쪽과 오른쪽 서브트리로 나뉘어 데이터를 저장합니다.

트리는 다양한 실생활 문제를 해결하는 데 사용됩니다.

• 파일 시스템: 운영체제의 파일 구조는 디렉터리와 파일이 노드로, 디렉터리 간의 포함 관계가 간선으로 표현됩니다.

• 검색 알고리즘: 이진 검색 트리(Binary Search Tree)를 사용하면 데이터 검색 속도를 크게 향상시킬 수 있습니다.

• 문서 구조: HTML이나 XML 같은 문서 구조는 트리 형태로 표현되어, 요소 간의 계층 관계를 나타냅니다.