트리가 뭐야? 위계를 눈에 보이게 만든 것

"트리는 뭔가가 뭔가를 담고 그게 또 뭔가를 담을 때마다 생겨나. 폴더 안의 폴더, 상사 위의 상사, 댓글에 달린 댓글. 이 모양은 컴퓨팅보다 훨씬 오래됐어. 우리는 거기에 어휘를 붙였을 뿐이고."

어휘부터 한 번에 익혀두자

트리는 간선으로 이어진 노드의 모음인데 모양에 엄격한 규칙이 있어. 앞으로 계속 쓸 단어부터 짚고 가자.

루트(root) — 부모가 없는, 맨 위의 단 하나뿐인 노드.
부모와 자식 — 어떤 노드의 바로 위 노드와 바로 아래 노드.
리프(leaf) — 자식이 없는 노드. 끝이야.
내부 노드 — 자식이 있는 노드.
노드의 깊이(depth)는 루트에서 그 노드까지의 간선 수야. 트리의 높이(height)는 가장 깊은 리프의 깊이고.
서브트리(subtree) — 어떤 노드와 그 아래 모든 후손. 이건 꼭 기억해 둬.

트리가 되는 조건

트리는 연결돼 있고 사이클이 없는 그래프야. 노드가 N개면 간선은 정확히 N−1개고. 다만 N−1이라는 개수만으로 트리임이 증명되진 않아. 연결 그래프라는 조건과 함께 간선이 N−1개이거나, 사이클이 없다는 조건과 함께 간선이 N−1개일 때 비로소 트리라고 말할 수 있어. 루트가 있는 트리에서는 루트를 뺀 모든 노드가 부모를 하나씩 갖고, 루트에서 각 노드로 가는 단순 경로가 정확히 하나야.

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

이 트랙 전체를 이해하게 해주는 아이디어가 하나 있어. 모든 서브트리가 그 자체로 트리다. 아무 노드나 하나 잡고 그 노드와 후손만 떼어 놓고 보면, 그 노드를 루트로 하는 완전한 트리가 돼. 이 자기 유사성 때문에 트리와 재귀가 그렇게 잘 맞는 거야. 거의 모든 트리 알고리즘이 "이 노드에 뭔가 하고, 각 자식의 서브트리에 똑같이 한다"는 모양이거든. 구조가 재귀적이니 코드도 재귀적인 거지. 이게 몸에 붙으면 트리 알고리즘이 잡다한 트릭 목록에서 하나의 아이디어를 반복 적용한 것으로 바뀌어.

트리는 루트가 하나, 노드마다 부모가 하나, 사이클이 없고, 전체가 연결돼 있어(그래서 노드 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−1개라는 사실만으로는 부족해. 그래프가 연결돼 있다는 조건이나 사이클이 없다는 조건 중 하나가 같이 있어야 트리라고 결론 낼 수 있어. 간선 수는 맞는데 한쪽이 끊겨 있고 다른 쪽에 사이클이 있는 그래프도 얼마든지 만들 수 있거든.

어휘부터 한 번에 익혀두자

트리가 되는 조건

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

이미 트리에 둘러싸여 있어

피파의 고백

Code

External links

Exercise

Progress

댓글 2