thenullpage.com
1. 한 줄이 아니라 갈래로 뻗는 구조
리스트도 스택도 큐도 값을 한 줄로 늘어놓습니다. 그런데 현실의 데이터에는 한 줄로 펴지지 않는 것이 많습니다. 폴더 안에 폴더가 들어 있는 파일 시스템, 회사 조직도, 댓글에 달린 답글이 그렇습니다. 하나가 여러 개를 거느리고 그것이 또 여러 개를 거느립니다. 이런 모양을 담는 자료구조가 트리(tree)입니다.
이름은 나무에서 왔지만 그림은 뒤집혀 있어 맨 위에 뿌리가 있고 아래로 가지가 퍼집니다. 값이 담긴 자리 하나를 노드(node), 노드를 잇는 선을 간선(edge)이라고 합니다. 맨 위 노드는 루트(root), 바로 아래 매달린 노드는 자식, 그 위쪽은 부모입니다. 자식이 하나도 없는 끝자락 노드는 리프(leaf)라고 부릅니다.
규칙은 단순합니다. 부모는 자식을 여럿 둘 수 있지만 자식의 부모는 하나뿐이고, 아래로 내려가다 제자리로 돌아오는 길은 없습니다.
2. 노드를 만들어 트리를 조립합니다
값 하나와 자식 목록을 담는 클래스를 만들면 그것이 곧 노드입니다.
class Node:
def __init__(self, value):
self.value = value
self.children = []
root = Node("문서")
photo = Node("사진")
code = Node("코드")
root.children.append(photo)
root.children.append(code)
photo.children.append(Node("여행.jpg"))
print([c.value for c in root.children])
print(len(code.children))
['사진', '코드']
0
노드마다 자식 목록을 하나씩 들고 있고, 부모의 목록에 자식을 넣는 것으로 간선이 생깁니다. 자식 목록이 빈 code가 리프입니다.
3. 깊이와 높이는 서로 다릅니다
가장 자주 헷갈리는 용어가 깊이와 높이입니다. 깊이(depth)는 루트에서 그 노드까지 내려온 간선 수라 루트의 깊이가 0이고, 높이(height)는 그 노드에서 가장 먼 리프까지 내려가는 간선 수라 리프의 높이가 0입니다. 위에서 세면 깊이, 아래에서 세면 높이입니다. 트리의 높이라고 하면 루트의 높이를 말합니다.
def height(node):
if not node.children:
return 0
return 1 + max(height(c) for c in node.children)
print(height(root))
print(height(photo))
print(height(code))
2
1
0
함수가 자기 자신을 부르고 있습니다. 자식들의 높이를 각각 물어보고 그중 가장 큰 값에 1을 더하면 자기 높이가 나옵니다. 자식이 없으면 더 물어볼 곳이 없으니 0을 돌려주고 멈춥니다. 이 멈춤 조건을 종료 조건이라고 하며, 빠뜨리면 함수가 끝없이 자기를 부르다 RecursionError가 납니다. 노드 하나 아래에 다시 작은 트리가 매달린 구조라 트리 코드는 대체로 이런 재귀 모양이 되며, 이 작은 트리를 서브트리라고 합니다.
4. 자식이 둘뿐인 이진 트리
자식 수에 제한이 없으면 자유롭지만 다루기 번거롭습니다. 그래서 코딩 테스트에서는 자식을 최대 둘까지만 두는 이진 트리(binary tree)를 훨씬 많이 씁니다. 목록 대신 왼쪽과 오른쪽 두 칸을 둡니다.
class BNode:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
root = BNode(1)
root.left = BNode(2)
root.right = BNode(3)
root.left.left = BNode(4)
print(root.left.left.value)
print(root.right.left)
4
None
비어 있는 자리는 None입니다. 이 None을 확인하지 않고 바로 .value를 읽으면 AttributeError가 나므로 트리 코드에서는 노드가 None인지 먼저 묻는 습관이 필요합니다.
같은 개수의 노드라도 모양은 천차만별입니다. 모든 층이 빈틈없이 찬 트리를 포화 트리, 마지막 층만 왼쪽부터 채워진 트리를 완전 트리라고 합니다. 반대로 자식이 한쪽으로만 붙으면 사실상 연결 리스트가 됩니다. 노드가 n개일 때 잘 퍼진 트리의 높이는 대략 log2 n이지만 한쪽으로 늘어진 트리는 n-1이라, 백만 개면 20 대 999999입니다. 트리를 쓰는 자료구조가 빠른 것은 높이가 낮게 유지될 때뿐입니다.
5. 세는 일은 왼쪽과 오른쪽에 물어봅니다
트리에서 무언가를 세는 코드는 형태가 거의 같습니다. 왼쪽에게 묻고, 오른쪽에게 묻고, 자기 몫을 더합니다.
def count(node):
if node is None:
return 0
return 1 + count(node.left) + count(node.right)
def leaves(node):
if node is None:
return 0
if node.left is None and node.right is None:
return 1
return leaves(node.left) + leaves(node.right)
print(count(root))
print(leaves(root))
4
2
두 함수의 뼈대는 하나입니다. None을 만나면 0을 돌려주는 종료 조건, 그리고 양쪽 결과를 합치는 한 줄뿐입니다. 1 대신 node.value를 더하면 값의 합계가 됩니다. 노드를 한 번씩만 방문하므로 O(n)입니다. 다만 부를 때마다 호출 정보가 쌓여서, 늘어진 트리를 재귀로 훑으면 파이썬 기본 한도인 1000단계 근처에서 멈춰 버립니다.
6. 배열 한 줄로 트리를 담는 방법
노드를 만들지 않고 배열 한 줄로 이진 트리를 담을 수도 있습니다. 위에서 아래로, 같은 층에서는 왼쪽부터 번호를 매기고 그 번호를 인덱스로 씁니다.
tree = [1, 2, 3, 4, 5, None, 7]
def left(i):
return 2 * i + 1
def right(i):
return 2 * i + 2
def parent(i):
return (i - 1) // 2
print(tree[left(0)], tree[right(0)])
print(tree[left(1)], tree[right(1)])
print(tree[parent(4)])
2 3
4 5
2
i번 노드의 왼쪽 자식은 2i+1, 오른쪽 자식은 2i+2, 부모는 (i-1)//2 자리입니다. 계산만으로 위아래를 오갈 수 있어 코드가 짧아집니다. 대신 빈 자리도 칸을 차지해 늘어진 트리에서는 낭비가 심하므로 빈틈없이 채워지는 완전 트리에만 쓰며, 우선순위 큐를 만드는 힙이 대표적입니다.
7. 트리를 볼 때 짚어야 할 것
흔한 오해부터 정리하겠습니다. 이진 트리와 이진 탐색 트리는 다릅니다. 이진 트리는 자식이 최대 둘이라는 모양의 제약일 뿐 값이 어떻게 놓이든 상관하지 않습니다. 왼쪽에는 작은 값, 오른쪽에는 큰 값이라는 순서 조건까지 지켜야 이진 탐색 트리입니다. 위에서 만든 트리는 루트가 1인데 왼쪽 자식이 2이니 이진 탐색 트리가 아닙니다.
계층이 있는 데이터를 만나면 트리를 떠올리면 됩니다. 폴더와 파일, 조직도, 카테고리 분류, 답글, HTML 문서가 모두 트리 모양입니다.
챙길 것은 세 가지입니다. 깊이는 위에서 세고 높이는 아래에서 센다는 것, 트리를 다루는 코드는 종료 조건과 양쪽에 묻는 한 줄로 이루어진 재귀 형태라는 것, 그리고 같은 노드 수라도 늘어진 트리의 높이는 n-1까지 커지므로 성능을 따질 때는 노드 수가 아니라 높이를 봐야 한다는 것입니다.