[자료구조] - 트리(Tree)[3] - 이진 트리(Binary Tree)

 

이진트리 (Binary Tree)

이진트리는 다음과 같이 정의됩니다.

비어있거나(노드가 0개), 혹은 
루트(Root)와 두개의 서로 겹치지 않는 이진 트리로 구성되며, 각각 왼쪽 서브트리(left subtree)와 오른쪽 서브트리(right subtree)라 합니다.

 

이론적인 측면에서 노드가 없는 경우 

트리는 노드가 하나 이상 존재해야 하므로 트리가 아니지만,

이진트리는 비어있을 수 있으므로 이진트리는 맞습니다.

 

이진트리는 다음과 같이 생겼습니다.

 

 

 

 

 

 

 

 

 

트리와 이진트리의 차이점

 

 

1. 노드의 최소 개수

트리는 노드가 하나 이상이어야 하지만
이진트리는 노드가 0개여도 됩니다.

 

 

2. 서브트리의 순서

트리의 서브트리에는 순서도, 위치도 존재하지 않습니다.
이진트리의 서브트리에는 위치와 순서가 있습니다.

 

예를 들어 다음 두개의 트리를 살펴보도록 하겠습니다.

만약 이들이 트리인 경우, 이들은 서로 같습니다.

그러나 이진트리라면 이들은 서로 다릅니다.

 

 

 

 

 

 

 

 

 

 

 

 

 

이진트리의 종류

 

치우친(Skewed / Degenerate) 이진트리

트리가 한 방향으로 기울어진 트리입니다.

 

 

 

 

 

 

 

 

완전이진트리 (Complete Binary Tree)

마지막 레벨을 제외하고 모든 레벨에서 노드가 완전히 채워져 있습니다.
마지막 레벨은 꽉 차 있지 않아도 되지만, 노드가 왼쪽에서 오른쪽으로 채워져야 합니다. 

 

 

 

 

 

 

포화이진트리 (Full Binary Tree)

모든 레벨에서 노드가 완전히 채워진 트리입니다.

 

 

 

 

 

 

 

 

 

 

 

 

이진트리의 레벨과 노드 수와의 관계

루트의 레벨을 1로 보았을 때, 레벨 i에 있을 수 있는 노드의 최대 개수는 다음과 같습니다.

$$2^{i-1}$$

 

 

또한

 

 

루트의 레벨을 1로 보았을 때, 깊이(높이)가 k인 이진트리가 가질 수 있는 노드의 최대 개수는 다음과 같습니다.

$$2^{0}+2^{1}+2^{2}+\cdots + 2^{k-1}$$
$$=2^{k} - 1$$

 

 

 

역으로 완전 이진트리의 노드의 개수가 n일 때  높이는 다음과 같습니다.

$$[log_2(n)] + 1$$

 

 

 

 

 

 

 

 

 

 

잎노드 수와 차수가 2인 노드 수와의 관계

잎노드의 개수를 $n_0$, 차수가 2인 노드의 수를 $n_2$ 라고 하면 다음이 성립합니다.
$$n_0 = n_2 + 1$$

 

증명

 

 

 

 

 

 

 

 

 

 

Left Child -Right Sibling 표현과의 관계

트리를 Left Child - Right Sibling 로 표현하는 것은 컴퓨터의 관점에서 보자면 결국 Left 노드와 Right 노드를 가진 이진 트리를 보는 것과 같습니다.

물론 트리에서의 child와 sibling의 관계는 달라집니다만, child와 sibling이 중요한 것이 아니라면 left child - right sibling을 이진 트리로 볼 수 있습니다.

 

 

left child - right sibling을 시계 방향으로 45도 회전하면 이진트리가 됩니다.