트리와 이진 트리의 구조

컴퓨터의 폴더, 회사의 조직도, 대회의 대진표는 모두 위아래가 있는 갈래 구조입니다. 어느 폴더에서든 맨 위 폴더로 가는 길이 하나뿐이라서, 위치를 경로 하나로 적을 수 있습니다. 이런 구조를 그래프로 나타낸 것이 트리입니다. 이 글에서는 그래프의 모델과 표현의 연결과 사이클로 트리를 정의하고, 트리가 갖는 성질을 증명한 뒤, 컴퓨터에서 자주 쓰는 이진 트리를 다룹니다.

트리는 사이클이 없는 연결 그래프다

사이클이 없는 연결된 무방향 그래프를 트리(tree)라고 합니다. 연결되어 있지 않아도 사이클만 없으면 숲(forest)이라 하며, 숲의 연결 성분 하나하나가 트리입니다. 정의는 짧지만, 트리에는 서로 같은 뜻인 여러 성질이 있습니다.

첫째, 트리에서는 서로 다른 두 정점 사이의 경로가 정확히 하나입니다. 연결되어 있으므로 경로가 적어도 하나 있고, 서로 다른 경로가 두 개 있다면 둘이 처음 갈라지는 정점에서 다시 만나는 정점까지의 두 구간이 사이클을 이루기 때문입니다. 거꾸로 모든 두 정점 사이의 경로가 하나뿐인 그래프는 연결되어 있고, 사이클이 있다면 사이클 위의 두 정점 사이에 경로가 두 개 생기므로 사이클도 없습니다.

둘째, 정점이 n개인 트리의 간선은 n − 1개입니다. 이것을 보이려면 먼저 정점이 2개 이상인 트리에 차수가 1인 정점, 곧 잎(leaf)이 있다는 것을 알아야 합니다. 트리에서 가장 긴 경로를 하나 잡으면 그 끝 정점은 차수가 1입니다. 끝 정점에 경로 밖의 이웃이 있다면 경로를 더 늘릴 수 있고, 경로 안의 다른 정점과 이어져 있다면 사이클이 생기기 때문입니다. 이제 수학적 귀납법을 씁니다. 정점이 1개인 트리는 간선이 0개입니다. 정점이 n개(n ≥ 2)인 트리에서 잎과 그 간선을 지우면 연결되어 있고 사이클이 없는 정점 n − 1개의 트리가 남으므로, 귀납 가정에 따라 간선이 n − 2개이고, 지운 간선을 더하면 n − 1개입니다.

간선 수로 트리를 판정할 수도 있습니다. 정점 n개인 연결 그래프의 간선이 n − 1개이면 트리입니다. 사이클이 있다면 사이클 위의 간선을 하나 지워도 연결이 유지되므로, 사이클이 없어질 때까지 지우면 간선이 n − 1개보다 적은 트리가 남아 앞의 결과와 어긋나기 때문입니다. 같은 이유로 연결 성분이 k개인 숲은 간선이 n − k개입니다.

더 깊이: 이름 붙은 정점 n개로 만드는 트리의 수

