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

이진트리(Binary Tree)란?

이진트리(Binary Tree)란 트리 중에서도 각 노드가 최대 2개의 자식노드를 가질때 이진트리라고 한다.

최대 2개의 자식노드를 가질때이기 때문에 자식이 없을수도 있고, 한개만 있을수도 있다

이진트리 구분

 

 

이때 자식노드는 각각 왼쪽 자식노드와 오른쪽 자식노드로 표현한다.

그래서 같은 루트에 같은 자식노드 하나를 가지고있어도, 자식노드의 위치가 왼쪽과 오른쪽이 다르다면 이 두 트리는 서로 다른 트리가된다.

아래 그림은 A라는 같은 루트노드를 가지고있지만, 자식노드의 위치가 왼쪽,오른쪽 다르기때문에 두개의 트리는 별개의 트리(서로 다른 트리)가 된다.

왼쪽 자식노드, 오른쪽 자식노드 (서로 다른 트리)

 

 

 

 

 

 

 

이진트리(Binary Tree)의 종류

1. 정 이진트리(Full Binary Tree / Strict Binary Tree)

 

이진트리(Binary Tree)중에서도 모든 노드가 2개의 자식을 가지거나, 자식이 없는 경우에는

정 이진트리(Full Binary Tree) 혹은 엄격한 이진트리(Strict Binary Tree) 라고한다.

즉, 자식이 한개인 경우가 없어야 정이진트리라고 할 수 있다.

 

아래 그림에서는 자식을 하나만 가지는 노드가 있기때문에 정이진트리가 될수없다.

(C의 자식이 F하나만 있기 때문)

정 이진트리(X)

 

 

아래 그림에서는 모든 노드들이 자식을 두개가지거나, 아예 가지고있지 않기때문에 정이진트리가 될 수 있다.

정 이진트리(O)

 

 

 

 

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

이진트리중에서도 모든 노드가 2개의 자식을 가지고, leaf노드가 모두 같은 레벨일때는 포화이진트리 라고한다.

 

포화 이진트리는 높이가 k인 포화 이진트리에서 노드의 개수는 아래와같은 특징을 갖는다

 

포화 이진트리

 

그림에서보듯이 포화이진트리에서는 모든 레벨의 노드가 꽉차있기때문에, 자식노트의 개수가 2의 제곱만큼 계속 증가하게된다.

루트부터 시작해서 각 레벨별로 2의0제곱, 2의1제곱, 2의2제곱과 같은 순서대로 자식노드가 생성되기떄문에,

이것을 수식으로 표현하면 2의 K+1제곱의 -1로 표현할 수 있는것이다.

그리고 포화이진트리에서 leaf노드의 개수는 2의 k제곱이 된다는 특징도 있다.

 

 

 

 

 

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

완전 이진트리는 두가지 조건을 충족해야한다

1. 마지막 레벨을 제외하고 모든 노드가 채워져있어야한다 (마지막 레벨의 노드는 다 채워져있을수도 있고, 아닐수도 있음)

2. 노드는 왼쪽에서 오른쪽 방향으로 채워져야한다.

그래서 어느 노드에 오른쪽 자식이 존재한다면, 반드시 왼쪽 자식도 있어야지 완전 이진트리라고 볼 수 있다.

 

완전 이진트리 (O)

 

위의 그림에서 노드는 왼쪽에서 오른쪽 방향으로 채워져야한다는 조건을 만족하기때문에, 완전 이진트리라고 할 수있다.

 

앞에서 봤던 포화이진트리도 완전이진트리의 조건을 모두 충족하기 때문에, 포화이진트리도 완전이진트리에 속할 수 있다.

그치만 완전 이진트리라고해서 포화 이진트리라는 역은 성립하지 않는다.

 

 

 

완전 이진트리 (X)

 

위의 왼쪽트리에서 오른쪽 자식노드는 있지만, 왼쪽 자식노드가 비어있기 때문에 완전 이진트리가 성립하지 않는다.

