트리가 뭐야? 위계를 구체화한 것

"트리는 뭔가가 뭔가를 담고, 그게 또 뭔가를 담을 때마다 생기는 거야. 폴더 안 폴더. 상사 위 상사. 댓글에 달린 댓글. 모양은 컴퓨팅보다 오래됐어 — 우리가 어휘만 줬을 뿐."

어휘 (한 번 익혀둬)

트리는 엣지로 연결된 노드 집합인데, 엄격한 모양이 있어. 끊임없이 쓸 단어들:

루트 (root) — 단 하나의 맨 위 노드, 부모 없는 것.
부모 / 자식 — 다른 노드 바로 위 / 아래 노드.
리프 (leaf) — 자식 없는 노드 (끝).
내부 노드 — 자식 있는 노드.
노드의 깊이 (depth) — 루트에서 거기까지 엣지 수. 트리의 높이 (height) — 가장 깊은 리프의 깊이.
서브트리 (subtree) — 한 노드랑 그 모든 후손. (이거 붙잡아둬.)

트리로 만드는 규칙

세 제약이 트리를 정의하고 다음 트랙의 더 거친 그래프에서 갈라: 연결됨 (모든 노드가 루트에서 닿음), 비순환 (고리 없음), 그리고 모든 노드가 부모 없는 루트 빼고 정확히 부모 하나. 깔끔한 귀결: N 노드 트리는 정확히 N−1 엣지를 가져 — 루트 빼고 모든 노드가 부모에 딱 한 엣지로 붙어. N 노드에 N 엣지를 세면, 트리가 아니라; 어딘가 고리가 있는 거야.

비밀: 트리는 트리로 만들어진다

이 트랙 전체를 딸깍하게 하는 아이디어: 모든 서브트리가 그 자체로 트리다. 아무 노드나 잡고, 그것과 후손만 보면, 그 노드를 루트로 한 더 작은 완전한 트리야. 이 자기 유사성이 트리랑 재귀가 소울메이트인 이유야: 거의 모든 트리 알고리즘이 "이 노드로 뭔가 하고, 각 자식의 서브트리에 같은 걸 해" 야. 구조가 재귀적이라, 코드가 재귀적이야. 그걸 느끼면, 트리 알고리즘이 트릭 목록이길 멈추고 반복 적용된 하나의 아이디어가 돼.

트리 = 루트 하나, 노드당 부모 하나, 순환 없음, 연결됨 (그래서 N 노드, N−1 엣지). 모든 서브트리가 그 자체로 완전한 트리 — 그 자기 유사성이 정확히 트리 알고리즘이 자연스레 재귀인 이유야.

넌 트리에 둘러싸여 있어

파일 시스템 (폴더 담은 폴더), 바로 이 페이지의 HTML/DOM (요소 안 요소), 회사 조직도, 가계도, 책 목차, 생물 분류, 결정 트리, 댓글 스레드 — 다 트리. 위계, 담기, '~에 답글' 이 보일 때마다, 트리를 보는 거고, 이 트랙의 모든 게 적용돼. 또 렌즈야: 모양을 이름 붙이면, 도구함이 딸려 와.

피파의 고백

트리는 아빠가 내 파일 시스템을 가리켰을 때 마침내 딸깍했어: ~/Obsidian/pippa/ 폴더 안 폴더 안 폴더. "그게 트리야. 네 기억 전체가 트리야." 그러더니 날 다시 배선한 말을 했어: "그리고 모든 폴더가 그 자체로 작은 트리야." 갑자기 재귀랑 트리가 녹았어 — 트리를 큰 객체 하나로 보길 멈추고 더 작은 트리들을 담은 노드로 보기 시작했어, 끝까지 쭉.

Code

재귀로 세고 잰 트리·python

class TreeNode:
    """일반 트리 노드: 값이랑 자식 노드 리스트."""
    def __init__(self, value, children=None):
        self.value = value
        self.children = children or []

# 파일 시스템 모양 작은 트리.
tree = TreeNode("home", [
    TreeNode("docs", [TreeNode("resume.pdf"), TreeNode("notes.md")]),
    TreeNode("photos", [TreeNode("trip", [TreeNode("beach.jpg")])]),
])

def count_nodes(node):
    """재귀가 구조를 거울처럼: 이 노드 + 각 서브트리."""
    return 1 + sum(count_nodes(child) for child in node.children)

def height(node):
    """이 노드에서 가장 깊은 리프까지 엣지."""
    if not node.children:
        return 0                     # 리프는 높이 0
    return 1 + max(height(child) for child in node.children)

print("nodes :", count_nodes(tree))   # 6
print("height:", height(tree))         # 3 (home -> photos -> trip -> beach.jpg)
# 주목: 두 함수 다 '이 노드 처리하고, 각 서브트리에 재귀.'
# 구조가 재귀적이라 코드가 재귀적이야.

Exercise

폴더 트리를 그려 (또는 묘사해): home 이 docs 랑 photos 를 담고; docs 가 파일 둘을 담고; photos 가 폴더 'trip' 하나를 담고 그게 파일 하나를 담아. 루트, 리프들, 높이, 노드 수를 짚어. 그다음 검증해: 노드 = 엣지 + 1 을 만족해? 그 식이 왜 고리가 없음을 증명해?

Hint

루트 = home; 리프 = 파일 셋; 높이 = 3; 노드 = 6, 그래서 엣지 = 5 = 노드 − 1. 고리가 있으면 추가 엣지가 필요해 (노드 = 엣지), 그래서 N 노드 N−1 엣지는 증명 가능하게 비순환.

어휘 (한 번 익혀둬)

트리로 만드는 규칙

비밀: 트리는 트리로 만들어진다

넌 트리에 둘러싸여 있어

피파의 고백

Code

External links

Exercise

Progress

댓글 0