[DataStructure] Binary Tree

토즐라·2022년 5월 4일
0

이번 글은 서강대학교 소정민 교수님의 강의와 Ellis Horowitz의「Fundamentals of Data Structures in C」를 바탕으로 작성했음을 밝힙니다.

From Textbook

A binary tree is a finite set of nodes that is either empty or conists of a root and two disjoint binary trees called the left subtree and the right subtree

From Wiki

이진 트리(Binary Tree)는 각각의 노드가 최대 두 개의 자식 노드를 가지는 트리 자료 구조로, 자식 노드를 각각 왼쪽 자식 노드와 오른쪽 자식 노드라고 한다.

1.1 ADT

  • Object: a finite set of nodes either empty or consisting of a root node, left Binary_Tree and right Binary_Tree
  • Functions: BinTree Create(), Boolean IsEmpty(bt), BinTree MakeBT(bt1, item, bt2), BinTree Lchild(bt), element Data(bt), BinTree Rchild(bt)

1.2 Properties

먼저, root node의 level이 0이라고 가정합니다. Tree 자료구조를 다룰 때에는, level과 depth, height가 0부터 시작하는지 1부터 시작하는지 잘 가정해야 합니다. 교과서마다 가정이 다르고, 가정이 달라지면 공식들의 내용도 전부 바뀌기 때문입니다.

먼저, i 레벨에서 가질 수 있는 최대 node의 개수는 2i2^i 입니다. 만약 level이 3이면, 가질 수 있는 최대 node의 개수는 8개입니다.

다음으로, depth가 k인 이진 트리가 가질 수 있는 총 node의 갯수는 2k+112^{k+1}-1개입니다. 3의 depth를 가진 이진 트리는 총 15(16-1)개의 node를 가질 수 있습니다.

1.2.1 Full Binary Tree


맨 마지막 level의 node들을 제외하고 모든 node들이 자식이 두 개인 경우, 이를 Full Binary Tree라고 부릅니다. k의 depth를 가진 Full Binary Tree는 2k+112^{k+1}-1개의 node를 가지고 있습니다.

Full Binary Tree는 모든 node들에 번호를 매길 수 있는데, 위의 그림처럼 1부터 시작해서 위에서 아래로, 동 level에 여러 개의 node가 있으면 왼쪽에서 오른쪽으로 진행하면서 번호를 매깁니다.

1.2.2 Complete Binary Tree

A binary tree with n nodes and depth k is complete iff its nodes correspond to the nodes numbered from 1 to n in the full binary tree of depth k.

보통 Binary Tree 자료구조를 다룰 때, Complete Binary Tree라는 가정을 많이 하게 됩니다.

Complete binarry tree란, 위의 그림과 같이 중간에 node의 번호가 끊기지 않고 연속적으로 이어지는 tree를 뜻합니다. 즉, 번호가 level 0부터 가득 채워져야 하고, 맨 마지막 레벨은 가득 채워질 필요가 없지만, 왼쪽부터 채워진 tree인 것이죠.


1.3 Representations

1.3.1 Array Representation

먼저 full binary tree를 가정하고, 그 때 해당하는 Node의 번호를 index로 넣고 array를 만듭니다.

Array Representationd은 부모와 자식이 몇 번 node에 위치하는지 알 수 있다는 장점이 있습니다. i번 node의 parent node는 tree[i//2]에 위치합니다. 또, i번 node의 왼쪽 child는 tree[2i]번에, 오른쪽 node는 tree[2i+1]에 위치합니다.

1.3.2 Linked List Representation


Binary Tree 를 Linked List로 표현할 때, 각각의 node는 하나의 데이터와 두 개의 link를 가지고 있습니다. n개의 node를 지닌 binary tree는 n * (sizeof(node))만큼의 공간이 필요합니다. 다음은 C 코드로 구현한 binary tree의 node입니다.

struct node {
	char data;
	struct node *left_child, *right_child;
};
typedef struct node *tree_pointer;
profile
Work Hard, Play Hard 🔥🔥🔥

0개의 댓글