AI Agent Developer 황화인 blog

트리

10 min read

트리 (Tree)

한마디 요약: 데이터를 “부모-자식” 관계로 가지치듯 이어놓은 계층 구조. JSON·파일시스템·DOM·의사결정·AST까지, 이름만 다를 뿐 AI Agent가 만지는 거의 모든 구조화 데이터가 트리다.

1. 트리가 뭔가

Tree(트리, 계층 구조 자료구조): 하나의 Root(루트, 뿌리 노드) 에서 시작해 자식으로 가지가 뻗어나가는 구조. 순환(자기 자신으로 돌아오는 길)이 없고, 모든 노드가 부모를 정확히 하나만 가진다(루트는 제외).

일상 비유: 가계도. 할아버지(루트) 아래 아버지, 삼촌이 자식으로 달리고, 그 밑에 나와 사촌이 손자로 달린다. 누구도 두 명의 아버지를 갖지 않고, 내가 할아버지로 거슬러 올라가는 길은 하나뿐이다.

포함 관계:

  • 트리는 Graph(그래프, 노드와 엣지로 이루어진 관계망) 의 특수한 형태. “순환 없고, 모두 연결됨”이라는 제약을 단 그래프가 트리.
  • Binary Tree(이진 트리, 자식이 최대 2개인 트리) 는 트리의 하위 유형.
  • BST(Binary Search Tree, 이진 탐색 트리) 는 이진 트리에 “왼쪽은 작은 값, 오른쪽은 큰 값” 규칙을 추가한 것.
  • Heap(힙) 은 큐의 우선순위 큐에 쓰이는 특수한 이진 트리.

즉: 그래프 ⊃ 트리 ⊃ 이진 트리 ⊃ BST / Heap.

2. 트리 용어 한 번에 정리

용어의미가계도 비유
Node(노드)데이터 한 개가 담긴 점사람 한 명
Root(루트)최상단 노드, 조상시조, 할아버지
Parent(부모)바로 위 노드아버지
Child(자식)바로 아래 노드아들/딸
Sibling(형제)같은 부모를 둔 노드형제자매
Leaf(리프, 잎 노드)자식이 없는 끝 노드자손이 없는 사람
Depth(깊이)루트에서 해당 노드까지 거리몇 대손인지
Height(높이)노드에서 가장 먼 리프까지 거리아래로 몇 대가 더 있는지
Subtree(서브트리)특정 노드를 루트로 하는 부분 트리한 집안

3. 이진 트리와 BST

Binary Tree(이진 트리): 자식이 왼쪽·오른쪽 최대 두 개. 구현과 분석이 단순해서 교과서·면접에 가장 많이 나옴.

BST(Binary Search Tree, 이진 탐색 트리) 의 규칙:

  • 왼쪽 자식 < 부모 < 오른쪽 자식
  • 이 규칙이 모든 노드에 재귀적으로 성립

BST로 17 찾기 단계 분해 (루트가 30, 왼쪽에 20, 20의 왼쪽에 15, 15의 오른쪽에 17):

1단계: 루트 30과 비교 → 17이 더 작다 → 왼쪽으로 2단계: 20과 비교 → 17이 더 작다 → 왼쪽으로 3단계: 15와 비교 → 17이 더 크다 → 오른쪽으로 4단계: 17 찾음. 총 4번 비교.

노드가 100만 개여도 균형 잡힌 BST라면 약 20번(log₂ 1,000,000 ≈ 20)만에 끝난다. 이게 시간복잡도_기초에서 말하는 O(log n).

단, 균형이 깨지면(한쪽으로만 가지가 자라면) 최악 O(n)이 된다. 이를 막으려고 AVL Tree, Red-Black Tree 같은 자가 균형 트리가 존재. Python dict 내부 구현이나 데이터베이스 인덱스(B-Tree, B+Tree)가 이 계열.

4. 트리 순회(Traversal) 방법

트리의 모든 노드를 방문하는 순서는 네 가지 대표가 있다.

방식순서용도
전위(Preorder)루트 → 왼쪽 → 오른쪽트리 복제, 구조 출력
중위(Inorder)왼쪽 → 루트 → 오른쪽BST에서 정렬된 값 얻기
후위(Postorder)왼쪽 → 오른쪽 → 루트트리 삭제, 계산식 평가
레벨(BFS)위에서 아래, 같은 층은 왼쪽부터가장 가까운 노드 탐색

