자료구조 핵심: 배열 인덱스와 트리 노드 관계

 

자료구조를 공부할 때, 배열과 트리의 관계는 반드시 이해해야 하는 중요한 개념입니다. 특히 완전이진트리를 배열로 표현하는 방식은 단순히 저장 방법을 넘어 효율적인 알고리즘 구현의 핵심 원리로 작용합니다. 배열 인덱스가 트리 노드의 부모와 자식 관계를 어떻게 나타내는지 이해하면, 힙(Heap)과 같은 고급 자료구조를 학습하는 과정이 훨씬 수월해집니다.

 

이 글에서는 배열 인덱스와 트리 노드의 관계를 체계적으로 정리하고, 자바를 예시로 그 구조가 어떻게 활용되는지를 설명하겠습니다.

배열 인덱스로 보는 부모-자식 관계 규칙

완전이진트리는 배열과 특히 잘 맞는 구조입니다.

루트 노드를 배열의 0번 인덱스에 두면, 부모와 자식 관계를 단순한 수식으로 표현할 수 있습니다.

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

예를 들어 배열 [15, 20, 30, 40, 50, 60]이 있다면,

• 인덱스 0의 15는 루트 노드입니다.
• 인덱스 1의 20은 15의 왼쪽 자식, 인덱스 2의 30은 오른쪽 자식입니다.
• 인덱스 3의 40은 20의 왼쪽 자식이고, 인덱스 4의 50은 20의 오른쪽 자식입니다.
• 인덱스 5의 60은 30의 왼쪽 자식이 됩니다.

이처럼 배열의 순서만으로도 트리 구조 전체를 파악할 수 있다는 점이 핵심입니다. 연결리스트처럼 포인터를 사용하지 않아도 되므로, 메모리 효율성과 접근 속도에서 큰 장점을 가집니다.

 

자바에서 배열과 ArrayList로 구현하기

자바에서 배열을 사용하면 정해진 크기를 기반으로 인덱스 규칙을 쉽게 적용할 수 있습니다. 하지만 크기를 유연하게 조절해야 하는 경우에는 ArrayList가 더 적합합니다.

import java.util.ArrayList;

class TreeUsingArray {
    private ArrayList<Integer> nodes = new ArrayList<>();

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

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

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

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

 

위 코드에서 add() 메서드를 통해 노드를 추가하면, 인덱스 규칙을 활용해 언제든 부모나 자식 노드로 이동할 수 있습니다. 초보 개발자가 이 구조를 이해하면, 단순 트리뿐 아니라 힙 자료구조를 구현할 때도 자연스럽게 확장할 수 있습니다.

힙 구조와 인덱스 관계의 응용

힙(Heap)은 완전이진트리를 기반으로 한 대표적인 자료구조입니다. 배열 인덱스 규칙을 그대로 따르면서, 부모와 자식 간의 크기 관계(최대 힙: 부모 ≥ 자식, 최소 힙: 부모 ≤ 자식)를 유지합니다.

삽입과 삭제 과정은 다음과 같이 배열 인덱스를 활용합니다.

• 삽입: 배열 끝에 값을 추가한 뒤, 부모 인덱스를 계산하며 "위로 올리기" 과정을 반복합니다.
• 삭제: 루트 노드를 제거하고 마지막 노드를 루트에 배치한 뒤, 자식 인덱스를 계산하며 "아래로 내리기"를 수행합니다.

이 과정에서 모든 이동은 단순한 인덱스 연산으로 처리되므로, 탐색은 O(1), 삽입과 삭제는 O(log n)의 시간 복잡도를 보장합니다. 이는 포인터 기반 트리 구현보다 훨씬 효율적입니다.

 

배열 인덱스와 트리 노드의 관계를 이해하는 것은 자료구조의 핵심을 파악하는 길입니다. 배열의 선형 구조가 트리의 계층적 구조와 자연스럽게 매핑되기 때문에, 자바에서는 ArrayList를 통해 이를 더욱 직관적이고 유연하게 다룰 수 있습니다. 이러한 규칙을 체계적으로 익혀두면 힙, 우선순위 큐, 그래프 알고리즘 등 고급 주제를 다룰 때 큰 도움이 됩니다.

 

이 글에서 배운 인덱스 규칙을 직접 코드에 적용해 보며, 자료구조의 근본 원리를 체득하시길 권장합니다.