이진 트리

컴퓨터 과학에서 이진 트리(二進-, 영어: binary tree)는 각각의 노드가 최대 두 개의 자식 노드를 가지는 트리 자료 구조로, 자식 노드를 각각 왼쪽 자식 노드와 오른쪽 자식 노드라고 한다. 단순히 집합론의 개념을 사용하는 재귀적 정의에서 (비어있지 않은) 이진 트리는 하나의 튜플 (L, S, R)로, L과 R은 이진 트리 또는 공집합이고 S는 싱글턴 집합이다. 일부 구현자는 공집합인 이진 트리도 허용한다.

그래프 이론 측면에서, 여기서 정의한 이진 (그리고 K-항) 트리는 실제로 일종의 방향성 그래프(arborescence)다. 따라서, 하나의 이진 트리는 bifurcating arborescence라고도 불리는데, 이 용어는 현대 컴퓨터 과학 기술이 널리 퍼지기 이전의 아주 오래된 프로그래밍 책에서 볼 수 있다. 이진 트리가 정렬 트리이면서, 루트 트리인 경우, 방향성 그래프가 아닌 비방향성 그래프로 해석할 수도 있다. 일부 저술자는 이진 트리 대신 루트 이진 트리를 사용해, 트리가 루트를 가지고 있지만, 위에서 설명한 것처럼, 이진 트리가 항상 루트를 가지고 있다는 사실을 강조한다. 이진 트리는 k가 2인 정렬 K-항 트리의 특수한 경우다.

수학에서, 이진 트리라고 명명한 것이 저술자마다 현저히 다를 수 있다. 어떤 이들은 컴퓨터 과학에서 보통 사용되는 정의를 사용하지만, 다른 이들은 정확하게 두 개의 자식 노드를 가진 잎이 없는 모든 트리로 정의하고 꼭 (왼쪽과 오른쪽으로) 자식 노드를 정렬하지도 않는다.

컴퓨팅에서, 이진 트리는 아주 다른 두 가지 방식으로 사용된다:

첫째, 어떤 값 또는 각 노드와 연관된 레이블에 기반한 노드에 액세스하는 수단. 이 방식의 이진 트리는 이진 탐색 트리와 이진 힙 구현에 사용되며, 효율적인 검색과 정렬을 위해 사용된다. 하나의 자식 노드만 있는 경우에도 왼쪽 또는 오른쪽으로 루트가 아닌 노드를 지정하면 이러한 일부 적용에 있어 문제가 되며, 특히 이진 탐색 트리에서 현저하다. 하지만, 특정 노드를 트리 내에 배치하는 것은 개념 정보의 일부가 아니다. 예를 들어, 일반적인 이진 탐색 트리에서 노드가 놓이는 위치는 추가되는 순서를 거의 따르며, 의미의 변경없이 재배치할 수 있다(예를 들어 자가 균형 이진 탐색 트리).
둘째, 연관 분기 구조를 이용한 데이터 표현. 이러한 경우 다른 노드의 아래와(또는) 왼쪽 또는 오른쪽에 노드를 특정하게 배치하는 것은 정보의 일부이다(즉, 이러한 배치를 변경하는 것은 의미 변경을 뜻한다). 일반적인 예는 허프만 코딩과 cladogram에 나타난다. 오늘 날의 문서를 장, 절, 구문 등으로 나누는 것은 이진 트리가 아닌 n-항 트리를 이용한 유사 예제다.

정의 편집

재귀적 정의 편집

(루트가 있는) 이진 트리(영어: (rooted) binary tree)는 자료 구조의 일종이며, 다음과 같이 재귀적으로 정의할 수 있다. 이진 트리 $B$ 는 공집합이거나, 다음과 같은 세 가지 요소로 구성된 튜플 $B=(S_{B},L_{B},R_{B})$ 이다.

노드 $S_{B}$ . 이를 루트 노드(영어: root node)라고 한다.
이진 트리 $L_{B}$ . 이를 왼쪽 부트리(-副-, 영어: left subtree)라고 한다.
이진 트리 $R_{B}$ . 이를 오른쪽 부트리(-副-, 영어: right subtree)라고 한다.