앞의 셋은 DFS(Depth-First Search, 깊이 우선, 한 가지 끝까지 파고 돌아옴), 마지막은 BFS(Breadth-First Search, 너비 우선, 층별로 훑음). DFS는 재귀 또는 큐의 형제인 스택으로, BFS는 큐로 구현한다.

5. Python에서 직접 확인

# 간단한 이진 트리 구현
class Node:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None
 
# 트리 만들기
#        10
#       /  \
#      5    15
#     / \
#    3   7
root = Node(10)
root.left = Node(5)
root.right = Node(15)
root.left.left = Node(3)
root.left.right = Node(7)
 
# DFS 중위 순회 (BST면 정렬된 순서)
def inorder(node):
    if node is None:
        return
    inorder(node.left)
    print(node.value, end=" ")
    inorder(node.right)
 
inorder(root)  # 3 5 7 10 15
 
# BFS 레벨 순회
from collections import deque
def bfs(root):
    q = deque([root])
    while q:
        node = q.popleft()
        print(node.value, end=" ")
        if node.left:  q.append(node.left)
        if node.right: q.append(node.right)
 
print()
bfs(root)  # 10 5 15 3 7

터미널에서 돌려보면 같은 트리인데 순회 방식에 따라 출력 순서가 다르다는 걸 확인할 수 있다.

6. AI Agent 개발에서 어디에 쓰이나

JSON 파싱 결과는 트리다: API 응답으로 받은 JSON은 중첩된 객체·배열 구조. Python이 json.loads()로 읽으면 dict/list가 섞인 트리 형태로 들어온다. 특정 필드 꺼내기는 트리 순회. 직렬화_JSON_YAML 참고.

파일시스템: 폴더-파일 구조가 트리. C:\1.Project\블로그 지식 옮기기\프로그래밍_CS\ 도 루트부터 리프까지 이어지는 경로.

AST(Abstract Syntax Tree, 추상 구문 트리, 코드를 문법 단위로 쪼갠 트리): Python의 ast 모듈, LLM이 코드를 생성·분석할 때 내부적으로 다루는 구조. “이 코드 안의 모든 함수 이름 뽑기” 같은 작업이 AST 순회.

의사결정 트리(Decision Tree): Agent가 “질문 받음 → 툴 필요? → 어떤 툴?” 식으로 분기할 때. LangGraph의 Conditional Edge가 이 형태.

DOM(Document Object Model, HTML 문서 트리): 웹 스크래핑에서 BeautifulSoup이 HTML을 트리로 파싱. .find(), .select()가 트리 탐색.

Tree of Thoughts(ToT, 사고 트리 프롬프팅): LLM이 여러 추론 경로를 가지처럼 뻗고, 각 경로를 평가한 뒤 가장 유망한 가지를 계속 확장. Agent의 고급 추론 기법.

디렉터리 기반 RAG: 문서를 폴더 계층에 맞춰 인덱싱하고 트리 순회로 관련 문서 묶음을 뽑아냄.

7. 왜 이렇게 만들었나 (설계 의도)

대안 1: 해시맵만 쓰기 → 계층·포함 관계를 표현 못 함. “상위 카테고리 전부 찾기” 같은 게 어려움.

대안 2: 리스트만 쓰기 → 선형이라 1:N 관계 표현 불가.

트리의 트레이드오프:

  • 장점: 계층 표현이 자연스러움, 균형 잡힌 트리는 O(log n) 탐색, 부분 구조(서브트리)를 독립적으로 다룰 수 있음
  • 단점: 구현이 리스트·해시맵보다 복잡, 균형이 깨지면 성능 급락, 포인터(참조) 때문에 메모리 오버헤드 있음
  • “순환이 있을 수 있다”면 트리가 아니라 그래프를 써야 함

핵심 교훈: 데이터에 계층·포함·분기 구조가 있으면 트리가 제일 깔끔하다. JSON, 파일시스템, 조직도처럼 “큰 것 안에 작은 것”이 반복되면 트리로 모델링한다.

8. 관련 문서

Graph View

Backlinks