완전이진트리와 배열 매핑 구조 심층 분석

 

자료구조를 학습하다 보면 가장 기본적이면서도 중요한 주제 중 하나가 바로 완전이진트리와 배열 간의 매핑 구조입니다. 완전이진트리는 효율적인 메모리 저장과 빠른 탐색이 가능하다는 장점을 가지고 있으며, 배열은 이러한 특성을 가장 잘 반영할 수 있는 선형 자료구조입니다.

 

이 글에서는 완전이진트리와 배열이 어떤 규칙으로 서로 연결되는지, 자바에서 이 관계를 어떻게 구현할 수 있는지, 그리고 실제 응용 사례까지 심층적으로 분석하겠습니다.

 

완전이진트리와 배열의 인덱스 매핑 규칙

완전이진트리를 배열로 표현할 수 있는 핵심은 바로 "인덱스 규칙"입니다. 루트 노드를 배열의 첫 번째 요소(인덱스 0)에 배치하면, 그 이후 모든 노드는 일정한 수식으로 부모와 자식 관계를 정의할 수 있습니다.

• 부모 노드 인덱스: (i - 1) / 2
• 왼쪽 자식 인덱스: 2i + 1
• 오른쪽 자식 인덱스: 2i + 2

예를 들어 배열이 [10, 20, 30, 40, 50]일 때, 인덱스 0에 위치한 10은 루트 노드이고, 인덱스 1의 20은 루트의 왼쪽 자식, 인덱스 2의 30은 오른쪽 자식이 됩니다.

 

인덱스 3의 40은 20의 왼쪽 자식, 인덱스 4의 50은 20의 오른쪽 자식이 됩니다. 이처럼 수식만 알면 배열과 트리 간의 매핑은 매우 직관적이고 빠르게 이루어집니다.

자바에서의 배열 기반 완전이진트리 구현

자바에서는 배열(Array)과 ArrayList를 활용해 완전이진트리를 쉽게 표현할 수 있습니다. 배열을 사용하면 인덱스 계산을 직접 수행해야 하지만, ArrayList를 사용하면 크기 조정의 유연함까지 확보할 수 있습니다.

import java.util.ArrayList;

class CompleteBinaryTree {
    private ArrayList<Integer> tree = new ArrayList<>();

    public void add(int value) {
        tree.add(value);
    }

    public int getLeftChild(int index) {
        int leftIndex = 2 * index + 1;
        return leftIndex < tree.size() ? tree.get(leftIndex) : -1;
    }

    public int getRightChild(int index) {
        int rightIndex = 2 * index + 2;
        return rightIndex < tree.size() ? tree.get(rightIndex) : -1;
    }

    public int getParent(int index) {
        int parentIndex = (index - 1) / 2;
        return index > 0 ? tree.get(parentIndex) : -1;
    }
}

 

이 코드를 통해 ArrayList를 기반으로 한 완전이진트리 구현을 단순화할 수 있습니다. 삽입은 add() 메서드로 처리되고, 부모-자식 관계는 인덱스 계산으로 즉시 접근 가능합니다.

 

이러한 구조 덕분에 힙(Heap)이나 우선순위 큐와 같은 자료구조를 효율적으로 구현할 수 있습니다.

응용: 힙과 우선순위 큐에서의 활용

완전이진트리와 배열 매핑 구조는 단순히 트리를 표현하는 데 그치지 않습니다. 실제로 많이 쓰이는 자료구조인 힙(Heap)이 바로 이 규칙을 기반으로 구현됩니다.

힙은 항상 완전이진트리의 형태를 유지하면서, 특정 규칙(최대 힙: 부모가 자식보다 크거나 같음, 최소 힙: 부모가 자식보다 작거나 같음)을 만족합니다. 배열 기반으로 구현된 힙은 삽입과 삭제 연산에서 O(log n)의 시간 복잡도를 가지며, 이는 인덱스 계산 덕분에 가능한 일입니다.

예를 들어, 우선순위 큐를 구현할 때 힙을 사용하면 항상 가장 높은 우선순위를 가진 요소를 빠르게 꺼낼 수 있습니다. 이는 단순 연결리스트 기반 구현보다 훨씬 효율적이며, 데이터 개수가 많아질수록 그 차이는 커집니다. 따라서 완전이진트리와 배열 매핑 구조를 이해하는 것은 곧 고성능 알고리즘과 자료구조 설계의 기초를 다지는 일과 같습니다.

 

 

완전이진트리와 배열 매핑 구조는 단순한 자료구조 개념을 넘어 실제 응용에서 중요한 역할을 합니다. 배열의 인덱스 규칙은 트리 구조를 메모리에 선형적으로 표현할 수 있게 하며, 자바에서는 이를 ArrayList를 통해 더욱 직관적으로 다룰 수 있습니다. 또한 이러한 원리는 힙과 우선순위 큐 같은 고급 자료구조로 확장되어 실무에서 널리 사용됩니다.

 

초보 개발자라면 단순한 이론 이해에 그치지 말고, 직접 배열과 ArrayList로 트리를 구현해 보면서 그 동작 원리를 체득하는 것을 권장합니다.