[ 트리구조 ] 이진트리의 이해,

|

2. 트리구조의 종류

이진트리

트리구조 중에서 구조가 간단하며, 쉽게 그 구조를 유지하고, 메모리를 적게 사용하는 이진트리가 있다.

이진트리를 크게 구분해보면, 기본적인 성질을 만족하는 이진트리와 이진트리를 좀 더 효율적으로 사용하고자 하여 만들어진 스레드이진트리, 허프만트리, AVL트리로 나눌 수 있다.

 

기본적인 이진트리의 정의는 다음과 같다.

이진트리(binary tree) T는 다음 성질을 만족하는 노드들의 유한 집합이다.

① T가 공백(empty) 이거나,

② T가 루트 노드를 포함하고, T의 나머지 노드들이 서로 분리된 두 개의 이진트리 의 순서쌍을 구성한다. 즉 T는 루트노드와 왼쪽 부트리, 오른쪽 부트리로 구성된다.

참조 : 예제로 배우는 자료구조론 , 주낙근 , 이숙희, 최철재, 김정자 공저

기본적인 이진트리는 트리의 구조에 따라서 엄밀한 이진트리, 크누스 이진트리(Knuth binary tree),정이진 트리(Full binary tree), 전이진트리(Complete binary tree), 사향 이진 트리(Skewed binary tree)가 있다.

 

(1) 엄밀한 이진트리

트리를 구성하는 각 노드의 차수가 0 또는 2인 트리를 엄밀한 이진트리라고 부른다.

< 그림 5 > 엄밀한 이진트리 참조 / 참조 : 소프트웨어를 위한 자료구조론 p150

 

(2) 크누스 이진 트리( knuth binary tree )

트리를 구성하는 각 노드의 차수가 0,1,2인 트리를 말하며, 일반적인 이진트리를 의미한다.

< 그림 6 > knuth 이진트리 / 참조 : 소프트웨어를 위한 자료구조론 p150

 

(3) 정이진 트리 ( Full Binary tree )

포화 이진트리라고도 부르는 정이진 트리는 트리를 구성하는 각 노드의 차수가 0 또는 2로 구성된 트리이다.

< 그림 7 > 정이진 트리 / 참조 : 소프트웨어를 위한 자료구조론 p150

 

(4) 전이진 트리 ( Complete binary tree )

완전 이진 트리라고도 부르는 전이진 트리는 트리의 노피가 k인 이진 트리의 전체 노드 수가 n일 때, 레벨 1로부터 시작해서 하위 레벨 순서로 정이진 트리의 형태를 취하면서, 동일한 레벨에서는 왼쪽에서 오른쪽으로 순서대로 n개의 노드를 배열한 형태

참조 : 소트웨어를 위한 자료구조론 p151 , 김에녹, 박상규, 복혁규 공저

< 그림 8 > 전이진 트리 / 참조 : 소프트웨어를 위한 자료구조론 p151

 

(5) 사향 이진트리 ( Skewed binary tree )

트리르 구성하는 노드들이 한쪽 방향으로만 모여 있는 트리 형태

< 그림 8 > 사향 이진트리 / 참조 : 소프트웨어를 위한 자료구조론 p151

 

 

이진트리는 다음과 같은 3가지의 기본적인 성질을 만족한다.

① 이진트리의 레벨 에서의 최대 노드 수 = ( i 1 )

② 깊이가 k인 이진트리의 최대 노드수 = , ( k 1 )

③ T를 공백이 아닌 이진트리, 을 단말 노드 수, 를 차수가 2인 노드 수라 하자. 그러면

를 만족한다.

참조 : 예제로 배우는 자료구조론 , 주낙근 , 이숙희, 최철재, 김정자 공저

각 기본적인 성질에 대해서 그림으로 설명하면 다음과 같다.

 

① 이진트리의 레벨 에서의 최대 노드 수 = ( i 1 )

예를 들어 레벨에 따라 이진트리 중 노드값을 최대로 갖는 노드를 그려보면 다음과 같다.

레벨이 2인

노드들의 개수

= 2개

레벨이 3인

노드들의 개수

= 4

레벨이 4인 노드들의 개수

= 8

레벨이 5인 노드들의 개수

= 16

< 그림 9 > 이진트리의 최대 노드수 구하기.

 

② 깊이가 k인 이진트리의 최대 노드수 = , ( k 1 )

깊이가 2인

노드의

최대 노드수 =

3개

깊이가 3인

노드의

최대 노드수 =

7개

깊이가 3인 노드의 최대 노드수 =

3개

깊이가 4인 노드의 최대 노드수 =

15개

< 그림 10 > 이진트리의 최대 노드수 구하기.

 

③ T를 공백이 아닌 이진트리, 을 단말 노드 수, 를 차수가 2인 노드 수라 하자. 그러면

를 만족한다.

 

 

차수가 2인 노드 = 2

단노드의 수 = 3

 

차수가 2인 노드 = 4

단노드의 수 = 5

< 그림 9 > 이진트리의 최대 노드수 구하기.




Trackback 0 And Comment 0
prev | 1 ... | 49 | 50 | 51 | 52 | 53 | 54 | 55 | 56 | 57 ... | 64 | next

티스토리 툴바