혹자는 이진 트리에 공집합을 포함시키지 않는다. 이 경우, 이진 트리 $B=(S_{B},L_{B},R_{B})$ 는 다음 세 가지 요소로 구성된다.

노드 $S_{B}$ . 이를 루트 노드(영어: root node)라고 한다.
공집합 또는 이진 트리 $L_{B}$ . 이를 왼쪽 부트리(-副-, 영어: left subtree)라고 한다.
공집합 또는 이진 트리 $R_{B}$ . 이를 오른쪽 부트리(-副-, 영어: right subtree)라고 한다.

그래프 이론을 사용한 컨셉 편집

이진 트리는 루트가 있는 트리이며, 즉 모든 노드가 적어도 두 개의 자식 노드를 가진 (평면 트리가 별칭인) 정렬 트리이기도 하다. 루트 트리는 당연히 레벨(루트로부터의 거리)이라는 개념을 가지고 있으며, 따라서 모든 노드에 대해서 해당 노드에 하위 레벨로 연결되는 노드로 자식 노드의 개념을 정의할 수 있다. 이런 자식 노드의 정렬하면 (예를 들어, 노드를 평면 위에 그려서) 왼쪽 자식 노드와 오른쪽 자식 노드를 구분하는 것이 가능하다.

필연적인 구분은 첫번째 모서리 구분으로 만들어지는데, (V, E₁ ∪ E₂)이 루트 트리이고 E₁ ∩ E₂가 비어있는 triplet (V, E₁, E₂)으로 이진 트리를 정의하고 j ∈ { 1, 2 }인 모든 j에 대해 모든 노드가 적어도 하나의 E_j 자식 노드를 갖는다는 것을 요구한다. 좀 더 회화적으로 구분 방법을 말하자면, 수학 백과사전에 인용된대로, "모든 노드가 하나의 좌측 자식 노드나 우측 자식 노드 또는 둘 다 가지고 있다"라고 말하고 이것들이 "모두 다른" 이진 트리라고 지정하는 것이다.

용어 편집

노드의 왼쪽 자식 노드(-子息-, 영어: 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)는 자기 자신 및 모든 자손 노드의 수이다.
트리의 깊이와 레벨과 높이와 크기는 각각 노드의 길이와 레벨과 높이와 크기의 최댓값이다. 특히, 트리의 높이는 그 루트 노드의 높이와 같으며, 트리의 크기는 그 루트 노드의 크기와 같다.

이진 트리의 종류 편집

트리 용어는 잘 표준화되어 있지 않아서 문헌마다 차이가 있다.

