이진 트리

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요
2. 정의
- 2.1. 재귀적 정의
- 2.2. 그래프 이론을 사용한 정의
3. 용어
4. 이진 트리의 종류
5. 이진 트리의 속성
6. 이진 트리 탐색
7. 표현 방법
- 7.1. 배열 표현
- 7.2. 연결 리스트 표현
8. 응용
참조

1. 개요

이진 트리는 각 노드가 최대 두 개의 자식을 갖는 트리 자료구조로, 공집합이거나 루트 노드, 왼쪽 부트리, 오른쪽 부트리로 구성된 튜플로 재귀적으로 정의된다. 이진 트리는 그래프 이론, 다양한 용어 정의, 그리고 완전, 정, 포화, 균형, 변질 트리 등 여러 종류로 분류된다. 이진 트리는 배열 또는 연결 리스트로 표현할 수 있으며, 이진 탐색 트리, 이진 힙, 수식 트리 등 다양한 자료 구조와 알고리즘에 활용된다.

2. 정의

(rooted) binary tree^영어는 각 노드가 최대 두 개의 자식 노드를 갖는 자료 구조의 일종이다. 이진 트리는 재귀적 정의와 그래프 이론을 사용한 정의, 두 가지 방법으로 정의할 수 있다.

하위 섹션에서 재귀적 정의와 그래프 이론을 사용한 정의를 자세히 설명한다.

2. 1. 재귀적 정의

'''이진 트리'''((rooted) binary tree^영어)는 자료 구조의 일종으로, 다음과 같이 재귀적으로 정의할 수 있다.

공집합이거나,
루트 노드(root node^영어)와 왼쪽 부트리(left subtree^영어), 오른쪽 부트리(right subtree^영어)의 세 요소로 구성된 튜플.

이때 왼쪽 부트리와 오른쪽 부트리는 각각 다시 이진 트리이다.

혹자는 이진 트리에 공집합을 포함시키지 않기도 한다. 이 경우, 이진 트리는 다음과 같이 정의된다.

루트 노드(root node^영어)
공집합 또는 왼쪽 부트리(left subtree^영어)
공집합 또는 오른쪽 부트리(right subtree^영어)

이진 트리를 정의할 때, 자식 노드 중 하나만 비어 있을 수 있다는 가능성을 고려해야 한다. 일부 교과서에서는 이를 위해 ''확장 이진 트리''라는 아티팩트를 사용한다. 확장 이진 트리는 다음과 같이 재귀적으로 정의된다.^[17]

공집합은 확장 이진 트리이다.
T₁과 T₂가 확장 이진 트리이면, T₁의 왼쪽에 T₁, T₂의 오른쪽에 T₂를 연결하고 루트 ''r''을 추가하여 얻은 확장 이진 트리를 T₁ • T₂로 표시한다. 이때 하위 트리가 비어 있지 않으면 가장자리를 추가한다.

이 구성을 다른 방식으로 표현하면, 공집합 대신 다른 유형의 노드를 고려하는 것이다. 예를 들어 일반 노드가 원이라면, 사각형 노드를 생각할 수 있다.^[10]

2. 2. 그래프 이론을 사용한 정의

이진 트리는 모든 노드가 최대 두 개의 자식을 갖는 근원 트리이자 순서 트리이다. 근원 트리는 자연스럽게 레벨(루트로부터의 거리) 개념을 부여한다. 따라서 모든 노드에 대해 한 레벨 아래에 연결된 노드로 자식의 개념을 정의할 수 있다. 이러한 자식들의 순서(예: 평면에 그리는 것)는 왼쪽 자식과 오른쪽 자식을 구별할 수 있게 한다.^[11] 그러나 이것은 왼쪽 자식은 있지만 오른쪽 자식은 없는 노드와 오른쪽 자식은 있지만 왼쪽 자식은 없는 노드를 구별하지 못한다.

필요한 구별은 먼저 에지를 분할하여 만들 수 있다. 즉, 이진 트리를 3중항 (V, E₁, E₂)으로 정의한다. 여기서 (V, E₁ ∪ E₂)는 근원 트리(또는 방향성 트리)이고 E₁ ∩ E₂는 비어 있으며, 또한 모든 ''j'' ∈ { 1, 2 }에 대해 모든 노드가 최대 하나의 E_''j'' 자식을 갖도록 요구한다.^[12] 구별을 만드는 더 비공식적인 방법은 수학 백과사전에서 인용하여 "모든 노드는 왼쪽 자식, 오른쪽 자식, 둘 다 또는 아무것도 없음"을 가지며, 이러한 "모두 다름" 이진 트리임을 명시하는 것이다.^[13]

