트리2

[이진 트리]

• 트리 중에서 가장 많이 쓰이는 트리이다.

• 정의

- (1) 공집합이거나

- (2) 루트와 왼쪽 서브 트리, 오른쪽 서브 트리로 구성된 노드들의 유한 집합으로 정의된다. 이진 트리의 서브 트리들은 모두 이진트리여야 한다.

• 정의에서 ‘이진 트리’의 개념이 재귀적으로 들어간다는 점에 유의하자! 이진트리의 서브 트리도 이진트리의 성질을 만족하여야 한다는 것!

• 위 그림은 이진트리인지를 알아보자.

• 먼저 SUB3을 보자. SUB3은 하나의 노드 D로만 이루어져 있다. 만약 노드 D를 SUB3의 루트라고 생각하면 D의 왼쪽, 오른쪽 서브트리는 공집합이다. 하지만 정의 (1)에 의해서 공집합도 이진트리이므로 정의 (2)에 의하여 SUB3은 루트와 공집합 서브트리 2개를 갖는 이진트리이다.

• SUB1은 SUB1의 루트노드 B와 서브트리 SUB3과 공집합 서브트리를 갖고 있으므로 역시 이진트리이다.

• 최종적으로 전체 트리는 루트노드 A와 SUB1과 SUB2 두 개의 서브트리를 갖고 있는데, 이 두 개의 서브트리가 이진트리이므로 전체 트리도 이진트리라고 결론내릴 수 있다.

[이진트리의 성질]

• n개의 노드를 갖은 이진트리는 n-1개의 간선을 갖는다.

• 높이가 h인 이진트리의 경우 최소 h개의 노드를 가지며, 최대 2h-1개의 노드를 갖는다.

• n개의 노드를 가지는 이진트리의 높이는 최대 n이거나 최소 ⌈log2(n+1)⌉개이다.

 

[포화이진트리]

• 용어 그래도 트리의 각 레벨에 노드가 꽉 차 있는 이진트리를 의미

• 즉 높이 K인 포화 이진트리는 정확하게 2K-1개의 노드를 갖는다.

 

[완전이진트리]

• 높이가 K일 때 레벨 1부터 K-1까지는 노드가 모두 채워져 있고 마지막 레벨 K에서는 왼쪽부터 오른쪽으로 노드가 순서대로 채워져 있는 이진트리이다.

• 마지막 레벨에서는 노드가 꽉 차 있지 않아도 되지만 중간에 빈 곳이 있어서는 안 된다.

• 따라서 포화 이진트리는 완전 이진트리이지만 그 역은 항상 성립하지 않는다.

    

<포화이진트리>                           <완전이진트리>                           <기타이진트리>