[자료구조] Tree (3): 이진 트리(Binary Tree) 완벽 정리

프로그래밍을 배우다 보면, 한 번쯤은 트리 구조를 마주치게 된다. 그리고 그 트리 구조의 입구에는 늘 '이진 트리(Binary Tree)'가 있다. 이진 트리는 단순히 자식 노드를 둘만 가지는 트리라고 배우지만, 그 안에는 탐색, 정렬, 재귀, 메모리 최적화, 알고리즘 설계 등 다양한 문제 해결 전략이 내포되어 있다. 단순하지만 강력하고, 구조적으로 간단하지만 응용 범위는 광범위하다.

 

이번 글에서는 이진 트리의 기본 개념부터 시작해서 다양한 종류와 구조적 특성, 연산 방식, 그리고 실전에서 어떤 방식으로 활용되는지까지 자연스럽게 풀어보려 한다. 단순한 용어 정리를 넘어서, "왜 이런 구조가 존재하고", "어디에 쓰이는지를" 중심으로 공부해보자.

---

이진 트리란 무엇인가?

이진 트리(Binary Tree)는 각 노드가 최대 두 개의 자식 노드를 갖는 트리 구조를 말한다. 여기서 중요한 건 '최대'라는 표현이다. 즉, 어떤 노드는 자식이 없을 수도 있고, 하나만 있을 수도 있으며, 둘 다 있을 수도 있다. 그리고 이 세 가지 상황 모두 유효한 이진 트리이다.

 

예를 들어 아래와 같은 구조도 이진 트리이다.

이진 트리의 예시

이 트리에서 A는 루트(root)이고, 두 개의 자식 노드인 B와 C를 가지고 있다. B는 왼쪽 자식(D)만 가지고 있고, C는 자식이 없다. 이처럼 왼쪽 서브트리와 오른쪽 서브트리를 각각 독립적으로 가질 수 있다는 유연성이 이진 트리의 핵심이다.

 

이진 트리는 기본이지만, 이후 배울 다양한 트리 구조(예를 들어 이진 탐색 트리(BST), 힙(Heap), 균형 트리(AVL Tree, Red-Black Tree))들의 기반이 된다. 그만큼 정확한 개념 이해가 중요하다.

---

이진 트리의 다양한 형태: Full, Complete, Strict

이진 트리라는 큰 틀 안에서도 노드의 배치 방식이나 자식 노드 유무에 따라 다양한 하위 유형이 존재한다. 각각의 특징은 알고리즘 문제에서 시간 복잡도나 구조 선택의 기준이 되기도 한다.

 

1️⃣ Full Binary Tree

리프 노드가 아닌 모든 노드가 0개 또는 2개의 자식만 갖는 트리를 말한다. 즉, 자식이 하나만 있는 노드는 허용되지 않는다. 일반적으로 모든 리프 노드가 같은 깊이에 존재하며, 꽉 찬 느낌을 준다. (리프 노드가 모두 같은 깊이에 있을 필요는 없다.)

 

이 구조는 계산이 깔끔해서, 노드 수나 높이 등을 쉽게 구할 수 있는 장점이 있다.

 

2️⃣ Complete Binary Tree

완전 이진 트리는 배열 기반 힙(Heap) 구조에서 자주 사용된다. 마지막 레벨을 제외하고는 모든 레벨이 완전히 채워져 있어야 하며, 마지막 레벨은 왼쪽부터 순차적으로 채워져야 한다.

 

이 구조는 메모리 낭비를 줄이면서도 배열 인덱스를 활용한 빠른 접근이 가능하다는 점에서, 실무적으로 자주 등장한다.

 

3️⃣ Strict Binary Tree

정이진 트리는 Full과 비슷하지만 더 유연한 개념이다. 모든 노드가 자식이 없거나, 정확히 두 개의 자식을 가지는 구조로, 자식이 하나만 있는 노드는 허용되지 않는다. 조건이 엄격해서 'strict'라는 이름이 붙었다.

 

이 정의는 Full Binary Tree의 하위 개념처럼 보이지만 리프의 위치가 달라도 상관없다. Full은 트리 전체가 꽉 찬 상태를 의미하는 반면, Strict는 구조적 조건만 만족하면 높이가 달라도, 리프가 어긋나도 상관없다.

---

이진 트리의 수학적 속성

이진 트리의 아름다움 중 하나는 그 구조가 수학적으로 정제되어 있다는 점이다. 즉, 노드의 수, 높이, 레벨에 따라 예측 가능한 계산이 가능하다는 것이다.

 

