데이터 구조에서 이진 트리를 표현하는 방법: 배열과 연결 리스트

이번 글에서는 이진 트리(binary tree)를 컴퓨터 메모리에 어떻게 표현하는지 살펴보겠습니다. 이진 트리를 표현하는 대표적인 방법은 두 가지가 있습니다. 바로 배열(Array)을 이용하는 방법과 연결 리스트(Linked List)를 이용하는 방법입니다.

1. 배열을 이용한 표현

먼저 다음과 같은 트리가 있다고 가정해 보겠습니다.

배열 표현 방식은 트리의 요소들을 레벨 순서(level order), 즉 위에서 아래로, 같은 레벨에서는 왼쪽에서 오른쪽으로 차례대로 탐색하면서 데이터를 저장합니다. 따라서 노드들이 레벨별로 순서대로 배열에 담기며, 존재하지 않는 노드가 있는 경우 해당 위치는 빈칸으로 남겨둡니다. 위 트리를 배열로 표현하면 다음과 같습니다.

인덱스 1에는 루트(root) 노드인 10이 저장되어 있으며, 루트의 두 자식 노드인 5와 16은 각각 인덱스 2와 3에 배치됩니다. 자식 노드가 존재하지 않는 위치는 그대로 빈칸으로 처리됩니다.

부모와 자식 인덱스 계산 공식

배열 표현에서는 다음 공식을 사용하면 특정 노드의 두 자식 위치를 손쉽게 구할 수 있습니다.

$$child_{1}=2*parent$$ 

$$child_{2}=\lgroup2*parent\rgroup+1$$

반대로 자식 인덱스로부터 부모 인덱스를 구할 때는 다음 공식을 따릅니다.

$$parent=\begin{bmatrix}\frac{child}{2} \end{bmatrix}$$

이 방식은 부모와 자식의 인덱스를 계산으로 바로 찾을 수 있다는 점에서 매우 편리합니다. 하지만 실제로 사용되지 않는 빈 공간이 많이 생겨 메모리 효율성은 떨어지는 단점이 있습니다. 따라서 배열 표현은 모든 레벨이 가득 찬 완전 이진 트리(complete binary tree)나 포화 이진 트리(full binary tree)를 저장할 때 가장 적합합니다.

2. 연결 리스트를 이용한 표현

두 번째 방법은 연결 리스트를 활용하는 것입니다. 이 방식에서는 트리의 각 요소마다 하나의 노드(node)를 생성하고, 노드들을 포인터로 서로 연결하여 트리 구조를 만듭니다. 각 노드는 데이터와 함께 왼쪽 자식, 오른쪽 자식을 가리키는 포인터를 가지므로, 빈 공간 낭비 없이 필요한 만큼만 메모리를 사용할 수 있습니다. 연결 리스트로 표현된 트리의 구조는 아래와 같습니다.