[k-mooc/자료구조] 07. 트리(Tree)

지금까지 공부한 자료구조는 공통적으로 리스트형 자료 구조로, 선형 자료 구조였기 때문에 모든 원소는 인덱스에 대응된다.

[prev] (i-1)번째 원소 → [curr] i번째 원소 → [next] (i+)번째 원소

 

 

개요

선형 자료구조의 한계

모든 원소들 사이에서 관계 비교가 가능하지만, 이 때 선후 관계는 a[i] < a[j] 처럼 동일한 관계만 표현한다.

8, 19, 23, 24, 48, 90       //오름차순으로 정렬된 리스트
가가가, 라라라, 하하하           //사전순으로 정렬된 리스트 

 

🤔 2개 이상의 관계를 표현할 수 있을까?

가가가(엄마), 라라라(딸), 하하하(동생)
//가가가 - 라라라: 모녀관계     
//라라라 - 하하하: 자매관계

위의 경우, 동일한 리스트에 있는 원소들이지만 원소들 사이의 관계가 항상 일정하지 않다. [예] Family Record
그래서 위와 같은 원소들 사이의 관계를 일정하게 표현하기 위한 자료구조가 트리 [예] Family Tree, File System

 

계층 구조의 공통점

https://www.geeksforgeeks.org/dsa/tree-data-structure/

하나의 근원(root)로부터 파생되어 노드 1개는 여러 개의 노드로 전파되며, 순환하는 경로가 없다.
이러한 계층 구조의 특징을 트리가 모두 가지고 있다.

 

 

07-1. 트리의 개념

https://www.geeksforgeeks.org/dsa/introduction-to-tree-data-structure/

1. 루트(root)라는 특별한 노드가 1개 존재
2. 모든 노드는 부모 자식 관계라는 1:1 관계에 대해 재귀적으로 연결됨
3. 순환하는 경로(Cycle Path) 없음

⇒ 이 세 가지 속성을 만족하는 노드(Node)와 엣지(Edge)의 집합이 트리

 

용어

	설명	예시
Node(Vertex)	하나의 정보 단위
Edge	연결된 노드의 쌍
Root Node	트리의 최상위 노드로, 부모 노드가 없음
Leaf Node	자식 노드가 없는 노드
Internal Node	Leaf Node가 아닌 노드
Parent Node	연결된 한 쌍의 노드 중 Root Node에 더 가까운 노드가 다른 노드의 Parent Node	—는 —의 parent node이다.
Child Node	연결된 노드 중 Root Node에서 더 먼 노드
Sibling Node	같은 노드를 Parent Node로 공유하는 노드들
Ancestor Node	Root Node로부터 어떤 Node에 이르는 경로에 있는 모든 노드들	A, B는 D의 조상 노드이다. A, B, E는 K의 조상 노드이다.
Descendent Node	Ancestor Node의 반대	D는 B의 후손 노드이다.
Subtree(부분 트리)	어떤 트리의 노드를 Root Node로 하며 트리의 정의를 만족하는 노드와 엣지의 집합
Degree of a node	한 노드가 갖는 자식 노드의 개수	Degree of A → 2, Degree of C → 3
Degree of a tree	한 트리에 속한 노드들의 Degree 중 최대값	Degree 기반 트리 정의: Binary Tree(2), Tenary Tree(3), K-ary Tree(k)
Depth of a node (노드의 깊이)	- Root node의 depth는 1, Child node는 parent node의 depth + 1 - Leaf node까지의 maximum distance
Depth(height) of a tree (트리의 깊이/높이)	한 트리에 속한 노드들의 depth 중 최대값

 

트리의 자료 구조

노드는 (1)저장할 데이터, (2)자식 노드의 수, (3)자식 노드에 대한 포인터를 저장해야 한다.

typeof class node *nptr;
class node {
	data_type data;
	int n_childs;
	nptr *childs;
}

 

 

---

💬 트리는 어떻게 자료를 효율적으로 관리하는지?

자료구조는 자료를 효율적으로 관리하는 기법이다.

트리의 원소를 찾는 기본적인 탐색 알고리즘이 BFS와 DFS가 있다.

그리고 이진 트리(Binary Tree)에서 특수한 이진 트리 중 임의의 원소(X)를 찾는 연산이 리스트보다 빠른 이진 탐색 트리와 리스트보다 TOP을 찾는 연산이 빠른 힙을 배우게 된다.

이 두 가지가 실제로 검색 성능이 좋고 자료를 추가/제거하는 과정이 훨씬 더 효율적으로 작동하는 자료구조!

 

 

 

 

---

 

07-2. 이진 트리(Binary Tree)

https://www.geeksforgeeks.org/dsa/introduction-to-binary-search-tree/

 

정의

Degree가 2인 트리로, 모든 노드는 최대 2개의 자식 노드를 가진다.
⚠️ ”최대” 2개이므로 모든 노드가 2개의 자식 노드를 가지는 것이 아니라, 0~2개의 자식 노드를 가지게 된다.

typeof class node *nptr;
class node {
	data_type data;
	nptr lchild, rchild; //왼쪽 자식 노드, 오른쪽 자식 노드에 대한 포인터
}

 

 

성질

1. i번째 레벨의 최대 노드 수는 \(2^{i-1}\)개
2. Depth가 k인 이진 트리의 최대 노드는 \(2^k-1\)개
3. 원소가 있는 이진 트리에 대해서 \(n_0\)를 leaft node의 수, \(n_2\)를 drgree가 2인 노드의 수라고 하면, \(n_0 = n_2+1\)이 성립한다.