예를 들어, 높이가 h인 Full Binary Tree에서 레벨 h에 있는 노드 수는 2ʰ이다.

레벨 h의 노드 수

전체 노드 수는 2^(h+1) - 1이라는 공식으로 구할 수 있다. 이건 각 레벨의 노드 수를 더한 결과와도 같다.

(2⁰ + 2¹ + 2² + … + 2ʰ = 2^(h+1) - 1)

 

반면, Complete Binary Tree는 조금 유동적인 구조이기 때문에, 전체 노드 수는 2ʰ 이상 2^(h+1) -1 이하가 된다.

 

이런 속성들은 나중에 트리 구조를 배열로 구현하거나, 힙 연산을 구현할 때 반드시 활용된다.

---

이진 트리의 구조와 구현 방식

프로그래밍 언어에서 이진 트리는 일반적으로 다음과 같은 구조체로 표현된다. 여기서는 C 언어 기준으로 살펴보자.

struct BinaryTreeNode {
    int data;
    struct BinaryTreeNode* left;
    struct BinaryTreeNode* right;
};

 

각 노드는 데이터를 저장하고, 왼쪽과 오른쪽 자식 노드를 가리키는 포인터를 가진다. 이 구조를 기반으로 탐색, 삽입, 삭제 등의 연산이 모두 구현된다. Java나 Python에서도 유사한 클래스 형태로 표현할 수 있으며, 재귀적 정의(노드가 또 다른 트리를 품고 있음)라는 점이 구현의 핵심이다.

---

이진 트리에서 할 수 있는 연산들

이진 트리는 단지 구조적으로 데이터를 담고 있는 게 아니라, 그 위에서 다양한 연산이 일어난다. 대표적으로는 다음과 같은 연산이 있다.

• traverse: 전체 트리를 순회하는 연산. 전위(preorder), 중위(inorder), 후위(postorder), 레벨 순서(level-order) 등의 방식이 있다.
• insert: 새로운 데이터를 트리에 삽입.
• delete: 특정 노드를 삭제.
• search: 원하는 값을 가진 노드를 탐색. 

이 외에도 트리의 크리(size)나 높이(height)를 구하는 연산도 자주 쓰이며, 이러한 대부분의 연산은 재귀적으로 구현된다. 그래서 트리를 이해하는 건 곧 재귀적 사고를 훈련하는 과정이기도 하다.

---

실전에서 이진 트리는 어떻게 사용될까?

이진 트리는 실제로 다양한 분야에서 쓰인다. 여기서 몇 가지 대표적인 예를 살펴보자.

• 수식 트리(Expression Tree): 컴파일러에서 수식을 해석할 때 연산자와 피연산자의 계층 구조를 표현하기 위해 사용된다. 수식의 우선순위를 정확히 반영할 수 있는 구조다.
• 허프만 트리(Huffman Tree): 데이터 압축 알고리즘에서 등장하는 구조로, 문자 빈도 기반으로 트리를 만들어 효율적인 인코딩을 수행한다.
• 이진 탐색 트리(Binary Search Tree): 중복 없는 정렬 데이터를 효율적으로 저장하고, 평균 O(log n)의 시간 복잡도로 탐색, 삽입, 삭제가 가능하다.
• 힙(Heap): 우선순위 큐의 핵심 자료구조로, Complete Binary Tree를 배열로 표현하여 최소값 혹은 최대값을 빠르게 꺼낼 수 있게 해준다.

이처럼 이진 트리는 다양한 문제 해결에서 반복적으로 등장하는 도구이며, 실전에서는 이 구조 위에 다양한 규칙과 연산을 얹어서 응용하게 된다.

---

이진 트리는 단순히 "왼쪽과 오른쪽 자식을 가진 트리"라는 개념에 그치지 않는다. 이는 재귀적 사고, 정렬된 데이터 구조, 효율적인 탐색 방식, 다양한 실전 응용의 기반이 되는 매우 중요한 개념이다.

 

이번 글에서는 이진 트리의 기본적인 정의와 다양한 종류, 수학적 속성과 구현 구조, 그리고 연산과 활용까지 총체적으로 다뤄보았다. 이후 글에서는 이진 트리 위에서 작동하는 순회(Traversal) 방식을 중심으로, 트리를 어떻게 탐색하고 데이터를 읽을 수 있는지를 구체적으로 살펴볼 예정이다.

 

이진 트리를 제대로 이해했다면, 이제부터는 "트리를 어떻게 탐색할까?"라는 질문에 답할 차례다.

다음 글에서 이어가자.