Ch.6 트리 기초

트리란? — 폴더, 가계도, DOM

트리 자료구조의 정의와 핵심 용어(루트, 노드, 간선, 리프)를 이해한다폴더 구조, 가계도, HTML DOM이 모두 트리임을 인식한다

컴퓨터 안의 모든 것이 트리다

폴더 안에 폴더, 그 안에 파일 — 이 구조를 매일 사용하면서도 이것이 트리라는 사실을 모르는 개발자가 많습니다.

배열과 연결 리스트는 '한 줄'인데, 트리는 왜 '가지'가 필요한가?

계층적 관계를 표현해야 할 때 트리가 유일한 해답입니다. 면접에서도 가장 자주 출제됩니다.

lightbulb

핵심 개념

트리(Tree)

노드와 간선으로 이루어진 계층적 비순환 자료구조

루트(Root)

트리의 최상위 노드. 부모가 없다

리프(Leaf)

자식이 없는 말단 노드

article

핵심 내용

지금 이 파일을 열기까지 몇 개의 폴더를 거쳤나요?

C:\Users\폴더 구조 — 이것이 트리입니다. 루트 드라이브 아래 폴더(노드)가 가지를 뻗고, 파일(리프)이 끝에 달려 있죠

트리의 핵심 규칙: 사이클이 없다. 어떤 노드에서 출발해도 자기 자신으로 돌아오는 경로가 없습니다

가계도를 떠올려 보세요. 조부모 → 부모 → 자녀 이것도 트리입니다

웹 브라우저도 HTML을 DOM 트리로 파싱합니다. `<html>` 루트 아래 `<head>`와 `<body>`가 자식 노드죠

트리가 쓰이는 곳 • 파일 시스템 — 폴더/파일 계층 • HTML DOM — 웹 페이지 구조 • 조직도 — 상하 관계 • 데이터베이스 인덱스 — B-Tree

배열은 순서, 해시맵은 검색, 트리는 계층. 각 자료구조는 고유한 강점이 있습니다

면접에서 트리 문제를 풀려면 용어를 정확히 알아야 합니다

부모(Parent) — 바로 위 노드 자식(Child) — 바로 아래 노드 형제(Sibling) — 같은 부모의 자식들 깊이(Depth) — 루트에서 해당 노드까지 간선 수 높이(Height) — 해당 노드에서 가장 깊은 리프까지 간선 수 서브트리(Subtree) — 특정 노드를 루트로 하는 부분 트리

이진 트리(Binary Tree)란 각 노드의 자식이 최대 2개인 트리입니다. 면접 트리 문제의 90%가 이진 트리입니다

이진 트리의 노드는 놀라울 정도로 간단합니다

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left    # 왼쪽 자식
        self.right = right  # 오른쪽 자식

# 트리 만들기
#       1
#      / \
#     2   3
#    / \
#   4   5

root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)

print(root.val)        # 1 (루트)
print(root.left.val)   # 2
print(root.right.val)  # 3

TreeNode 클래스 하나로 어떤 이진 트리든 만들 수 있습니다. 이 구조를 외워두세요 — 면접 첫 줄에 씁니다

트리의 연산 성능은 높이(h)에 달려있습니다

완전 이진 트리 — 높이 h일 때 노드 수: 2^(h+1) - 1 • 높이 3 → 최대 15개 노드 • 높이 10 → 최대 2,047개 노드 • 높이 20 → 최대 약 200만 개 노드

균형 잡힌 트리에서 탐색은 O(log n). 하지만 한쪽으로 치우치면 O(n)이 됩니다. 이 차이가 면접의 핵심 포인트입니다

이진 트리에서 각 노드가 가질 수 있는 최대 자식 수는?

트리에는 사이클(순환)이 존재할 수 있다

리프(Leaf) 노드란 어떤 노드를 의미하는가?

key

핵심 용어

🌳

트리(Tree)

노드와 간선으로 이루어진 계층적 비순환 자료구조

👑

루트(Root)

최상위 노드 — 부모가 없다

🍃

리프(Leaf)

자식이 없는 말단 노드

📏

높이(Height)

루트에서 가장 깊은 리프까지의 간선 수

edit_note

정리 노트

트리란? — 폴더, 가계도, DOM

핵심 용어

트리: 노드 + 간선, 비순환 계층 구조
이진 트리: 자식 최대 2개인 트리
높이: 루트→가장 깊은 리프까지 간선 수

트리 노드 (Python)

TreeNode: val, left, right 세 필드
성능: 균형: O(log n), 편향: O(n)

image

시각 자료

다이어그램: ds-d42

다이어그램: ds-d43

퀴즈와 인터랙션으로 더 깊이 학습하세요

play_circle인터랙티브 레슨 시작