정점에 1부터 n까지 서로 다른 이름이 붙어 있을 때 만들 수 있는 트리는 모두 $n^{n-2}$개이며, 이를 케일리 공식(Cayley's formula)이라고 합니다. OEIS의 A000272에 따르면 정점이 2, 3, 4, 5개일 때 1, 3, 16, 125개입니다. 정점이 4개일 때를 세어 보면, 한 정점에 나머지 셋이 모두 붙은 별 모양이 가운데 정점을 고르는 4가지, 네 정점이 한 줄로 이어진 경로가 순서 $4!=24$가지를 양쪽 방향으로 두 번씩 센 12가지라서 합이 16입니다.

이 공식은 트리마다 길이 $n-2$인 수열 하나를 짝지어 주는 프뤼퍼 수열(Prüfer sequence)로 증명합니다. 남은 잎 가운데 이름이 가장 작은 것을 지우면서 그 잎과 이웃한 정점의 이름을 적고, 정점이 두 개 남을 때까지 되풀이하면 수열이 하나 나옵니다. 거꾸로 수열에서 원래의 트리를 하나뿐인 방법으로 되살릴 수 있으므로 트리와 수열이 하나씩 짝을 이루고, 각 자리에 n가지 이름이 올 수 있으니 수열은 $n^{n-2}$개입니다. 이 수열에서 각 정점이 나타나는 횟수는 그 정점의 차수보다 1 작다는 성질도 있어서, 잎은 수열에 한 번도 나오지 않습니다.

루트를 정하면 생기는 말

트리의 정점 하나를 골라 루트(root)로 정하면 위아래가 생깁니다. 루트에서 어떤 정점으로 가는 경로가 하나뿐이므로, 그 경로에서 바로 앞의 정점을 부모(parent), 바로 뒤의 정점을 자식(child)이라 할 수 있습니다. 부모가 같은 정점끼리는 형제(sibling)이고, 루트까지 가는 경로 위의 정점들은 조상(ancestor), 반대로 아래쪽으로 이어진 정점들은 자손(descendant)입니다. 루트를 정한 트리에서는 자식이 없는 정점을 잎이라고 부릅니다.

루트에서 어떤 정점까지의 간선 수를 그 정점의 깊이(depth)라 하고, 어떤 정점에서 그 아래의 가장 먼 잎까지의 간선 수를 높이(height)라고 합니다. 이 교재에서는 루트의 깊이와 잎의 높이를 0으로 셉니다. 정점 수로 세어 루트를 1층으로 부르는 자료도 있으므로, 높이를 비교할 때는 어느 약속인지 먼저 확인해야 합니다. 무방향 트리 자체에는 특별한 루트가 없으며, 루트는 위아래를 읽기 위해 고르는 것입니다.

이진 트리의 종류

모든 정점의 자식이 많아야 둘이고, 각 자식이 왼쪽 자식인지 오른쪽 자식인지 구분되는 루트 있는 트리를 이진 트리(binary tree)라고 합니다. 자식이 하나뿐이어도 그것이 왼쪽인지 오른쪽인지에 따라 서로 다른 이진 트리입니다. 이진 트리에는 모양에 따라 이름이 붙은 종류가 있습니다.

정 이진 트리는 엄격 이진 트리라고도 하며, 이 이름들의 번역은 자료마다 조금씩 다르므로 이름과 함께 조건을 확인하는 것이 안전합니다. 루트 8의 자식이 3과 10이고, 3의 자식이 1과 6인 이진 트리를 보겠습니다.

마지막 층의 1과 6이 왼쪽부터 채워져 있으므로 완전 이진 트리입니다. 모든 정점의 자식이 0개 또는 2개라 정 이진 트리이기도 합니다. 하지만 잎 10은 깊이 1, 잎 1과 6은 깊이 2라 잎의 깊이가 다르므로 포화 이진 트리는 아닙니다. 높이는 2이고, 깊이 0, 1, 2에 있는 정점은 각각 1개, 2개, 2개입니다.

정점 수의 한계

이진 트리에서 깊이 d에 있는 정점은 많아야 $2^d$개입니다. 깊이 0에는 루트 하나뿐이고, 각 정점의 자식이 많아야 둘이므로 한 층 내려갈 때마다 많아야 두 배가 되기 때문입니다. 그래서 높이가 h인 이진 트리의 정점은 많아야 $1+2+\cdots+2^h=2^{h+1}-1$개이고, 이 값은 포화 이진 트리일 때 나옵니다. 거꾸로 말하면 정점 n개를 담은 이진 트리의 높이는 적어도 $\log_2(n+1)-1$입니다. 반대로 모든 정점이 자식을 하나씩만 가지고 한쪽으로 늘어진 트리는 높이가 n − 1까지 커집니다.

정 이진 트리에서는 잎의 수가 내부 정점의 수보다 언제나 하나 많습니다. 내부 정점이 I개, 잎이 L개이면 정점은 I + L개이고 간선은 I + L − 1개입니다. 한편 간선은 내부 정점마다 자식으로 내려가는 두 개씩이라 2I개입니다. 두 식을 같게 놓으면 2I = I + L − 1, 곧 L = I + 1입니다. 예제 트리는 내부 정점이 8과 3의 2개이고 잎이 10, 1, 6의 3개입니다.

배열에 담기

완전 이진 트리는 정점을 층 순서대로 배열에 넣으면 부모와 자식의 위치를 계산으로 찾을 수 있습니다. 루트를 1번 칸에 두면 i번 칸의 왼쪽 자식은 2i번, 오른쪽 자식은 2i + 1번, 부모는 $\lfloor i/2\rfloor$번 칸에 있습니다. 깊이 d의 정점들은 $2^d$번부터 $2^{d+1}-1$번 칸까지 차지하므로, i번 칸의 깊이는 $\lfloor\log_2 i\rfloor$입니다.

tree = [None, 8, 3, 10, 1, 6]
n = len(tree) - 1
for i in range(1, n + 1):
    children = [tree[c] for c in (2 * i, 2 * i + 1) if c <= n]
    parent = tree[i // 2] if i > 1 else None
    print(i, tree[i], "깊이", i.bit_length() - 1, "부모", parent, "자식", children)
print("높이", n.bit_length() - 1)

1 8 깊이 0 부모 None 자식 [3, 10]
2 3 깊이 1 부모 8 자식 [1, 6]
3 10 깊이 1 부모 8 자식 []
4 1 깊이 2 부모 3 자식 []
5 6 깊이 2 부모 3 자식 []
높이 2

0번 칸은 계산을 단순하게 하려고 비워 두었습니다. i.bit_length()는 i를 이진수로 적었을 때의 자릿수이므로, 1을 빼면 $\lfloor\log_2 i\rfloor$와 같습니다. 정점이 n개인 완전 이진 트리의 높이는 마지막 칸 n의 깊이인 $\lfloor\log_2 n\rfloor$입니다. 루트를 0번 칸에 두면 자식이 2i + 1번과 2i + 2번, 부모가 $\lfloor(i-1)/2\rfloor$번으로 바뀌며, 이 방식은 자료구조·알고리즘 교재의 완전 이진 트리·힙·우선순위 큐에서 씁니다.

이 배열 표현은 완전 이진 트리에 잘 맞지만 모든 이진 트리에 효율적이지는 않습니다. 정점 4개가 오른쪽으로만 이어진 트리는 1번, 3번, 7번, 15번 칸을 쓰므로 값 4개를 담는 데 칸 15개가 필요합니다. 이런 트리는 정점마다 왼쪽 자식과 오른쪽 자식을 가리키는 참조를 두는 편이 낫습니다.

정리

• 트리는 사이클이 없는 연결 그래프이고, 두 정점 사이의 경로가 하나뿐입니다. 정점 n개인 트리의 간선은 n − 1개이며, 간선이 n − 1개인 연결 그래프는 트리입니다.
• 연결 성분이 k개인 숲의 간선은 n − k개입니다.
• 루트를 정하면 부모, 자식, 조상, 자손, 잎이 정해집니다. 이 교재는 루트의 깊이와 잎의 높이를 0으로 셉니다.
• 이진 트리는 왼쪽과 오른쪽 자식을 구분하며, 정 이진 트리, 포화 이진 트리, 완전 이진 트리는 조건으로 구분해야 합니다.
• 높이 h인 이진 트리의 정점은 많아야 $2^{h+1}-1$개이고, 정 이진 트리의 잎은 내부 정점보다 하나 많습니다.
• 완전 이진 트리는 배열에 담으면 i번 칸의 자식이 2i, 2i + 1번, 부모가 $\lfloor i/2\rfloor$번입니다.

연습 문제

1. 포화 이진 트리 세기

높이가 3인 포화 이진 트리의 정점, 잎, 간선은 각각 몇 개인가요?

2. 간선 수만으로 판정하기

정점 7개, 간선 6개인 무방향 그래프는 반드시 트리인가요?

3. 정 이진 트리의 잎

잎이 10개인 정 이진 트리의 내부 정점과 전체 정점은 몇 개인가요?

트리 문제에서 개수를 세기 전에 높이와 깊이를 간선으로 세는지 정점으로 세는지부터 확인해 보세요. 다음 글 트리 순회와 수식의 표현에서는 트리의 정점을 빠짐없이 한 번씩 방문하는 여러 순서와, 그 순서로 수식을 읽고 계산하는 방법을 다룹니다.