3. 용어

'''왼쪽 자식 노드'''(left child node^영어)는 왼쪽 부트리의 노드이다.
'''오른쪽 자식 노드'''(right child node^영어)는 오른쪽 부트리의 노드이다.
'''부모 노드'''(parent node^영어)는 그 노드를 자식으로 하는 노드이다.
'''형제 노드'''(sibling node^영어)는 부모가 같은 두 노드이다.
노드의 '''차수'''(degree^영어)는 자식의 수이다.
'''잎 노드'''(external/leaf node^영어)는 차수가 0인 노드이다. 즉, 자식이 없는 노드이다.
'''내부 노드'''(internal/branch node^영어)는 차수가 0이 아닌 노드이다. 즉, 자식이 있는 노드이다.
'''방향 간선'''(directed edge^영어)은 부모 노드가 첫째, 자식 노드가 둘째 원소인 순서쌍이다. 그림의 화살표라고 생각할 수 있다.
'''경로'''(path^영어)는 이웃하는 두 노드가 앞이 부모, 뒤가 자식인, 노드의 열이다.
경로의 '''길이'''(length^영어)는 경로가 포함하는 방향 간선의 수이다. 특히, 시작점과 출발점이 같은 경로의 길이는 0이다.
두 노드 사이에 양수 길이 경로가 존재한다면, 시작점 노드를 도착점 노드의 '''조상 노드'''(ancestor node^영어)이라고 하고, 반대로 도착점을 시작점의 '''자손 노드'''(descendant node^영어)이라고 한다.
노드의 '''깊이'''(depth^영어)는 루트 노드에서 자신까지 가는 경로의 길이이다. 특히, 루트 노드의 깊이는 0이다.
노드의 '''레벨'''(level^영어)는 루트 노드에서 자신까지 가는 경로의 길이 더하기 1이다. 특히, 루트 노드의 레벨은 1이다. 간혹 트리의 특정 깊이를 가지는 노드의 집합을 레벨이라고 하기도 한다.
노드의 '''높이'''(height^영어)는 그 노드와 단말 노드 사이의 경로의 최대 길이이다.
노드의 '''크기'''(size^영어)는 자기 자신 및 모든 자손 노드의 수이다.
트리의 깊이, 레벨, 높이, 크기는 각각 노드의 깊이, 레벨, 높이, 크기의 최댓값이다. 특히, 트리의 높이는 그 루트 노드의 높이와 같으며, 트리의 크기는 그 루트 노드의 크기와 같다.

4. 이진 트리의 종류

이진 트리는 그 구조와 속성에 따라 다양한 종류로 분류된다. 트리 용어는 문헌마다 차이가 있어 표준화가 잘 되어 있지 않다.

'''루트 이진 트리'''(rooted binary tree^영어): 루트 노드를 가지며, 모든 노드는 최대 두 개의 자식 노드를 갖는다.
'''정 이진 트리'''(full binary tree^영어): 모든 노드가 0개 또는 2개의 자식 노드를 갖는 트리이다. 때로는 proper 또는 plane 이진 트리라고도 불린다.
'''포화 이진 트리'''(perfect binary tree^영어): 모든 내부 노드가 두 개의 자식 노드를 가지며 모든 잎이 동일한 깊이 또는 레벨을 갖는 트리이다.
'''완전 이진 트리'''(complete binary tree^영어): 마지막 레벨을 제외하고 모든 레벨이 완전히 채워져 있으며, 마지막 레벨의 모든 노드는 가능한 한 가장 왼쪽에 있는 트리이다.
'''무한 완전 이진 트리'''(infinite complete binary tree^영어): 모든 노드가 두 개의 자식 노드를 갖는 트리이다. 레벨의 집합은 가산 무한이다.
'''균형 이진 트리'''(balanced binary tree^영어): 잎 노드에 대해 가능한 한 최대의 최소 높이(깊이)를 갖는 트리이다. 일반적으로 모든 노드의 왼쪽과 오른쪽 하위 트리의 높이 차이가 1 이하이다.
'''변질 트리'''(degenerate tree^영어): 각 부모 노드가 오직 한 개의 연관된 자식 노드를 갖는 트리이다. 이는 성능 면에서 트리가 연결 리스트처럼 동작한다는 것을 의미한다.

