트리 자료구조 | 이진 트리, BST, 순회 완벽 정리

· 22분 읽기 · 수정 중급 튜토리얼
트리 자료구조 | 이진 트리, BST, 순회 완벽 정리

이 글의 핵심

트리 자료구조에 대한 실전 가이드입니다. 이진 트리, BST, 순회 완벽 정리 등을 예제와 함께 상세히 설명합니다.

들어가며

”계층 구조의 완벽한 표현”

트리는 계층 구조를 표현하는 자료구조입니다. 파일 시스템, DOM, 조직도 등 모두 트리입니다.

1. 트리 기본 개념

용어

        1  ← 루트(Root)
       / \
      2   3  ← 자식(Child)
     / \
    4   5  ← 리프(Leaf)

- 노드(Node): 1, 2, 3, 4, 5
- 간선(Edge): 노드를 연결하는 선
- 부모(Parent): 2의 부모는 1
- 자식(Child): 1의 자식은 2, 3
- 형제(Sibling): 2와 3
- 깊이(Depth): 루트부터 거리 (4의 깊이 = 2)
- 높이(Height): 리프까지 최대 거리 (트리 높이 = 2)
- 레벨(Level): 같은 깊이의 노드들

Python 구현

아래는 값(val)과 왼쪽·오른쪽 자식 포인터를 갖는 노드를 정의하고, 루트에서 아래로 가지를 뻗어 연결하는 예입니다. 조직도나 가계도처럼 한 부모 아래에 자식이 달리는 구조를 코드로 만든 것입니다.

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

# 트리 생성
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)

2. 트리 순회

전위 순회 (Preorder)

부모 → 왼쪽 → 오른쪽 순서로 방문합니다:

def preorder(node):
    # 기저 조건: 노드가 없으면 빈 리스트 반환
    if not node:
        return []
    
    # 전위 순회 순서:
    # 1. 부모 노드 먼저 방문: [node.val]
    # 2. 왼쪽 서브트리 순회: preorder(node.left)
    # 3. 오른쪽 서브트리 순회: preorder(node.right)
    return [node.val] + preorder(node.left) + preorder(node.right)

# 트리 구조:
#        1
#       / \
#      2   3
#     / \
#    4   5
#
# 순회 과정:
# 1. 노드 1 방문 → [1]
# 2. 왼쪽(2) 이동 → [1, 2]
# 3. 왼쪽(4) 이동 → [1, 2, 4]
# 4. 4는 리프 → 백트랙
# 5. 오른쪽(5) 이동 → [1, 2, 4, 5]
# 6. 백트랙 후 오른쪽(3) → [1, 2, 4, 5, 3]
#
# 결과: [1, 2, 4, 5, 3]

전위 순회 활용:

  • 트리 복사 (부모부터 생성)
  • 트리 직렬화 (파일 저장)
  • 수식 트리의 전위 표기법 (Prefix notation)

반복문 구현 (스택 사용):

def preorder_iterative(root):
    if not root:
        return []
    
    result = []
    stack = [root]  # 스택에 루트 추가
    
    while stack:
        # 스택에서 노드 꺼내기 (LIFO)
        node = stack.pop()
        result.append(node.val)  # 방문
        
        # 오른쪽 먼저 push (나중에 pop)
        if node.right:
            stack.append(node.right)
        # 왼쪽 나중에 push (먼저 pop)
        if node.left:
            stack.append(node.left)
    
    return result

중위 순회 (Inorder)

왼쪽 → 부모 → 오른쪽:

def inorder(node):
    if not node:
        return []
    
    return inorder(node.left) + [node.val] + inorder(node.right)

# 결과: [4, 2, 5, 1, 3]
# BST에서는 오름차순!

후위 순회 (Postorder)

왼쪽 → 오른쪽 → 부모:

def postorder(node):
    if not node:
        return []
    
    return postorder(node.left) + postorder(node.right) + [node.val]

# 결과: [4, 5, 2, 3, 1]

레벨 순회 (Level Order)

BFS 사용:

from collections import deque

def level_order(root):
    if not root:
        return []
    
    result = []
    queue = deque([root])
    
    while queue:
        node = queue.popleft()
        result.append(node.val)
        
        if node.left:
            queue.append(node.left)
        if node.right:
            queue.append(node.right)
    
    return result

# 결과: [1, 2, 3, 4, 5]

3. 이진 탐색 트리 (BST)

BST 규칙

왼쪽 < 부모 < 오른쪽:

        5
       / \
      3   7
     / \ / \
    2  4 6  8

중위 순회: [2, 3, 4, 5, 6, 7, 8] (정렬됨!)

BST 삽입

BST의 규칙을 유지하며 새 값을 삽입합니다:

def insert_bst(root, val):
    # 기저 조건: 빈 자리를 찾으면 새 노드 생성
    if not root:
        return TreeNode(val)
    
    # BST 규칙: 왼쪽 < 부모 < 오른쪽
    if val < root.val:
        # val이 현재 노드보다 작으면 왼쪽 서브트리에 삽입
        root.left = insert_bst(root.left, val)
    else:
        # val이 현재 노드보다 크거나 같으면 오른쪽 서브트리에 삽입
        # (중복 허용 시 오른쪽에 삽입)
        root.right = insert_bst(root.right, val)
    
    # 현재 노드 반환 (재귀 호출 시 부모에게 연결)
    return root

# 사용 예시
root = TreeNode(5)  # 루트 노드 생성
root = insert_bst(root, 3)  # 5보다 작으므로 왼쪽
root = insert_bst(root, 7)  # 5보다 크므로 오른쪽
root = insert_bst(root, 2)  # 3보다 작으므로 3의 왼쪽

# 결과 트리:
#        5
#       / \
#      3   7
#     /
#    2

