Tree
- Definition : root를 가지고, Cycle을 만들지 않는 Graph를 Tree라고 한다.
* 특징
- Root가 아닌 모든 노드들은 parent와 child를 가진다.
// ex) president 노드를 제외한 모든 노드
- children이 존재하지 않는 노드를 leaves라고 한다.
// ex) leaves : Manager1, Manger2, Worker Bee, Manager
- level은 계층 구조를 나타낸다.
// root부터 낮은 level로 시작하여 leaves에서 가장 높은 level로 끝을 낸다.
- 빈 Tree란 존재할 수 없다.
Binary Tree
- Definition : 두 개의 child를 가지는 Tree
* 특징
- 두 child를 left child & right child로 구분 가능
- binary tree는 empty가 가능하다.
* Tree & Binary Tree 차이점
위 a, b의 관계가 a = parent, b = child일 때
Tree는 left& right 구분이 없기에 그냥 child라고 하지만
Binary Tree는 left & right child 구분이 있기에 b를 right child라고 한다.
=> Binary Tree가 left& right child로 구분 할 수 있는 것이 큰 차이점이다.
Skewed binary Tree & Complete binary Tree
Skewed binary Tree : binary tree 성질을 가지는데 left 또는 right 한 쪽으로만 tree가 형식된 것이다.
//(a)는 left Skewed binary Tree라고 할 수 있다.
Complete binary Tree : binary tree 성질을 가지는데 가장 높은 level을 제외하고 그 아래 level은 부모 아래 left & right child가 모든 존재한다.
그리고 가장 높은 level일 경우 왼쪽으로부터 순차적으로 노드가 구성되어 있으면 Complete binary tree이다.
//(b)는 1~3 level은 모든 parent 아래에 left & right child가 존재하고, 4 level은 왼쪽으로부터 순차적으로 H, I 노드가 구성되어 있기에
Complete binary tree라고 할 수 있다.
//만약 (b)의 I 노드가 E의 left child라고 하고, D의 right child가 비어있다고 가정한다면, Complete binary tree가 아니다.
왜냐하면 가장 높은 level에서 node들이 좌측에서 순차적으로 구성된 것이 아니기 때문이다.
Minimum & Maximum Number of Nodes
Binary Representation
binary Tree를 나타내는 방식으로는 Arrary Representation과 Linked Representation이 있다.
- Array Representation
배열을 만들어서 이를 좌측 그림과 같이 표현하는 형식
아주 큰 배열을 선언하여 Tree를 구성하여 표현하는 편이 편하다.(꽉 찰 때마다 늘려주는 방식도 존재)
=> Tree를 배열로 구성하였을 때 아래와 같은 식이 성립하게 된다.
(부모 index) * 2 = (left child index)
ex) tree[1*2] = tree[2]
(부모 index) * 2 + 1= (right child index)
ex) tree[3*2 + 1] = tree[7]
(left child index) / 2 = 부모 index
ex) tree[8/2] = tree[4]
(right child index) / 2 = 부모 index
ex) tree[9/2] = tree[4]
=> 장점 : complete binary tree일 경우 선언된 배열의 모든 index를 사용하기에 사용하기 편함
=> 단점: skewed된 tree 등 여러 다른 tree에는 사용하는 것이 비효율적이다.
아래와 같이 중간 중간이 비기 때문이다.
- Linked Representation
root 포인터 / left child 포인터 / right child 포인터를 이용하여 그림과 같이 연결시킨다.
하나의 Node에 Data / Right 포인터 / Left 포인터 존재
-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
참고 자료
- 광운대학교 컴퓨터정보공학부 / Data Structure / 이기훈 교수 / 2017
- Introduction to Algorithm / 로널드 라이베스트, 클리포드 스테인, 토마스 H. 코만 / 3rd edition
-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
혹시 궁금한 사항이 있으시거나 게시글에 잘못된 점이 있다면 댓글을 달아주세요.