4. 1. 루트 이진 트리 (Rooted Binary Tree)

루트 이진 트리(-二進-, rooted binary tree^영어)는 루트 노드를 가지며, 모든 노드는 최대 두 개의 자식 노드를 갖는 이진 트리이다.

4. 2. 정 이진 트리 (Full Binary Tree, Proper Binary Tree)

정 이진 트리(整二進-, full binary tree^영어)는 모든 노드가 0개 또는 2개의 자식 노드를 갖는 트리이다. 때로는 proper 또는 plane 이진 트리라고도 불린다.^[14]^[15]^[16]

4. 3. 포화 이진 트리 (Perfect Binary Tree)

포화 이진 트리(perfect binary tree^영어)는 모든 내부 노드가 두 개의 자식 노드를 가지며 모든 잎 노드가 동일한 깊이 또는 레벨을 갖는 이진 트리이다.^[18] 이는 모든 잎 노드가 같은 레벨에 있다는 점에서 완전 이진 트리의 조건을 만족한다. 주어진 깊이에 대한 한 사람의 가계도가 포화 이진 트리의 예가 될 수 있는데, 이는 각 사람이 정확히 두 명의 생물학적 부모(어머니와 아버지)를 갖기 때문이다.

4. 4. 완전 이진 트리 (Complete Binary Tree)

완전 이진 트리(完全二進-, complete binary tree^영어)는 마지막 레벨을 제외하고 모든 레벨이 완전히 채워져 있으며, 마지막 레벨의 모든 노드는 가능한 한 가장 왼쪽에 있는 이진 트리이다.^[19] 마지막 레벨 ''h''에서 1부터 2^''h''-1 개의 노드를 가질 수 있다.^[19] 어떤 저술자는 '''완전(complete)'''이라는 용어를 포화 이진 트리를 지칭하는데 사용하며, 이 경우 마지막 레벨이 채워지지 않을 수 있는 완전 이진 트리를 '''거의 완전한(almost complete)''' 이진 트리 또는 '''대체로 완전한(nearly complete)''' 이진 트리라고도 한다.^[20]^[21] 완전 이진 트리는 배열을 사용해 효율적으로 표현할 수 있다.^[19]

다른 정의로는, 어떤 n에 대해 모든 잎이 n 또는 n-1의 "깊이"를 가지며, 모든 잎을 가능한 한 왼쪽에 배치한 이진 트리를 가리키기도 한다. 이 경우, 가장 "아래" 레벨은 왼쪽부터 모두 연속적으로 채워져 있어야 한다.

"거의 완전한 이진 트리"(almost complete binary tree)는 오른쪽에 자식이 있으면 반드시 왼쪽에 자식이 있지만, 그 반대는 반드시 참이 아닌 것을 말한다.

4. 5. 무한 완전 이진 트리 (Infinite Complete Binary Tree)

무한 완전 이진 트리(infinite complete binary tree^영어)는 모든 노드가 두 개의 자식 노드를 갖는 트리이다. 레벨의 집합은 가산 무한이다. 모든 노드의 집합은 가산 무한이지만, 루트로부터의 모든 무한한 경로의 집합은 연속체의 원소 개수를 가지고 있어 셀 수 없다. 이러한 경로는 칸토어 집합의 점 또는 (Stern-Brocot 트리의 예를 사용해) 양의 무리수 집합과 일치한다.^[19]

4. 6. 균형 이진 트리 (Balanced Binary Tree)

균형 이진 트리(均衡二進-, balanced binary tree^영어)는 일반적으로 모든 노드의 왼쪽과 오른쪽 하위 트리의 높이 차이가 1 이하인 이진 트리 구조이다.^[22] 이러한 구조는 탐색, 삽입, 삭제 연산의 시간 복잡도를 O(log n)으로 유지하는 데 중요한 역할을 한다.

