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

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

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

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

트리의 기본 개념과 주요 용어

트리의 기본 개념

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

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

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

주요 용어

루트 노드(Root Node): 트리의 최상위 노드입니다.
자식 노드(Child Node): 루트 노드에서 연결된 하위 노드입니다.
부모 노드(Parent Node): 자식 노드를 가진 노드입니다.
리프 노드(Leaf Node): 자식 노드가 없는 노드로, 트리의 끝에 위치합니다.
서브트리(Subtree): 트리 내의 하나의 노드를 루트로 하는 부분 트리입니다.
깊이(Depth): 루트 노드에서 특정 노드까지의 경로 길이입니다.
높이(Height): 트리의 루트에서 가장 깊은 리프 노드까지의 길이입니다.

파이썬에서의 트리 구현 간단 예제

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

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

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

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

간단한 이진 트리 구현 예제
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)

코드 실행 결과

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

출력 결과
Root: 10
   L: 5
      L: 3
      R: 7
   R: 15
      L: 13
      R: 17

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

트리 구조 활용 사례

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

파일 시스템: 운영체제의 파일 구조는 디렉터리와 파일이 노드로, 디렉터리 간의 포함 관계가 간선으로 표현됩니다.
검색 알고리즘: 이진 검색 트리(Binary Search Tree)를 사용하면 데이터 검색 속도를 크게 향상시킬 수 있습니다.
문서 구조: HTML이나 XML 같은 문서 구조는 트리 형태로 표현되어, 요소 간의 계층 관계를 나타냅니다.

다음 내용이 궁금하다면?

코드프렌즈 PLUS 멤버십 가입 or 강의를 등록해 주세요!

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

트리의 기본 개념과 주요 용어​

트리의 기본 개념​

주요 용어​

파이썬에서의 트리 구현 간단 예제​

코드 실행 결과​

트리 구조 활용 사례​