루트 이진 트리(-二進-, 영어: rooted binary tree)는 이진 트리의 별칭이다.
정 이진 트리(整二進-, 영어: full binary tree, 때로는 proper 또는 plane 이진 트리라고도 함)는 모든 노드가 0개 또는 2개의 자식 노드를 갖는 트리다.
포화 이진 트리(飽和二進-, 영어: perfect binary tree)는 모든 내부 노드가 두 개의 자식 노드를 가지며 모든 잎 노드가 동일한 깊이 또는 레벨을 갖는다(이는 애매모호하게 완전 이진 트리라고도 불린다). 각각의 사람이 정확히 두 명의 생물학적 부모(한 명의 어머니와 한 명의 아버지)를 갖는 것처럼, 주어진 깊이에 대한 한 사람의 가계도가 포화 이진 트리의 예가 될 수 있다.
완전 이진 트리(完全二進-, 영어: complete binary tree)에서, 마지막 레벨을 제외하고 모든 레벨이 완전히 채워져 있으며, 마지막 레벨의 모든 노드는 가능한 한 가장 왼쪽에 있다. 마지막 레벨 h에서 1부터 2^h-1 개의 노드를 가질 수 있다. 또 다른 정의는 가장 오른쪽의 잎 노드가 (아마도 모두) 제거된 포화 이진 트리다. 어떤 저술자는 완전(complete)라는 용어를 사용해 위에서 정의한 포화 이진 트리 대신, 이러한 종류의 트리를 거의 완전한(almost complete) 이진 트리 또는 대체로 완전한(nearly complete) 이진 트리라고 하는 경우도 있다. 완전 이진 트리는 배열을 사용해 효율적으로 표현 가능하다.
무한 완전 이진 트리(無限完全二進-, 영어: infinite complete binary tree)에서, 모든 노드는 두 개의 자식 노드를 갖는다(그래서 레벨 집합은 가산 무한이다). 모든 노드 집합은 가산 무한이지만, 루트로부터의 모든 무한한 경로 집합은 연속체의 원소 개수를 가지고 있어 셀 수 없다. 이러한 경로는 칸토어 집합의 점 또는 (Stern-Brocot 트리의 예를 사용해) 양의 무리수 집합과 일치한다.
균형 이진 트리(均衡二進-, 영어: balanced binary tree)는 잎 노드에 대해 가능한 한 최대의 최소 높이(다른 말로 깊이)를 갖는데, 주어진 수의 잎 노드에 대해, 잎 노드가 가능한 가장 큰 높이에 위치하기 때문이다.
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 일반적으로 알려진 균형 트리 구조는 모든 노드의 왼쪽과 오른쪽의 하위 트리와의 높이가 1 이상 차이가 나지 않는 이진 트리 구조다. 또 다르게는 루트로부터 어떤 다른 잎 노드보다 훨씬 더 멀리 떨어진 잎 노드가 없는 이진 트리라고 생각할 수 있다(다른 균형 체계에서는 "훨씬 더 멀리"의 다른 정의가 가능하다).

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

이진 트리의 속성 편집

정 이진 트리에서 노드 개수 $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 _{2}n\rfloor$ 이고 내부 노드의 개수는 $\lfloor n/2\rfloor$ 다.
$n_{0}$ 개의 잎 노드와 차수(degree)가 2인 $n_{2}$ 개의 노드를 가진 비어있지 않은 이진 트리에 대해, $n_{0}=n_{2}+1$ 가 성립한다.
이진 트리의 노드의 수가 $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}}$ 이다.

이진 트리 탐색 편집

이진 트리의 모든 노드를 방문하는 것 혹은 방문하여 어떤 작업을 하는 것을 이진 트리 탐색이라고 한다. 이진 트리 탐색의 방법에는 여러 가지가 있으며, 다음의 방법들이 유명하다.

in-order(중위 순회) : 왼쪽 자식노드(L), 내 노드(P), 오른쪽 자식노드(R) 순서로 방문한다.
pre-order(전위 순회) : 내 노드(P), 왼쪽 자식노드(L), 오른쪽 자식노드(R) 순서로 방문한다.
post-order(후위 순회) : 왼쪽 자식노드(L), 오른쪽 자식노드(R), 내 노드(P) 순서로 방문한다.
level-order(레벨 순회) : 내 노드(P), 내 노드로부터 깊이 1인 노드들, 내 노드로부터 깊이 2인 노드들, ... , 내 노드로부터 깊이 N인 노드들 (N: 나(트리)의 깊이)

표현 방법 편집

이진 트리를 표현하는데는 크게 두 가지 방법이 있다.

1차원 배열 표현: 이진 트리의 i번째 노드를 배열의 i번째 요소에 저장하는 방법이다.

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

연결리스트 표현: 왼쪽 자식을 가리키는 포인터 필드와 오른쪽 자식을 가리키는 포인터 필드를 포함하는 노드로 표현하는 방법이다.

장점: 기억 장소를 절약할 수 있고, 노드의 삽입과 삭제가 용이하다.
단점: 이진 트리가 아닌 일반 트리의 경우에는 각 노드의 차수만큼 가변적인 포인터 필드를 가져야 하기 때문에 접근상의 어려움이 따른다.

위키미디어 공용에 관련된
미디어 분류가 있습니다.

이진 트리