또는, 어떤 잎 노드도 다른 잎 노드보다 루트에서 훨씬 멀리 떨어져 있지 않은 이진 트리로 정의할 수도 있다.^[23] (여기서 "훨씬 멀리"에 대한 정의는 균형을 잡는 방법에 따라 달라질 수 있다.)

아래는 균형 트리와 불균형 트리의 구조를 시각적으로 비교한 예시이다.

```text

: '''h''' '''Balanced''' '''Unbalanced, h = (n + 1)/2 - 1'''
: 0: ABCDE ABCDE
: / \ / \
: 1: ABCD E ABCD E
: / \ / \
: 2: AB CD ABC D
: / \ / \ / \
: 3: A B C D AB C
: / \
: 4: A B

4. 7. 변질 트리 (Degenerate Tree, Pathological Tree)

변질 트리(degenerate tree, 또는 pathological tree)는 각 부모 노드가 오직 한 개의 연관 자식 노드를 갖는 트리이다.^[24] 이는 성능 면에서 트리가 연결 리스트 데이터 구조처럼 동작한다는 것을 의미한다.

5. 이진 트리의 속성

정 이진 트리에서 노드 개수 $n$ 은 최소 $2h+1$ 개, 최대 $2^{h+1}-1$ 개이다. 여기서 $h$ 는 트리의 높이이며, 루트 노드 하나로만 이루어진 트리는 높이가 0이다.
포화 이진 트리의 잎 노드 개수 $l$ 은 $l = (n + 1)/2$ 이다. 잎 노드가 아닌 노드(내부 노드)의 개수는 ${\displaystyle n-l=\sum _{k=0}^{\log _{2}(l)-1}2^{k}=2^{\log _{2}(l)}-1=l-1}$ 이기 때문이다. 이는 $l$ 개의 잎 노드를 지닌 포화 이진 트리가 $n = 2l - 1$ 개의 노드를 갖는다는 것을 의미한다.
'''균형''' 정 이진 트리에서, $h = \lceil log_2(l) \rceil + 1 = \lceil log_2((n + 1)/2) \rceil + 1 = \lceil log_2(n + 1) \rceil$ 이다(천장 함수 참고).
'''포화''' 정 이진 트리에서, $l = 2^h$ 이므로, $n = 2^{h+1} - 1$ 이다.
$n$ 개 노드를 가진 '''완전''' 이진 트리의 가능한 최대 널 링크(자식 노드 없음)의 개수는 $(n + 1)$ 개이다.
$n$ 개 노드를 가진 '''완전''' 이진 트리의 경우, 높이는 $\lfloor\log_2n\rfloor$ 이고 내부 노드의 개수는 $\lfloor n/2\rfloor$ 이다.
$n_0$ 개의 잎 노드와 차수(degree)가 2인 $n_2$ 개의 노드를 가진 비어있지 않은 이진 트리에 대해, $n_0=n_2+1$ 가 성립한다.^[25]
이진 트리의 노드의 수가 $n$ 이라면, 공집합 부트리의 수는 $n+1$ 개이다.
이진 트리의 높이가 $h$ 라면, 노드의 수는 최소 $h$ 개, 최대 $2^{h+1}-1$ 개이다.
포화 이진 트리의 높이가 $h$ 라면, 노드의 수는 $2^{h+1}-1$ 개이며, 잎 노드의 수는 $2^h$ 개이다.
완전 이진 트리의 높이가 $h$ 라면, 노드의 수는 최소 $2^h$ 개, 최대 $2^{h+1}-1$ 개이다.
완전 이진 트리의 노드에 0부터 시작하여 번호를 매긴다면, $i$ 번째 노드의 자식 노드는 (존재한다면) $2i+1,2i+2$ 번째 노드이며, 부모 노드는 (존재한다면) $\lfloor(i-1)/2\rfloor$ 번째 노드다.
무한 완전 이진 트리의 노드의 수는 $\aleph_0$ 이며, 경로의 수는 $2^{\aleph_0}$ 이다.
'''전체''' 이진 트리의 노드 수 $n$ 은 최소 $2h+1$ 개이고 최대 $2^{h+1}-1$ 개이다(즉, '''완전''' 이진 트리의 노드 수). 여기서 $h$ 는 트리의 높이이다. 최소 노드 수는 높이당 두 개의 자식 노드만 추가하여 얻고( $2h+1$ , 루트 노드 계산을 위해 1개), 최대 노드 수는 각 레벨에 노드를 완전히 채워 얻는다(완전 트리). 완전 트리의 경우 노드 수는 $1 + 2 + 4 + \ldots + 2^h = 2^{h + 1} - 1$ 개이며, 마지막 등식은 등비 수열 합에서 나온다.
'''완전''' 이진 트리에서 잎 노드 수 $l$ 은 $l = (n + 1) / 2$ 개이다(여기서 $n$ 은 트리의 노드 수).
$l$ 개의 잎 노드와 차수 2인 $i_2$ 개의 노드(두 개의 자식 노드를 가진 내부 노드)를 가진 비어 있지 않은 이진 트리에 대해, $l = i_2 + 1$ 이다.^[25]
주어진 $n$ 개의 노드가 있을 때, 최소 가능한 트리 높이는 $h_{min} = \log _2 (n+1)-1$ 이며, 이 경우 트리는 균형 잡힌 전체 트리 또는 완전 트리이다.
$l$ 개의 잎이 있는 이진 트리의 최소 높이는 $h_m = \log _ 2 (l)$ 이다.
비어 있지 않은 이진 트리에서 $n$ 이 총 노드 수이고 $e$ 가 총 간선 수이면 $e = n - 1$ 이다. 이는 루트 노드를 제외한 각 노드에 하나의 간선이 필요하기 때문이다.
''n''개의 노드가 있는 이진 트리에서 널 링크(즉, 노드의 부재 자식)의 수는 (''n'' + 1)개이다.
''n''개의 노드가 있는 '''완전''' 이진 트리에서 내부 노드 수는 $\lfloor n/2\rfloor$ 이다.

6. 이진 트리 탐색

이진 트리의 모든 노드를 특정 순서로 방문하는 것을 이진 트리 탐색이라고 한다. 탐색 방법은 크게 전위 순회, 중위 순회, 후위 순회, 레벨 순회로 나뉜다. 이진 트리에 대해 수행할 수 있는 다양한 연산에는 노드를 다른 두 노드 사이에 삽입하거나 리프 노드 뒤에 추가하는 것이 있으며, 이때 어떤 자식 노드가 될지 지정된다.

6. 1. 전위 순회 (Pre-order Traversal)

전위 순회는 루트 노드를 먼저 방문하고, 그 다음 왼쪽 서브트리, 마지막으로 오른쪽 서브트리를 재귀적으로 방문하는 방식이다. 이러한 순서는 부모 노드가 자식 노드보다 먼저 처리되기 때문에 위상 정렬된 순서로 볼 수 있다.

이진 트리에서 특정 노드와 그 자손들은 또 다른 이진 트리를 형성하는데, 이를 부분 트리라고 한다.

이진 트리를 부분 트리로 나누어 재귀적으로 탐색하는 것은 자연스러운 방법이다. 전위 순회는 뿌리(루트 노드)를 먼저 조사하고, 그 다음에 매달린 부분 트리를 조사하는 방식이다.

6. 2. 중위 순회 (In-order Traversal)

중위 순회는 왼쪽 자식 노드(L), 현재 노드(P), 오른쪽 자식 노드(R) 순서로 방문한다. 이진 트리에서 어떤 노드와 그 자손은 부분 트리(subtree)를 구성한다.^[31]

이진 트리를 부분 트리로 나누어 재귀적으로 탐색하는 것은 자연스러운 방법이다. 한쪽 부분 트리를 조사하고, 루트를 조사하고, 이어서 반대쪽 부분 트리를 조사하는 것을 중위 순회(in-order)라고 한다. 이진 탐색 트리에서는 중위 순회 탐색은 노드를 크기 순 (또는 크기의 역순)으로 조사하게 된다. In-order 순회 방식은 항상 현재 노드의 왼쪽 서브트리를 재귀적으로 순회하고, 다음으로 현재 노드를 방문하며, 마지막으로 현재 노드의 오른쪽 서브트리를 재귀적으로 순회한다.

6. 3. 후위 순회 (Post-order Traversal)

후위 순회는 항상 현재 노드의 왼쪽 서브 트리를 재귀적으로 순회하고, 다음으로 현재 노드의 오른쪽 서브 트리를 재귀적으로 순회한 다음 현재 노드를 방문하는 방식이다. 왼쪽 자식 노드(L), 오른쪽 자식 노드(R), 내 노드(P) 순서로 방문한다고 할 수 있다. 부분 트리를 조사한 다음 그 뿌리를 조사하는 것이 후위 순회이다. 후위 순회는 이진 수식 트리의 후위 표기식을 얻는 데 유용할 수 있다.^[32]

6. 4. 레벨 순회 (Level-order Traversal, 너비 우선 탐색)

레벨 순회는 루트 노드에서 시작하여, 깊이 1인 노드들, 깊이 2인 노드들, ..., 깊이 N인 노드들(N: 트리의 깊이) 순서로 방문한다. 이러한 레벨 순회는 너비 우선 탐색이라고도 불린다. 깊이 우선 탐색과 대조적으로, 아직 방문하지 않은 노드를 뿌리에 가까운 쪽부터 탐색한다.

7. 표현 방법

이진 트리는 배열이나 연결 리스트를 사용하여 표현할 수 있다.

1차원 배열 표현: 이진 트리의 i번째 노드를 배열의 i번째 요소에 저장한다.
장점: 노드의 위치를 쉽게 접근할 수 있다.
단점: 특정 트리에서 기억 공간 낭비가 심할 수 있다.
연결 리스트 표현: 왼쪽 자식을 가리키는 포인터 필드와 오른쪽 자식을 가리키는 포인터 필드를 포함하는 노드로 표현한다.
장점: 기억 장소를 절약할 수 있고, 노드의 삽입과 삭제가 용이하다.
단점: 이진 트리가 아닌 일반 트리의 경우에는 각 노드의 차수만큼 가변적인 포인터 필드를 가져야 하기 때문에 접근이 어렵다.

레코드와 참조가 있는 언어에서, 이진 트리는 일반적으로 데이터를 포함하고 왼쪽 자식과 오른쪽 자식에 대한 참조를 갖는 트리 노드 구조를 통해 구성된다. 때로는 부모 노드를 가리키는 참조를 포함하기도 한다. 만약 자식 노드가 두 개 미만일 경우, 일부 자식 포인터는 특수한 null 값이나 센티넬 노드로 설정될 수 있다.

이러한 이진 트리의 저장 방법은 포인터가 절반 이상 null이 되거나 센티넬을 가리키기 때문에 상당한 양의 메모리를 낭비한다. 더 보수적인 표현 방법의 대안은 스레드 이진 트리이다.^[26]

태그된 유니언이 있는 ML과 같은 언어에서, 트리 노드는 종종 두 가지 유형의 노드의 태그된 유니언인데, 하나는 데이터, 왼쪽 자식 및 오른쪽 자식의 3-튜플이고, 다른 하나는 "잎" 노드로, 데이터가 없으며 포인터가 있는 언어의 null 값과 거의 동일하게 작동한다.^[27]

간결 자료 구조는 정보 이론의 하한에 의해 설정된, 가능한 최소 공간에 가깝게 차지하는 자료 구조이다.

n

개의 노드를 가진 서로 다른 이진 트리의 수는

\mathrm{C}_{n}

이며, 이는

n

번째 카탈랑 수이다(동일한 ''구조''를 가진 트리를 동일하게 간주한다고 가정).

7. 1. 배열 표현

완전 이진 트리의 경우, 배열을 사용하여 효율적으로 표현할 수 있다. 루트 노드를 배열의 첫 번째 요소에 저장하고, 특정 노드의 왼쪽 자식과 오른쪽 자식은 각각 정해진 인덱스에 저장한다.

장점: 노드의 위치를 쉽게 접근할 수 있다.^[28]
단점: 특정 트리에서 기억 공간의 낭비가 심할 수 있다.

노드의 인덱스가 ''i''인 경우,

관계	인덱스 (루트의 인덱스가 0이라고 가정)
부모 노드 (있는 경우)	$\left \lfloor \frac{i-1}{2} \right \rfloor$
왼쪽 자식 노드	$2i + 1$
오른쪽 자식 노드	$2i + 2$

1부터 시작하는 배열의 경우,

관계	인덱스
부모 노드	$\lfloor i/2 \rfloor$
자식 노드	$2i$ 및 $2i+1$

와 같이 간소화된 구현이 가능하다.^[28]

이 방법은 더 콤팩트한 저장 방식과 더 나은 참조 지역성을 갖는다는 이점이 있으며, 특히 전위 순회 중에 유용하다. 이는 종종 이진 힙에 사용된다.^[29]

7. 2. 연결 리스트 표현

각 노드는 데이터와 왼쪽, 오른쪽 자식 노드를 가리키는 포인터를 갖는다. 이러한 방식은 기억 장소를 절약하고, 노드의 삽입과 삭제를 용이하게 한다는 장점이 있다. 하지만, 이진 트리가 아닌 일반 트리의 경우에는 각 노드의 차수만큼 가변적인 포인터 필드를 가져야 하므로 접근이 어렵다는 단점이 있다.^[26]

레코드와 참조가 있는 언어에서, 이진 트리는 일반적으로 데이터를 포함하고 왼쪽 자식과 오른쪽 자식에 대한 참조를 갖는 트리 노드 구조를 통해 구성된다. 때로는 부모 노드를 가리키는 참조를 포함하기도 한다. 만약 자식 노드가 두 개 미만일 경우, 일부 자식 포인터는 특수한 null 값이나 센티넬 노드로 설정될 수 있다.

태그된 유니언이 있는 ML과 같은 언어에서는, 종종 태그된 유니언으로 이진 트리가 구축된다. 여기에는 두 종류의 노드가 사용되며, 하나는 데이터, 왼쪽 자식, 오른쪽 자식을 가진 3-tuple의 노드이고, 다른 하나는 데이터도 함수도 갖지 않는 "잎"이다(위의 파스칼이나 C와 같은 포인터형을 가진 언어의 nil에 해당).^[27]

8. 응용

이진 트리는 여러 분야에서 활용된다.

이진 탐색 트리는 각 노드에 값을 할당하고, 왼쪽 자식 및 그 자손 노드의 값은 해당 노드보다 작으며, 오른쪽 자식 및 그 자손 노드의 값은 해당 노드보다 크게 구성된 이진 트리이다. 이러한 구조는 이진 탐색을 용이하게 한다.

균형 이진 탐색 트리는 이진 탐색 트리의 높이를 최소화하여 검색 효율을 최적화한 트리이다.

이진 힙은 반순서 집합을 이진 트리로 표현한 것으로, 부모 노드와 자식 노드 사이에 특정 값의 관계(부모 ≤ 자식 또는 부모 ≥ 자식)가 항상 성립한다.

이항 연산자를 사용하는 산술식은 이진 트리로 표현 가능하다. 이렇게 표현된 산술식은 역 폴란드 표기법, 중위 표기법, 전위 표기법으로 나타낼 수 있다.

8. 1. 이진 탐색 트리 (Binary Search Tree)

이진 탐색 트리(binary search tree)는 각 노드에 값이 할당되어 있으며, 특정 노드의 왼쪽 자식 및 그 모든 자손 노드의 값은 해당 노드의 값보다 작고, 오른쪽 자식 및 그 모든 자손 노드의 값은 해당 노드의 값보다 크도록 구성된 이진 트리이다. 이진 탐색 트리를 중위 순회로 탐색하면 각 노드의 값을 크기 순(또는 역순)으로 얻을 수 있다.

이러한 트리를 사용하면 이진 탐색이 용이해진다. 목표로 하는 값을 x라고 할 때, 루트 노드부터 시작하여 다음과 같이 탐색한다.

현재 노드의 값이 n일 때:
* x = n → 목표 값을 찾음
* x > n → 왼쪽 서브 트리를 탐색
* x < n → 오른쪽 서브 트리를 탐색

이러한 과정은 재귀적으로 구현할 수 있다.

8. 2. 균형 이진 탐색 트리 (Balanced Binary Search Tree)

이진 탐색 트리의 검색 효율이 최고가 되는 것은, 트리의 높이가 최소일 때, 즉, 뿌리에서 각 잎까지의 높이가 가능한 한 균등해졌을 경우이다. 이러한 이진 탐색 트리를 균형 이진 탐색 트리라고 부른다.

8. 3. 이진 힙 (Binary Heap)

이진 힙(Binary Heap)은 반순서 집합을 이진 트리로 표현한 것이다. 힙, 이진 힙, 바이너리 힙이라고도 부른다. 부모와 자식 간에는 값이 할당되는데, 부모 ≤ 자식 또는 부모 ≥ 자식 관계가 항상 성립해야 한다. 전자의 경우 루트가 최소값을, 후자의 경우 루트가 최대값을 갖는다.

8. 4. 수식 트리 (Expression Tree)

그림은 이항 연산자를 사용한 산술식을 이진 트리로 표현한 예시이다. 이 식을 역 폴란드 표기법, 중위 표기법, 전위 표기법으로 나타내면 각각 다음과 같다.

'''a b + c d - ×''' e f + ÷
'''(a + b) × (c - d)''' ÷ (e + f)
÷ '''× + a b - c d''' + e f

이는 각각 왼쪽 우선의 후위 순회, 중위 순회, 전위 순회에 해당한다. 그림에서 강조된 부분은 점선으로 둘러싸인 부분 트리이다. 부분 트리가 이진 트리라는 것은, 수식의 항도 역시 수식이라는 것과 잘 대응된다.

참조

_[1] 서적 Discrete Mathematics:Proofs, Structures and Applications, Third Edition https://books.google[...] CRC Press
_[2] 서적 The Algorithm Design Manual https://books.google[...] Springer Science & Business Media
_[3] 서적 The Art Of Computer Programming, Volume 1, 3/E Pearson Education
_[4] 서적 Computer programming system/360 Prentice-Hall
_[5] 서적 Discrete Mathematics and Its Applications, 7th edition McGraw-Hill Science
_[6] 서적 Combinatorics: A Guided Tour https://books.google[...] Mathematical Association of America
_[7] 서적 Graph Theory Applications https://books.google[...] Springer Science & Business Media
_[8] 서적 Sets, Logic and Maths for Computing Springer Science & Business Media
_[9] 서적 Combinatorial Methods with Computer Applications https://books.google[...] CRC Press
_[10] 서적 Combinatorial Algorithms Courier Dover Publications
_[11] 서적 Graph Theory and Interconnection Networks https://books.google[...] CRC Press 2008
_[12] 서적 Parameterized Complexity Theory Springer
_[13] 서적 Binary tree https://books.google[...] Springer Science & Business Media
_[14] 서적 Algorithm design : foundations, analysis, and Internet examples Wiley-India 2011
_[15] 웹사이트 full binary tree http://xlinux.nist.g[...] NIST
_[16] 문서 Richard Stanley, Enumerative Combinatorics, volume 2, p.36
_[17] 서적 Discrete Mathematics and Its Applications 7th edition McGraw-Hill Science
_[18] 웹사이트 perfect binary tree https://xlinux.nist.[...] NIST
_[19] 웹사이트 complete binary tree https://xlinux.nist.[...] NIST
_[20] 웹사이트 almost complete binary tree http://faculty.cs.ni[...] 2015-12-11
_[21] 웹사이트 nearly complete binary tree http://homepages.mat[...]
_[22] 문서 Aaron M. Tenenbaum, et al. Data Structures Using C, Prentice Hall, 1990
_[23] 간행물 "data structure" in Dictionary of Algorithms and Data Structures http://xw2k.nist.gov[...] National Institute of Standards and Technology 2004-12-15
_[24] 웹사이트 Different Types of Binary Tree with colourful illustrations https://towardsdatas[...] 2020-01-22
_[25] 서적 Handbook of Data Structures and Applications Chapman and Hall
_[26] 서적 Classic Data Structures PHI Learning Pvt. Ltd.
_[27] 서적 Programming Language Pragmatics Morgan Kaufmann
_[28] 서적 Introduction to algorithms MIT Press 2001
_[29] 웹사이트 Priority Queue and Binary Heap http://www.cse.hut.f[...] 2023-10-11
_[30] 웹사이트 6.897: Advanced Data Structures Spring 2003 Lecture 12 http://theory.csail.[...] MIT CSAIL 2022-04-14
_[31] 웹사이트 Binary Tree Structure http://www.clear.ric[...] rice.edu 2010-12-28
_[32] 웹사이트 Lecture 18: Tree Traversals http://www.math.ucla[...] 2023-04-29

본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com