[Data Structure] 트리(tree)와 이진 트리(binary tree)

---

트리

 

 

트리는 일대다로 연결된 비선형자료구조로 계층적 자료구조이다. 노드로 구성되어 있으며 다음과 같은 용어를 사용한다.

• 루트 노드(root node): 최상위 노드, 즉 부모가 없는 노드로 트리의 시작점
• 부모 노드(parent node): 해당 노드의 위(루트 노드 방향)로 연결된 노드
• 자식 노드(child node): 해당 노도의 아래(루트 노드 반대 방향)로 연결된 노드
• 형제 노드(siblings node): 같은 부모 노드를 갖는 노드들
• 조상 노드(ancestor node): 해당 노드 위로 연결된 모든 노드
• 후손 노드(descendent node): 해당 노드 아래로 연결된 모든 노드
• 단말 노드(terminal node): 자식이 없는 노드, 리프 노드(leaf node)라 부르기도 함
• 간선(edge): 노드를 연결한 선
• 레벨(level): 트리의 각 층의 번호로 루트 노드가 1이고, 자식 노드로 이동할 때마다 1씩 증가한다고 보면 됨
• 높이(height): 트리의 최대 레벨
• 깊이(depth): 자신을 제외한 조상 노드의 수
• 차수(degree): 노드가 가지고 있는 자식 노드의 수, 이진 트리라면 차수는 2
• 서브트리(sub tree): 하나의 노드와 그 노도들의 후손들로 이루어진 트리

트리의 예로는 디렉토리 구조, 책의 목차 등이 있다.

 

---

이진 트리

 

 

모든 노드의 차수가 2인 트리이다. 때문에 차수가 정해져 있지 않은 트리에 비해 구현이 수월하다. 배열과 이중연결리스트를 활용하여 구현 가능하다.

이진 트리는 노드의 개수가 $ n $ 개 일 때 간선의 개수가 $ n-1 $ 개 이고, 높이가 $ h $ 일 때 최소 $ h $ 개의 노드를 가지며, 최대 $ 2^h-1 $ 개의 노드를 가진다. 높이는 $ n $ 개의 노드를 가질 때 최소 $ \lceil \lg (n+1) \rceil $ 이고, 최대 $ n $ 이다.

이진 트리는 생긴 것에 따라 포화 이진 트리(full binary tree), 완전 이진 트리(complete binary tree), 그 외 이진트리로 나뉜다. 포화 이진 트리는 빈 곳 없이 꽉찬 트리로, 높이가 $ h $ 일 때 노드의 개수가 $ 2^h - 1 $ 이어야 한다. 완전 이진 트리는 최하단, 즉 마지막 레벨을 제외하고 모든 노드가 차있고, 최하단 노드들은 왼쪽부터 채워져있는 트리이다.

차례대로 포화 이진 트리, 완전 이진 트리, 포화 이진 트리도 완전 이진 트리도 아닌 이진 트리이다.

 

---

ADT

 

객체 (Object)

• 하나 이상의 노드들이 부모-자식 관계로 구성된 계층적 자료구조

연산 (Operation)

• init() ::= 트리를 초기화한다.
• is_empty() ::= 트리가 비어 있다면 true를, 비어 있지 않다면 false를 반환한다.
• insert_parent(parent, item) ::= 특정 부모 노드 parent의 자식으로 item을 추가한다.
• delete(node) ::= node를 트리에서 삭제하며, 이 노드의 자식 트리들은 삭제된다.
• search(item) ::= 트리에서 특정 값 item을 가진 노드를 탐색하여 반환한다.
• get_root() ::= 트리의 루트 노드를 반환한다.
• get_parent(node) ::= node의 부모 노드를 반환한다.
• get_children(node) ::= node의 자식 노드들을 반환한다.
• inorder_traversal() ::= 트리를 중위 순회하여 방문한 노드 값을 순서대로 반환한다.
• preorder_traversal() ::= 트리를 전위 순회하여 방문한 노드 값을 순서대로 반환한다.
• postorder_traversal() ::= 트리를 후위 순회하여 방문한 노드 값을 순서대로 반환한다.
• level_order_traversal() ::= 트리를 레벨 순서로 순회하여 방문한 노드 값을 순서대로 반환한다.
• get_height() ::= 트리의 높이를 반환한다.
• get_size() ::= 트리의 총 노드 개수를 반환한다.
• get_depth(node) ::= 특정 노드 node의 깊이를 반환한다.

 

---

구현 | C

 

이진 트리는 배열과 이중연결리스트를 활용하여 구현 가능하다고 앞서 소개하였다.

배열로 구현하는 방법은 모든 이진 트리를 포화 이진 트리라 가정하고 각 노드에 번호를 붙여 그 번호를 배열의 인덱스로 삼아 저장하여 구현한다. 번호를 붙이는 방법은 루트 노드를 1, 루트 노드의 왼쪽 자식 노드를 2, 오른쪽 자식 노드를 3, 2 노드의 왼쪽 자식 노드를 4, 이런식으로 위에서 아래로, 왼쪽부터 오른쪽으로 차례로 번호 붙이는 방법을 사용한다.

이때 $ i $ 번 노드의 부모 노드의 인덱스는 $ \lfloor i / 2 \rfloor $ 이고, 왼쪽 자식 노드의 인덱스는 $ 2 \times i $ 이며, 오른쪽 자식 노드의 인덱스는 $ 2 \times i + 1 $ 이다.

예를 들어 위 그림과 같은 트리를 배열로 구현하면 다음과 같다. 공백은 -1 로 임의로 처리하였다.

int tree = {0, 9, 7, 12, 2, 8, -1, 14};

이중연결리스트를 활용하여, 즉 노드를 만들고, 포인터를 이용하여 부모 노드가 자식 노드를 가리키도록 구현하면 다음과 같다.

typedef struct TreeNode {
    int data;
    struct TreeNode* left;
    struct TreeNode* right;
} TreeNode;

TreeNode n1, n2, n3, n4, n5, n7;
n1 = {9, &n2, &n3};
n2 = {7, &n4, &n5};
n3 = {12, NULL, &n7};
n4 = {2, NULL, NULL};
n5 = {8, NULL, NULL};
n7 = {14, NULL, NULL};