트리와 이진트리의 구조

폴더나 조직의 위계를 따라갈 때 하나의 부모 경로가 있다는 성질은 이동을 단순하게 만듭니다. 그래프의 연결과 사이클을 바탕으로 트리의 정의를 익힙니다.

트리는 연결된 비순환 무방향 그래프

유한 트리는 서로 다른 정점 사이의 단순경로가 정확히 하나입니다. 연결되어서 적어도 하나의 경로가 있고, 두 개의 서로 다른 단순경로가 있다면 그 사이에서 사이클을 만들 수 있기 때문입니다. 정점 n개인 트리는 n−1개 간선을 가집니다. 연결이 빠진 비순환 그래프는 숲이며, 연결 성분이 k개이면 간선 수는 n−k입니다.

루트는 위계를 읽기 위해 선택한 정점입니다. 무방향 트리 자체에 원래부터 특별한 루트가 꼭 있어야 하는 것은 아닙니다. 루트를 정하면 부모·자식·조상·자손이 정해집니다. 자식이 없는 정점은 잎입니다. 깊이는 루트에서의 간선 수, 높이는 그 정점에서 가장 먼 아래 잎까지의 간선 수입니다. 이 교재는 루트 깊이 0, 잎 높이 0을 사용합니다.

이진트리에는 좌우 구분이 있다

각 정점에 왼쪽·오른쪽 자식이 각각 최대 하나인 트리가 이진트리입니다. 자식이 하나일 때도 왼쪽인지 오른쪽인지 구분합니다. 엄격 이진트리는 모든 정점의 자식 수가 0 또는 2입니다. 포화 이진트리는 모든 층이 꽉 찬 트리입니다. 완전 이진트리는 마지막 층을 제외하고 꽉 차며 마지막 층이 왼쪽부터 채워진 트리입니다. 이 이름들은 자료마다 번역이 다를 수 있어 실제 조건을 함께 적습니다.

루트 8, 그 자식 3·10, 3의 자식 1·6인 이진트리는 마지막 층이 왼쪽부터 채워져 완전이지만 모든 잎 깊이가 같지는 않아 포화가 아닙니다. 높이는 2이며 깊이별 정점 수는 1,2,2입니다.

깊이 d의 정점 수는 최대 2ᵈ입니다. 높이 h의 정점 수는 최대 $1+2+\cdots+2^h=2^{h+1}-1$입니다. 최댓값은 모든 층을 꽉 채웠을 때이며 아무 이진트리의 실제 개수를 뜻하지 않습니다. 한쪽으로 늘어지는 n정점 트리는 높이가 n−1이 될 수 있습니다.

배열과 연결 표현

완전 이진트리를 1번부터 층 순서로 배열에 넣으면 정점 i의 왼쪽 자식은 2i, 오른쪽은 2i+1, 부모는 $\lfloor i/2\rfloor$입니다. 존재하는 자식에만 적용합니다. 편향 트리는 빈 배열 칸이 많이 생기므로 연결 참조가 더 적합할 수 있습니다. 배열표현이 모든 트리에 항상 효율적인 것은 아닙니다.

스스로 풀어보기

문제 1. 높이 3인 포화 이진트리의 정점·잎·간선 수를 구하세요.

풀이: 정점은 2⁴−1=15, 잎은 마지막 층 2³=8, 간선은 15−1=14입니다. 높이를 층 수 4와 혼동하면 한 단계 큰 값을 계산하게 됩니다.

문제 2. 정점 7개·간선 6개인 무방향 그래프는 반드시 트리인가요?

힌트: 연결 여부를 확인해야 합니다.

풀이: 아닙니다. 삼각형 두 개와 고립 정점 하나를 두면 정점 7·간선 6이지만 비연결이고 사이클도 있습니다. 간선 수만으로 트리라고 판정할 수 없습니다. 연결 조건을 함께 알면 n−1 간선의 단순 무방향 그래프는 트리입니다.

개수 공식보다 먼저 높이의 약속을 확인하세요. 처리 순서와 수식 표현은 트리 순회에서 이어집니다.