오른쪽 트리 역시 왼쪽부터 채우고있지 않기때문에, 완전 이진트리가 성립하지 않는다.

 

 

 

 

 

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

균형 이진트리는 왼쪽과 오른쪽 트리의 높이차이가 모두 1만큼 나는 트리이다.

균형 이진트리(O)

 

위의 그림은 왼쪽높이2, 오른쪽높이 1로 둘의 높이차이가 1만큼 나기때문에 균형 이진트리라고 할 수 있다.

 

 

 

균형 이진트리(X)

 

위의 그림은 왼쪽과 오른쪽의 높이차이가 2만큼 나기때문에 균형 이진트리라고 볼 수 없다.

 

 

 

 

 

 

이진트리의 특징

1차원 배열로 표현할 수 있다!!

 

이진트리는 트리이지만, 선형자료구조인 1차원 배열로도 표현할 수 있다는 특징이 있다!!

1차원 배열로 이진트리를 표현할때는 0번쨰 인덱스는 비워두고, 첫번째 인덱스부터 루트값이 들어가는 특징이 있다.

 

완전 이진트리의 1차원 배열 표시

 

위의 그림처럼 트리를 1차원배열로 표시한다고했을때, 루트에서 시작해서 왼쪽노드부터 오른쪽노드까지 순서를 매기면, 완전이진트리 같은경우에는 빈숫자가 없게 된다.

그래서 완전이진트리는 각 번호를 인덱스로 써서 1차원 배열로 표현이 가능하다.

즉, 완전 이진트리는 1차원 배열에서 이렇게 빈틈없이 값을 채운 배열이 될 수 있다.

 

중간에 빈값이 있는 이진트리는, 1차원배열로 표현했을때 비어있는 공간의 인덱스에 null값으로 채워서 표현할 수 있다.

중간에 빈값이 있는 이진트리의 1차원 배열표현

 

 

 

 

1차원 배열로 이진트리를 표현할때는 0번째 인덱스는 비워두고, 첫번째 인덱스부터 루트값이 들어가는 특징이 있다고 했는데

이렇게 첫번째 인덱스부터 루트값을 넣으면, 인덱스 위치로 찾을수있는 연산이 있다.

 

이진트리의 연산

중간에 빈값이 있는 이진트리의 1차원 배열표현

 

위의 그림을 보고 살펴보면, 6번의 노드의 부모는 6나누기 2를 한 3번째 인덱스에 위치하게 되고,

노드 1의 왼쪽자식노드는 1*2를 한 2번째 인덱스에 위치하는것을 볼 수 있고,

노드 1의 오른쪽 자식노드는 1*2+1를 한 3번째 인덱스에 위치하는 것을 확인할 수 있다.

이를 수치화해서 식으로 정리하면 아래와 같이 정리할 수 있다.

 

이진트리의 연산

 

 

 

 

이진트리의 단점

이런식으로 1차원 배열로 이진트리를 표현하면, 간단하게 코드로 트리를 나타낼 수 있는 장점이 있지만,

배열의 한계인 공간의 제약이나 데이터삽입,삭제시에 기존 데이터의 이동과 같은 단점은 여전히 극복할 수 없기 때문에 

트리를 표현할때는 배열보다는 노드의 연결로만 거의 표현한다!

 

 

 

이진트리는 많은 응용트리의 기반이된다.

이진힙, 이진탐색트리, B-트리 등도 이진트리를 응용한 트리이다.

트리도 자료구조라서 트리에 데이터를 삽입,삭제하는 기본 연산을 하는데, 트리에는 트리탐색이라는 연산이 추가된다.

선형적 자료구조와는 다르게 트리는 구조특성상 데이터를 탐색하는 방법이 다르기때문에, 다음 게시글에서는 트리구조에서는 데이터탐색을 어떻게하는지 작성해봐야겠다.