[자료구조 10] 트리와 용어

지금까지 다룬 리스트나 집합은 값을 한 줄로 늘어놓거나 한 자루에 담는 평평한 구조였습니다. 트리(tree, 나무)는 다릅니다. 위에서 아래로 가지가 뻗듯이 값들이 계층을 이루는 구조입니다. 컴퓨터의 폴더 안에 폴더가 들어 있는 모습, 회사의 조직도, 가족의 가계도가 모두 트리입니다. 이번 편에서는 트리에서 쓰는 용어를 익히고, 파이썬 딕셔너리로 트리를 간단히 표현해 높이와 끝 개수를 재 보겠습니다.

왜 굳이 트리라는 구조가 필요할까요. 리스트는 값을 한 줄로만 늘어놓기 때문에 "누구 밑에 누가 있다"는 관계를 담지 못합니다. 폴더 안의 폴더, 부서 안의 부서처럼 무언가가 다른 것을 품는 관계는 계층으로만 표현됩니다. 트리는 바로 이 "품고 품기는" 관계를 자연스럽게 담아내는 그릇이라, 파일 시스템, 메뉴 구조, 웹 페이지의 화면 구성 등 우리 주변 프로그램 곳곳에 숨어 있습니다.

10.1 트리 용어부터 익힙니다

트리를 이루는 값 하나하나를 노드(node, 마디)라고 부릅니다. 노드들 사이의 관계에 이름이 붙어 있는데, 처음에는 낯설지만 가족 관계에 빗대면 쉽습니다.

맨 위에 있는 단 하나의 시작 노드를 루트(root, 뿌리)라고 합니다. 나무를 거꾸로 세운 모양이라 뿌리가 위에 있다고 생각하면 됩니다. 어떤 노드 바로 아래에 매달린 노드는 그 노드의 자식(child)이고, 반대로 위쪽 노드는 부모(parent)입니다. 그리고 더 이상 자식이 없는 맨 끝 노드를 리프(leaf, 잎)라고 합니다. 조직도로 치면 루트는 회사, 그 아래는 팀, 맨 끝의 잎은 실제 사원이 되는 셈입니다.

같은 부모를 둔 노드끼리는 형제(sibling)라고 부릅니다. 또 어떤 노드와 그 아래에 매달린 모든 노드를 통틀어 서브트리(subtree, 부분 나무)라고 하는데, 트리 안에는 작은 트리들이 겹겹이 들어 있는 셈입니다. 이 점이 중요합니다. 트리의 한 부분도 그 자체로 또 하나의 트리라서, 트리를 다룰 때는 "전체를 자식들의 서브트리로 나눠 똑같이 처리"하는 방식이 자연스럽게 나옵니다. 마지막으로 루트에서 어떤 노드까지 내려온 층수를 그 노드의 깊이(depth)라고 합니다. 루트의 깊이는 0, 그 자식은 1, 이런 식입니다.

10.2 딕셔너리로 조직도 만들기

파이썬에는 트리 전용 자료형이 따로 없지만, 딕셔너리로 쉽게 표현할 수 있습니다. 각 노드를 "값"과 "자식 목록"을 가진 딕셔너리로 만들고, 자식 목록 안에 다시 같은 모양의 딕셔너리를 넣으면 계층이 만들어집니다.

tree = {

"value": "회사",

"children": [

{"value": "개발팀", "children": [

{"value": "홍길동", "children": []},

{"value": "김철수", "children": []}]},

{"value": "영업팀", "children": [

{"value": "이영희", "children": []}]},

]

}

def show(node, depth=0):

print(" " * depth + node["value"])

for ch in node["children"]:

show(ch, depth + 1)

show(tree)

회사

개발팀

홍길동

김철수

영업팀

이영희

show 함수는 노드의 값을 깊이만큼 들여쓰기해서 출력한 뒤, 그 노드의 자식들에 대해 자기 자신을 다시 부릅니다. 이렇게 함수가 자신을 부르는 방식을 재귀(recursion)라고 합니다. 자식을 처리하는 일이 부모를 처리하는 일과 똑같은 모양이기 때문에, 재귀는 트리와 매우 잘 어울립니다. 실행 순서를 따라가 보면, show(tree)가 먼저 "회사"를 출력하고, 자식인 개발팀으로 show를 다시 부릅니다. 개발팀 안에서 홍길동과 김철수를 출력한 뒤 되돌아 나와 영업팀으로 들어가 이영희를 출력합니다. 이렇게 한 가지를 끝까지 파고들었다가 되돌아 나오는 흐름이 반복되며 트리 전체가 빠짐없이 출력됩니다. 깊이가 한 층 깊어질 때마다 공백 두 칸씩 더 들여써서 계층이 눈에 보입니다. 노드가 n개라면 전체를 한 번씩 훑으므로 순회 비용은 O(n)입니다.

10.3 트리의 높이 재기

트리가 몇 층으로 쌓여 있는지를 높이(height)라고 합니다. 높이도 재귀로 자연스럽게 구할 수 있습니다. 어떤 노드의 높이는 "1 더하기, 자식들 중 가장 높은 것"이라고 정의하면 됩니다.

def height(node):

if not node["children"]:

return 1

return 1 + max(height(ch) for ch in node["children"])

print(height(tree))

3

자식이 없으면(리프이면) 높이는 자기 자신 한 층이라 1을 돌려줍니다. 자식이 있으면 각 자식의 높이를 구해 그중 가장 큰 값에 1을 더합니다. 회사에서 팀으로, 팀에서 사원으로 내려가니 세 층이라 결과가 3으로 나왔습니다. if로 리프인지 먼저 확인하고, 그렇지 않을 때만 자식을 파고드는 것이 재귀를 안전하게 멈추는 핵심입니다. 모든 노드를 한 번씩 보므로 O(n)입니다.

10.4 리프 개수 세기

조직도에서 실제 사원 수, 즉 자식이 없는 끝 노드가 몇 개인지 세어 보겠습니다. 이것도 높이와 거의 같은 모양의 재귀입니다.

def leaves(node):

if not node["children"]:

return 1

return sum(leaves(ch) for ch in node["children"])

print(leaves(tree))

3

자식이 없으면 자기 자신이 리프 하나이므로 1을 돌려줍니다. 자식이 있으면 각 자식이 품은 리프 수를 모두 더합니다. 홍길동, 김철수, 이영희 세 명이 리프라서 결과가 3입니다. 높이는 max로 가장 깊은 가지를 골랐고, 리프 개수는 sum으로 모든 가지를 합쳤다는 점만 다릅니다. 같은 재귀 틀에서 max를 쓰느냐 sum을 쓰느냐로 답이 달라지는 것이 흥미롭습니다. 트리를 다루는 대부분의 문제가 이처럼 "리프이면 이렇게, 아니면 자식들의 결과를 모아서"라는 두 갈래 재귀로 풀린다는 점을 눈여겨보시기 바랍니다.

10.5 정리

트리는 루트에서 시작해 자식으로 뻗어 나가고, 자식이 없는 끝을 리프라고 부르는 계층 구조입니다. 파이썬에서는 "값"과 "자식 목록"을 가진 딕셔너리로 트리를 표현할 수 있고, 자식을 처리하는 일이 부모를 처리하는 일과 같은 모양이라 재귀로 다루기 좋습니다. 출력, 높이 재기, 리프 세기 모두 같은 재귀 틀에서 조금씩만 바꾸면 됩니다. 오늘 만든 조직도를 직접 쳐 보고, 사원을 몇 명 더 넣었을 때 높이와 리프 수가 어떻게 달라지는지 손으로 확인해 보시기 바랍니다.