트리(Tree)란?

트리(Tree)는 계층적인 구조를 가지는 비선형 자료구조다.

루트 노드(Root Node)에서 시작해 여러 개의 하위 노드(Child Node)로 확장되는 형태를 가진다.

트리는 데이터 탐색, 계층적 관계 표현 등에 많이 사용되며, 이진 트리(Binary Tree) 형태로 구현되는 경우가 많다.

 

https://ko.wikipedia.org/wiki/트리_구조

 

트리의 기본 개념

트리는 여러 개의 노드(Node)로 구성되며, 각 노드는 부모-자식 관계를 가진다.

그래프의 일종이지만, 순환(Cycle)이 없는 구조라는 점이 다르다.

 

트리의 주요 용어

• 노드(Node): 트리의 기본 구성 요소로 데이터를 저장하는 단위
• 루트 노드(Root Node): 트리의 최상단에 위치한 노드
• 부모 노드(Parent Node): 어떤 노드를 포함하는 상위 노드
• 자식 노드(Child Node): 특정 노드 아래에 연결된 노드
• 형제 노드(Sibling Node): 같은 부모 노드를 가진 노드들
• 리프 노드(Leaf Node): 자식 노드가 없는 노드
• 레벨(Level): 루트 노드에서부터의 깊이 (루트는 Level 0)
• 깊이(Depth): 트리에서 가장 깊은 레벨의 값

 

트리와 그래프의 차이점

트리는 그래프의 일종이지만, 몇 가지 중요한 차이점이 있다.

비교	트리(Tree)	그래프(Graph)
사이클 여부	없음 (비순환)	있을 수도 있음
연결 방식	부모-자식 관계	다양한 방식으로 연결 가능
루트 노드	존재	존재하지 않을 수도 있음

 

트리의 종류

1. 이진 트리(Binary Tree)

• 각 노드가 최대 2개의 자식 노드를 가질 수 있는 트리
• 탐색, 정렬, 연산 등에 많이 사용됨
• 종류: 완전 이진 트리, 포화 이진 트리, 균형 이진 트리 등

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

• 왼쪽 자식 노드는 부모보다 작은 값, 오른쪽 자식 노드는 부모보다 큰 값을 가짐
• 탐색 연산(O(log n))이 빠름

3. 균형 트리(Balanced Tree)

• 트리의 높이를 최소화하여 탐색 성능을 최적화한 트리
• 예: AVL 트리, 레드-블랙 트리

 

파이썬 구현 예제 (이진트리)

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

class BinaryTree:
    def __init__(self):
        self.root = None

    def insert(self, value):
        if self.root is None:
            self.root = Node(value)
        else:
            self._insert(self.root, value)

    def _insert(self, node, value):
        if value < node.value:
            if node.left is None:
                node.left = Node(value)
            else:
                self._insert(node.left, value)
        else:
            if node.right is None:
                node.right = Node(value)
            else:
                self._insert(node.right, value)

    def inorder_traversal(self, node, result=[]):
        if node:
            self.inorder_traversal(node.left, result)
            result.append(node.value)
            self.inorder_traversal(node.right, result)
        return result

# 사용 예제
tree = BinaryTree()
tree.insert(5)
tree.insert(3)
tree.insert(7)
tree.insert(2)
tree.insert(4)

print(tree.inorder_traversal(tree.root))  # [2, 3, 4, 5, 7]

 

트리의 활용

트리는 다양한 분야에서 활용된다.

• 파일 시스템: 디렉터리 구조를 트리 형태로 표현
• 데이터베이스 인덱싱: B-트리, B+트리를 활용한 빠른 검색
• HTML DOM: HTML 문서의 계층적 구조 표현
• AI 및 경로 탐색: 게임 트리, 의사 결정 트리 등에 활용

 

---

 

 

눈떠보니 코딩테스트 전날 강의 | 제주코딩베이스캠프 - 인프런