5-2강 - Binary Trees (이진 트리)

이전 5-1강에서 저희는 어떠한 tree든지 binary tree로 표현할 수 있다고 배웠습니다.

https://intelligentcm.tistory.com/155

 

2. Binary Trees

0) binary tree에 대한 소개

1> binary tree의 특징

- 모든 tree는 binary tree로 표현할 수 있다.

- 모든 node의 degree <= 2

- 왼쪽 subtree와 오른쪽 subtree를 구분합니다.

- 0개의 node를 가질 수 있다. (이전에 tree는 1개 이상의 node를 가져야했다.

 

=> 그래서 Binary Tree는 Tree와 다른 객체입니다.

(Binary Tree는 [1] empty tree가 가능하며 [2] subtree를 구분합니다.)

 

2> 다른 binary tree (binary tree은 left와 right를 구분한다.)

3> special tree (skewed tree, complete binary tree)

- (a) : skewed tree

- (b) : complete binary tree

 

 

1) The Abstract Data Type

1> Object : 

node의 유한 집합

[1] empty [2] root node, left Binary_Tree, right Binary_Tree로 구성

2> Function

- BinTree Create() : empty binary tree 생성
- Boolean IsEmpty(bt) : if (bt == empty binary tree) return TRUE | else return FALSE
- BinTree MakeBT(bt1, item, bt2) : bt1이 left subtree, bt2가 right subtree, root node에 item을 가진 binary tree 생성

- BinTree Lchild(bt) : if IsEmpty(bt) return error | else return the left subtree of bt

- BinTree Rchild(bt) : if IsEmpty bt return error | else return the right subtree of bt

- element Data(bt) : if IsEmpty(bt) return error | else return the data in the root node of bt

2) Binary Tree의 성질

1> Maximum number of nodes

- binary tree level i에서 최대 node의 개수 = 2^(i-1)개

- depth가 k인 binary tree의 최대 node의 개수 = 2^k - 1개

 

2> the number of nodes with degree

(n_0 : degree가 0인 node (leaf) 개수 / n_2 : degree가 2인 node 개수)

n_0 = n_2 + 1

 

3> the defintion of full binary tree

depth = k, node의 개수 = 2^k - 1인 tree

 

3) Binary Tree Representation (이진 트리의 표현)

1> Array 표현

위에서 붙은 index 순서대로 array에 배치한다. => tree[2^t-1]

- i != 1이면 → tree[i]의 parent는 tree[i/2]이다. (i=1이면, root이므로 부모가 없다.)

- 2i <= n이면 → tree[i]의 left_child는 tree[2i]에 있다. 2i > n이면 → tree[i]는 왼쪽 자식이 없다.

- 2i+1 <=n이면 → tree[i]의 right_child는 tree[2i+1]에 있다. 2i+1 > n이면 → tree[i]는 오른쪽 자식이 없다.

(full이라면 tree[i]의 left_child는 tree[2i]에 있고, right_child는 tree[2i+1]에 있다.)

 

하지만 그림에서 보는 것처럼 array representation은 (특히, (a)와 같은 case) 메모리 낭비가 심할 수 있다.

 

2> Linked 표현

각 Node structure는 [1] data [2] node pointer (left child) [3] node pointer (right child) 를 가진다.

typedef struct node *nodePointer;
typedef struct node{
	int data;
	nodePointer leftChild, rightChild;
};