이진트리(binary tree) & 트리탐색(BFS, DFS)

이진트리(binary tree)

모든 노드가 2개 이하의 자식을 가지는 트리를

이진트리라 합니다.

 

자식노드가 항상 2개 이하이기 때문에

이진트리는 왼쪽 자식과 오른쪽 자식으로 자식노드들을 구분합니다.

이진트리의 서브트리는 자식노드와 같이

왼쪽 서브트리와 오른쪽 서브트리로 구분됩니다.

 

왼쪽 서브트리는 왼쪽 자식을 루트로 하는 서브트리이며,

오른쪽 서브트리는 오른쪽 자식을 루트로 하는 서브트리입니다.

 

 

 

 

 

 

 

 

 

 

 

포화이진트리(perfect binary tree) & 

완전이진트리(complete binary tree)

포화이진트리는 모든 레벨이

노드들로 꽉 차있는 이진트리를 의미하며,

 

완전이진트리는 마지막 레벨을 제외한 각 레벨이 노드들로 꽉 차있어야 하며,

마지막 레벨에는 노드들이 왼쪽부터 빠짐없이 채워져 있어야 합니다.

 

 

 

 

 

 

 

 

 

 

이진트리의 속성

이진트리의 레벨 k에 있는 최대 노드 수는 2^k 입니다.

 

또한 높이가 h인 이진트리가 가질 수 있는 최대 노드 수는 2^(h+1) - 1 입니다.

 

 

 

 

 

 

 

 

 

완전이진트리의 속성

높이가 h인 완전이진트리가 가질 수 있는 최대 노드 수는 2^(h+1) - 1 입니다.

(완전이진트리 역시 이진트리이므로 공식은 동일합니다)

 

높이가 h인 완전이진트리가 가질 수 있는 최소 노드 수는 2^h 입니다.

(높이가 h-1 인 완전이진트리의 최대 노드 수에서 1을 더하여 구합니다.)

 

즉, 높이가 h인 완전이진트리가 가질 수 있는 노드 수의 범위는 다음과 같습니다.

$$2^{h} \leq n < 2^{h+1}$$

 

반대로 n개의 노드를 가진 완전이진트리의 높이는 다음과 같습니다.

$$floor(log_{2}n)$$

(*floor 함수는 버림함수입니다*)

 

 

 

 

 

 

 

 

 

 

완전이진트리 구현

배열(파이썬 리스트)를 이용하여 완전이진트리를 구현할 수 있습니다.

 

하나의 트리를 하나의 리스트로 구현하는데

다음과 같은 규칙을 따라 구현합니다.

1. 인덱스가 0 인 자리는 비워둔다. (None)
2. 루트노드의 인덱스는 1이다.
3. a[i] 의 부모는 a[i//2] 에 위치합니다.
4. a[i] 의 왼쪽자식은 a[2i]에 위치합니다.
5. a[i] 의 오른쪽자식은 a[2i + 1]에 위치합니다.

그림으로 표현하면 다음과 같습니다.

 

 

 

 

하지만 완전이진트리가 아닌 이진트리를

배열을 이용하여 구현하고자 한다면 메모리 낭비가 발생할 수 있습니다.

 

 

 

 

 

 

 

 

 

 

트리탐색

트리구조를 구성한 후 탐색을 하는 방법은

크게 두가지로 나누어지게 됩니다.

 

 

 

 

너비우선탐색(BFS, breadth-first search)

말 그대로 폭을 우선으로 하여 검색합니다. (가로검색, 수평검색)

낮은레벨부터 시작하여 왼쪽부터 오른쪽으로 검색을 진행합니다.

 

즉, 한 레벨의 검색이 끝난 후 다음 레벨로 넘어가는 방식으로 탐색이 진행됩니다.

 

 

 

 

 

깊이우선탐색(DFS, depth-first search)

말 그대로 세로, 수직으로 검색합니다.

 

리프에 도달할 때까지 아래쪽으로 내려가면서 검색하는 것을 우선으로 합니다.

 

만약 리프에 도달하여 더 이상 내려갈 곳이 없으면, 다시 부모 노드로 돌아간 후

그 다음 자식노드로 내려갑니다.

 

다음과 같이 

 

"노드 방문 -> 왼쪽 자식 -> 오른쪽 자식"

 

순으로 검색하는 것을 트리 순회 중 전위순회라 합니다.