# 삽입 과정 (val=2 삽입):
# 1. root(5): 2 < 5 → 왼쪽으로
# 2. node(3): 2 < 3 → 왼쪽으로
# 3. None: 빈 자리 → TreeNode(2) 생성
# 4. 재귀 반환: 3.left = TreeNode(2)
#
# 시간복잡도:
# - 평균: O(log n) - 균형 트리일 때
# - 최악: O(n) - 한쪽으로 치우친 트리일 때 (예: 1→2→3→4→5)

반복문 구현:

def insert_bst_iterative(root, val):
    # 빈 트리면 새 노드가 루트
    if not root:
        return TreeNode(val)
    
    current = root
    while True:
        if val < current.val:
            # 왼쪽으로 이동
            if current.left is None:
                # 빈 자리 발견 → 삽입
                current.left = TreeNode(val)
                break
            current = current.left
        else:
            # 오른쪽으로 이동
            if current.right is None:
                # 빈 자리 발견 → 삽입
                current.right = TreeNode(val)
                break
            current = current.right
    
    return root

BST 검색

BST의 정렬 속성을 활용하여 효율적으로 검색합니다:

def search_bst(root, val):
    # 기저 조건 1: 노드가 없으면 찾지 못함
    if not root:
        return None
    
    # 기저 조건 2: 찾았음!
    if root.val == val:
        return root
    
    # BST 규칙 활용: 왼쪽 < 부모 < 오른쪽
    if val < root.val:
        # val이 현재 노드보다 작으면 왼쪽 서브트리에만 있을 수 있음
        # 오른쪽은 확인할 필요 없음 (모두 현재 노드보다 큼)
        return search_bst(root.left, val)
    else:
        # val이 현재 노드보다 크면 오른쪽 서브트리에만 있을 수 있음
        return search_bst(root.right, val)

# 트리 구조:
#        5
#       / \
#      3   7
#     / \ / \
#    2  4 6  8

# 검색 과정 (val=6 찾기):
# 1. root(5): 6 > 5 → 오른쪽으로 (왼쪽은 무시)
# 2. node(7): 6 < 7 → 왼쪽으로 (오른쪽은 무시)
# 3. node(6): 6 == 6 → 찾음!
#
# 총 3번 비교 (트리 높이만큼)
#
# 시간복잡도:
# - 평균: O(log n) - 균형 트리일 때 (매번 절반씩 제거)
# - 최악: O(n) - 한쪽으로 치우친 트리일 때
#   예: 1→2→3→4→5 (연결 리스트와 동일)

# 일반 배열 검색과 비교:
# 배열 (정렬 안 됨): O(n) - 모든 요소 확인 필요
# 배열 (정렬됨): O(log n) - 이진 탐색 가능
# BST: O(log n) - 삽입/삭제도 O(log n)으로 유지

반복문 구현:

def search_bst_iterative(root, val):
    current = root
    
    while current:
        if current.val == val:
            # 찾았음!
            return current
        elif val < current.val:
            # 왼쪽으로 이동
            current = current.left
        else:
            # 오른쪽으로 이동
            current = current.right
    
    # 찾지 못함
    return None

# 반복문이 재귀보다 메모리 효율적
# (함수 호출 스택 오버헤드 없음)

BST의 장점:

# 정렬된 데이터 유지
# 중위 순회 시 자동으로 오름차순
def get_sorted(root):
    return inorder(root)  # O(n)

# 최소/최대값 찾기
def find_min(root):
    # 가장 왼쪽 노드가 최소값
    while root.left:
        root = root.left
    return root.val

def find_max(root):
    # 가장 오른쪽 노드가 최대값
    while root.right:
        root = root.right
    return root.val

4. 실전 문제

문제 1: 트리 높이

def max_depth(root):
    """
    트리의 최대 깊이
    """
    if not root:
        return 0
    
    left_depth = max_depth(root.left)
    right_depth = max_depth(root.right)
    
    return max(left_depth, right_depth) + 1

# 테스트
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
print(max_depth(root))  # 3

문제 2: 대칭 트리

def is_symmetric(root):
    """
    트리가 좌우 대칭인지 확인
    """
    def is_mirror(left, right):
        if not left and not right:
            return True
        if not left or not right:
            return False
        
        return (left.val == right.val and
                is_mirror(left.left, right.right) and
                is_mirror(left.right, right.left))
    
    return is_mirror(root.left, root.right) if root else True

# 테스트
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(2)
root.left.left = TreeNode(3)
root.right.right = TreeNode(3)
print(is_symmetric(root))  # True

문제 3: 최소 공통 조상 (LCA)

def lowest_common_ancestor(root, p, q):
    """
    두 노드의 최소 공통 조상 (BST)
    """
    if not root:
        return None
    
    # 둘 다 왼쪽
    if p.val < root.val and q.val < root.val:
        return lowest_common_ancestor(root.left, p, q)
    
    # 둘 다 오른쪽
    if p.val > root.val and q.val > root.val:
        return lowest_common_ancestor(root.right, p, q)
    
    # 갈라지는 지점 = LCA
    return root

실전 팁

트리 문제 접근법

# 1. 재귀 생각
# 대부분 트리 문제는 재귀로 풀림

# 2. Base Case 명확히
# if not root: return ...

# 3. 순회 방법 선택
# 전위: 부모 먼저 처리
# 중위: BST 정렬
# 후위: 자식 먼저 처리
# 레벨: 최단 경로

정리

핵심 요약

  1. 트리: 계층 구조, 루트-자식 관계
  2. 순회: 전위, 중위, 후위, 레벨
  3. BST: 왼쪽 < 부모 < 오른쪽, O(log n) 검색
  4. 재귀: 대부분 재귀로 해결

추천 문제

백준:

프로그래머스:

LeetCode:

관련 글