[자료구조] 14. 이진 트리

1. 이진 트리의 개념과 구조

1) 트리

• 일반 트리와 이진 트리로 구분됨.

 

2) 일반 트리

• 각 노드의 차수가 가변적이므로 자식 노드의 개수를 예상하기 힘들고, 이를 구현하려면 기억 공간 면에서도 비효율적임.

 

3) 이진 트리

• 트리의 노드 구조를 일정하게 정의하여 트리의 구현과 연산이 쉽도록 정의한 트리.

• 데이터의 구조적인 관계를 잘 반영하고 효율적인 삽입과 탐색을 가능하게 함.

• 일반 트리에 비해 간단하고 효율적으로 구현 가능.

• 가장 중요하면서도 자주 사용되는 트리.

• 다양한 탐색 트리(search tree), 히프(heap) 자료구조, 컴파일러의 수식을 위한 구문 트리(syntax tree) 등의 기본이 되는 자료구조.

• 광범위하게 응용됨.

 

일반 트리와의 차이점

• 공백 이진 트리 존재.

• 서브 트리의 순서 중요.

• 프로그램 구현이 간단함.

• 자식 노드의 순서를 구별(일반 트리는 자식 노드들의 순서를 구별하지 않음).

• 이진 트리는 구조가 간단하며 쉽게 그 구조를 유지하고 메모리를 적게 사용함.

 

이진 트리의 성질

• 노드의 개수가 n개이면 간선의 개수는 정확하게 n-1개.

• 높이가 h인 이진 트리는 최소 (h + 1)개의 노드를 가질 수 있고 최대 (2^h+1 - 1)개의 노드를 가질 수 있음.

 

2. 이진 트리의 종류

1) 포화 이진 트리 (Full Binary Tree)

• 트리의 모든 레벨에 노드가 꽉 차 있는 이진 트리.

• 모든 단말 노드의 높이가 같고, 각 내부 노드가 2개의 자식 노드를 가지는 트리.

• 이진 트리가 가질 수 있는 노드의 최대 수를 지닌 이진 트리.

• 높이가 h일 때 최대 노드 개수는 (2^h+1 - 1)개.

• 루트 노드를 1번으로 시작하여 (2^h+1 - 1)까지 정해진 위치에 대한 노드 번호를 가짐.

• 트리의 높이만 알아도 해당 레벨의 노드 개수 및 전체 노드 개수를 파악할 수 있음.

 

2) 완전 이진 트리 (Complete Binary Tree)

• 마지막 레벨을 제외한 각 레벨이 노드들로 꽉 차 있고, 마지막 레벨에는 노드들이 왼쪽부터 빠짐없이 채워진 트리.

• 높이가 h일 때 레벨 1부터 (h-1)까지는 포화 이진 트리이며, 마지막 레벨 h에서는 왼쪽에서 오른쪽으로 가면서 순서대로 단말 노드가 채워진 이진 트리.

• 노드의 번호는 포화 이진 트리와 같음.

 

3) 트리의 포함 관계

• 포화 이진 트리는 완전 이진 트리에 포함되지만, 완전 이진 트리가 반드시 포화 이진 트리인 것은 아님.

 

4) 편향 이진 트리 (Skewed Binary Tree)

• 왼쪽이나 오른쪽 서브 트리만 가지는 트리.

• 높이 h에 대한 최소 개수의 노드를 가지면서 한쪽 방향의 자식 노드만을 가진 이진 트리.

• 선형 구조와 다르지 않아 비효율적인 트리 구조.

• 특정 노드를 탐색하는 시간 복잡도가 O(n).

 

 

3. 이진 트리의 표현 방법

1) 이진 트리의 표현 방법

• 배열과 같은 순차 자료구조를 이용하여 표현(포화 이진 트리, 완전 이진 트리의 경우 배열 이용).

• 연결 리스트와 같은 연결 자료구조를 이용하여 표현.

 

2) 이진 트리를 배열로 표현하는 과정

• 이진 트리를 포화 이진 트리라고 가정하고 각 노드에 번호를 부여.

• 해당 번호를 배열의 인덱스로 삼아 노드의 데이터를 배열에 저장.

• 루트 노드를 1번으로 하고 하위 레벨로 내려가면서 왼쪽에서 오른쪽으로 차례대로 (2^h+1 - 1)까지 노드에 번호를 붙임.

• 노드의 번호는 1번부터 시작하므로 배열의 인덱스 0번은 사용하지 않음.

 

3) 이진 트리를 배열로 표현할 때의 인덱스

• 루트 노드의 인덱스는 1이고, 형제 노드 중 왼쪽 노드의 인덱스 순서가 오른쪽 노드보다 빠름.

 

부모와 자식의 인덱스 관계

• 자식 노드의 인덱스가 i일 때 부모 노드의 인덱스: ⌊i/2⌋

• 부모 노드의 인덱스가 i일 때 왼쪽 자식 노드 인덱스: 2i

• 부모 노드의 인덱스가 i일 때 오른쪽 자식 노드 인덱스: 2i+1

 

이진 트리의 배열 표현 방법의 문제점

• 편향 이진 트리의 경우, 트리의 높이가 커질수록 배열에 공간이 많이 생겨 기억 공간 낭비 발생.

• 데이터 삽입, 삭제 연산 시 노드 레벨 변경으로 인해 배열에서도 데이터 이동이 발생.

• 배열 크기에 따라 표현할 수 있는 트리의 높이가 제한됨. → 연결 리스트를 이용하여 표현하면 해결 가능.

 

4) 이진 트리의 연결 리스트 표현 방법

• 이진 트리는 연결 자료구조인 포인터를 이용하는 연결 리스트로 표현 가능.

• 포인터를 이용하여 부모 노드와 자식 노드를 연결.

• 연속된 메모리 영역이 아니더라도 연결 가능.

• 이진 트리의 노드 구조체 정의 (C 언어 예시)

typedef struct TreeNode {
    int data;                 /* 노드에 저장할 데이터 */
    struct TreeNode *left;    /* 왼쪽 자식 노드의 포인터 */
    struct TreeNode *right;   /* 오른쪽 자식 노드의 포인터 */
} TreeNode;

 

이진 트리의 연결 리스트 표현 방법의 문제점

• 일반 트리의 경우 각 노드의 차수만큼 가변적인 포인터 필드를 가져야 하므로 데이터 접근에 어려움이 있음.

• 자식 노드가 부모 노드 정보를 알기 어려움.

• 하지만 루트 노드를 가리키는 포인터만 있으면 트리의 모든 노드에 접근 가능.

• 기억 장소를 절약할 수 있고, 노드의 삽입·삭제가 용이함.

• 일반적으로 이진 트리는 연결 리스트 표현 방법을 사용하며, 많은 응용에서 적절하게 활용됨.

 

---

이 내용은 휴넷사회복지평생교육원의 자료구조 강의를 듣고 정리한 것입니다.