(1) 모든 노드의 수를 n개라고 하면, n = n_0 + n_1 + n_2
(2) child node의 관점에서 보면, n = 2n_2 + n_1 + 1
(3) 따라서, n_0 + n_1 + n_2 = 2n_2 + n_1 + 1 => n_0 = n_2 + 1

 

 

특별한 이진 트리

(1) 포화 이진 트리(Full Binary Tree)

Depth가 k일 때, \(2^k-1\)개의 노드를 갖는 이진 트리 ⇒ 즉 최대 노드를 가짐

따라서 노드를 증가시키려면 반드시 depth를 증가시켜야 한다.

(2) 완전 이진 트리(Complete Binary Tree)

마지막 레벨을 제외하고 모든 레벨이 완전히 채워져 있으며 + 마지막 레벨의 노드는 왼쪽부터 채워야 한다.

https://www.techiedelight.com/check-given-binary-tree-complete-binary-tree-not/

오른쪽 트리는 왼쪽부터 채워야 하는 규칙을 위반했으므로 완전 이진 트리가 아니다.

 

 

트리 탐색(Tree Search/Traversal)

기존 search: 배열 A와 값 x를 주고, x가 A에 속하면 인덱스를 리턴하고 아니라면 null을 리턴한다.

📍 그러나 트리에서의 탐색은 루트 노드에서 시작하여 트리의 모든 노드를 방문하는 연산이다.

모든 트리에서 적용되는 일반적인 탐색으로 깊이 우선 탐색(DFS)과 넓이 우선 탐색(BFS)이 있지만, 이진 트리에서만 적용되는 특별한 탐색이 있다.

 

이진 트리에서의 탐색

노드와 그 자식 노드를 방문하는 순서에 따라서 3가지 탐색이 가능하다.

 

https://www.geeksforgeeks.org/dsa/tree-traversals-inorder-preorder-and-postorder/

 

(1) 중위 우선 탐색(Inorder Traversal)

왼쪽 자식 노드 → 부모 노드 → 오른쪽 자식 노드

void inorder(nptr bt) {
	if(bt) {
		inorder(br->lchild); //왼쪽 자식 노드 
		print(bt->data);     //부모 노드
		inorder(br->rchild); //오른쪽 자식 노드 
	}
}

[예]

//root에서 출발 (1)
inorder(1);

inorder(2); //(2)
inorder(4); //(4) --> 리프 노드 print: 4
//inorder(2)에서 inorder(4)종료(왼쪽) -> 부모 노드인 2 출력 --> print: 4 2
//inorder(2)에서 왼쪽 > 부모 > 오른쪽 노드 
inorder(5); //(5) --> 리프 노드 print: 4 2 5

//inorder(1)에서 inorder(2) 종료 -> 부모 노드인 1 출력 --> print: 4 2 5 1
//inorder(1)에서 왼쪽 > 부모 > 오른쪽 노드
inorder(3); //(3)
inorder(6); //(6) --> 리프 노드 print: 4 2 5 1 6

//inorder(3)에서 inorder(6) 종료 -> 부모 노드인 3 출력 --> print: 4 2 5 1 6 3
//inorder(3)에서 왼쪽 > 부모 > 오른쪽 노드
inorder(7); //(7) --> 리프 노드 print: 4 2 5 1 6 3 7 [종료]

 

(2) 전위 우선 탐색(Preorder Traversal)

부모 노드 → 왼쪽 자식 노드 → 오른쪽 자식 노드

void preorder(nptr bt) {
	if(bt) {
		print(bt->data);      //부모 노드
		preorder(br->lchild); //왼쪽 자식 노드  
		preorder(br->rchild); //오른쪽 자식 노드 
	}
}

[예]

//root에서 출발 (1)
preorder(1);

//부모노드 출력 print: 1
//왼쪽 노드로 
preorder(2);

//(2) 부모노드 출력 print: 1 2
//왼쪽 노드로
preorder(4);
//(4) 부모노드 출력 print: 1 2 4 -- 리프노드 (재귀 끝)
//오른쪽 노드로
preorder(5);
//(5) 부모노드 출력 print: 1 2 4 5 -- 리프노드 (재귀 끝)

//오른쪽 노드로
preorder(3);

//(3) 부모노드 출력 print: 1 2 4 5 3
//왼쪽 노드로
preorder(6);
//(6) 부모노드 출력 print: 1 2 4 5 3 6 -- 리프노드 (재귀 끝)
//오른쪽 노드로
preorder(7);
//(3) 부모노드 출력 print: 1 2 4 5 3 6 7 -- 리프노드 (재귀 끝) [종료]

 

(3) 후위 우선 탐색(Postorder Traversal)

왼쪽 자식 노드 → 오른쪽 자식 노드 → 부모 노드

void postorder(nptr bt) {
	if(bt) {
		postorder(br->lchild); //왼쪽 자식 노드  
		postorder(br->rchild); //오른쪽 자식 노드 
		print(bt->data);       //부모 노드
	}
}

[예]

//root에서 출발 (1)
postorder(1);
//왼쪽 노드로
postorder(2);

//왼쪽 노드로
postorder(4); //(4) 리프 노드 - print: 4 (재귀 끝)
//오른쪽 노드로
postorder(5); //(5) 리프 노드 - print: 4 5 (재귀 끝)
//부모 노드 출력 //(2) print: 4 5 2

//오른쪽 노드로
postorder(3);

//왼쪽 노드로
postorder(6); //(6) 리프 노드 - print: 4 5 2 6 (재귀 끝)
//오른쪽 노드로
postorder(7); //(7) 리프 노드 - print: 4 5 2 6 7(재귀 끝)
//부모 노드 출력 //(3) print: 4 5 2 6 7 3 

//부모 노드 출력 //(1) print: 4 5 2 6 7 3 1 [종료]