이진 트리(Binary Tree) ADT 완벽 가이드: 기본 개념부터 종류와 활용까지

이진 트리의 기본 개념

이진 트리(binary tree)는 어떤 노드도 두 개를 초과하는 자식을 가질 수 없도록 정의된 트리 구조입니다. 즉, 모든 노드의 차수(degree)는 0, 1, 2 중 하나여야 하며, 세 개 이상의 자식을 가질 수 없습니다.

위 그림에서 볼 수 있듯이, 이진 트리는 하나의 루트(root)와 두 개의 서브트리(TreeLeft, TreeRight)로 구성됩니다. 루트를 기준으로 왼쪽에 위치한 모든 노드들의 집합을 왼쪽 서브트리(left subtree), 오른쪽에 위치한 노드들의 집합을 오른쪽 서브트리(right subtree)라고 부릅니다.

이진 트리의 구현

이진 트리의 노드는 자식을 최대 두 개까지만 가질 수 있기 때문에, 각 자식에 대한 포인터를 직접 할당하는 방식으로 손쉽게 구현할 수 있습니다. 트리 노드의 선언 구조는 이중 연결 리스트(doubly linked list)의 노드 선언과 매우 유사합니다. 하나의 노드는 핵심 데이터(key information)와 함께 다른 노드를 가리키는 두 개의 포인터(왼쪽 포인터와 오른쪽 포인터)를 포함하는 구조체로 정의됩니다.

이진 트리 노드 선언 예제

typedef struct tree_node *tree_ptr;
struct tree_node
{
    element_type element1;
    tree_ptr left1; tree_ptr right1;
};
typedef tree_ptr TREE;

위 코드에서 tree_node 구조체는 저장할 데이터(element1)와 왼쪽 자식(left1), 오른쪽 자식(right1)을 가리키는 포인터로 구성되어 있습니다.

이진 트리의 종류

엄격한 이진 트리(Strictly Binary Tree)

엄격한 이진 트리는 모든 노드가 자식을 0개 또는 2개만 가지는 이진 트리입니다. 자식이 하나뿐인 노드는 절대 존재하지 않는다는 것이 특징입니다.

기울어진 트리(Skew Tree)

기울어진 트리(skew tree)는 리프 노드를 제외한 모든 노드가 단 하나의 자식만 가지는 이진 트리입니다. 자식이 어느 방향에 위치하는지에 따라 좌편향 이진 트리와 우편향 이진 트리의 두 가지 유형으로 나뉩니다.

좌편향 이진 트리(Left Skewed Binary Tree)

모든 노드가 왼쪽 자식만을 가지며, 왼쪽 서브트리만으로 구성된 이진 트리입니다.

우편향 이진 트리(Right Skewed Binary Tree)

모든 노드가 오른쪽 자식만을 가지며, 오른쪽 서브트리만으로 구성된 이진 트리입니다.

전 이진 트리(Full Binary Tree / Proper Binary Tree)

전 이진 트리(full binary tree)는 모든 리프 노드가 동일한 레벨에 위치하고, 리프가 아닌 모든 노드가 정확히 두 개의 자식을 가지며, 모든 레벨에 가능한 최대 개수의 노드가 채워져 있는 이진 트리입니다. 높이가 h인 전 이진 트리는 최대 2^h+1 − 1개의 노드를 가질 수 있습니다.

완전 이진 트리(Complete Binary Tree)

완전 이진 트리(complete binary tree)는 리프가 아닌 모든 노드가 정확히 두 개의 자식을 가지지만, 모든 리프 노드가 같은 레벨에 있어야 하는 것은 아닙니다. 마지막 레벨을 제외한 모든 레벨에는 최대 개수의 노드가 존재해야 하며, 마지막 레벨의 노드들은 반드시 왼쪽에서 오른쪽 방향으로 순서대로 채워져야 합니다.

거의 완전 이진 트리(Almost Complete Binary Tree)

거의 완전 이진 트리(almost complete binary tree)는 오른쪽 자식을 가진 모든 노드가 반드시 왼쪽 자식도 함께 가지는 트리입니다. 반대로 왼쪽 자식을 가진다고 해서 반드시 오른쪽 자식까지 가질 필요는 없습니다.

일반 트리와 이진 트리의 차이점

일반 트리(General Tree)

자식 노드의 개수에 제한이 없습니다.
수식(expression)을 평가하기가 까다롭습니다.

이진 트리(Binary Tree)

자식 노드는 최대 두 개까지만 가질 수 있습니다.
수식 평가가 비교적 간단하고 효율적입니다.

트리의 주요 활용 분야

산술식(arithmetic expression)의 처리 및 조작
심볼 테이블(symbol table)의 구성
구문 분석(syntax analysis)
문법(grammar) 작성
수식 트리(expression tree) 생성

이처럼 이진 트리는 제한적인 자식 구조 덕분에 구현이 간단하면서도 수식 처리, 컴파일러 설계 등 다양한 분야에서 폭넓게 활용되는 핵심 자료구조입니다.