Data Structure(4) Tree

Tree

Tree는 노드로 구성된 계층적 자료구조이다.
트리는 우리가 아는 나무를 거꾸로 뒤집어 놓은 형태를 생각하면 쉽다

Tree 구조

Tree 자료구조의 구성 :

1. Root - Tree의 최상단에 위치한 뿌리노드.

Ex. A

2. Parent Node - 부모 노드들.

Ex. A, B, C, D, E

3. Child Node - 자식 노드들.

Ex. 'A' Root를 제외한 모든 노드.

4. Siblings - 형제 노드.

Ex. "B, C" / "D, E" / "F, G" / "H, I"

5. Leaf Node - 자식들이 더 없는 최하단 노드

Ex. F, G, H, I, J

6. Edge - 노드와 노드를 잇는 선

7. Depth - Root를 기준으로, 다른 노드로 접근하기 위한 거리

 

Tree 구조에서 사용되는 기본 Method :

* insertNode(value) - 트리에 노드를 추가합니다.

* contains(value) - 트리에 해당 노드가 존재하는지 여부를 반환합니다.

 

* depth와 height의 차이?

* 트리와 그래프의 차이점?

---

Binary Tree

Binary Tree(이진 트리) :  각 노드가 하나 혹은 최대 2개의 자식 노드만을 가지고 있는 상태의 트리구조이다.

BinaryTreeNode 구조

위 코드로 "한 노드는 Linked List와 매우 비슷한 구조"인 것을 알 수 있다.

---

Types of Binary Tree

Perfect Binary Tree : 자식 노드가 없는 Leaves를 제외한 모든 노드가 2개의 노드를 가지고 있다.
* Tree의 가장 깊은 Depth의 모든 Node가 값이 채워져 있는 형태이다.

Perfect Binary Tree

Perfect Binary Tree 특징 :

1. 한 단계 아래 Depth로 내려갈 때마다 노드의 수는 정확하게 2배가 된다.

Ex. 1개 > 2개 > 4개 > 8개 > ...

2. 마지막 Depth의 모든 노드의 개수 = 직전 Depth까지의 모든 노드의 개수 + 1이다.

- 즉, 마지막 Depth에 전체 노드의 절반이 있다는 의미이다.

 

Complete Binary Tree : "완전 이진 트리"는 왼쪽 자식노드부터 채워지며 마지막 Level을 제외하고는 모든 자식노드가 채워져있다.
* 반드시 트리 왼쪽부터 채워져있고 마지막 Level을 제외하고 모두 자식노드가 있다.

Full Binary Tree : "정 이진 트리"는 모든 노드가 0개 혹은 2개의 자식노드를 가지는 트리를 말한다.
* 또한, 포화 이진 트리의 하위종류이다.

위 세 가지의 Binary Tree(이진 트리) 구조는 아래 사진과 같다.

Types of Binary Trees

---

Binary Search Tree

Binary Search Tree (이진 탐색 트리) : 특정 값을 찾을 때 아주 유용한 자료구조로, 재귀적이며, 최대 2개의 자식만 갖는 트리다.
* 현재 노드의 오른쪽에 있는 노드는 반드시 현재 노드보다 큰 값을 가지고 있다.
* 반대로, 왼쪽에 있는 노드는 현재 노드보다 작은 값이다.

** 이 자료구조가 Hash Table보다 더 나은 이유는?

Hash Table : 데이터 간의 관계가 존재하지 않는다. 단지 키와 밸류만 존재한다.

BST : 노드들 간의 관계에 의거하여 자료가 분류되어 있다.

Ex. 컴퓨터 홈 디렉토리와 그의 폴더들.

Binary Search Tree 구조

---

Pros and Cons of Binary Search Tree :

BST의 장점 : Value-searching이 매우 빠르고 효율적이다.

- 모든 노드를 iterating 하지 않고도 특정 값을 빠르게 찾을 수 있다.

BST의 단점 : Insert & Delete의 경우, 현재 노드보다 큰지 작은지를 기반으로 추가/삭제 해야 하는 값의 위치로 이동하게 된다. 

Ex. 만약 위 그림에서 105를 지우면, 이 자리를 대체할 값을 찾아야 하며 144가 105의 자리를 대체하게 된다.

∴ 만약 노드의 level이 아주 깊다면, 최하단 Depth부터 값을 하나씩 위로 올려야 하기 때문에 해쉬 테이블에서 값을 삭제할 때의 시간복잡도 O(1)보다 느릴 수 밖에 없다.

 

정상적인 이진 트리의 경우, 위 사진과 같은 형태를 갖고 있으며, O(log N)의 시간 복잡도를 갖는다.

그러나, 아래 사진과 같이 언제나 최악의 경우는 있기 마련이다.

 

Unbalanced BST 예시 & 시간 복잡도

Unbalanced BST: 만약 현재 노드보다 큰 값만 계속 추가하게 될 경우에는 위 사진처럼 오른쪽으로만 치우진 불균형 형태가 된다.
이 경우, Searching은 모든 요소를 iterating하는 배열과 다를 바가 없으므로 O(n)의 시간 복잡도를 가지게 된다.

---

Binary Tree Traversal

두 가지 이진 트리 순회 방법 :

1. 깊이 우선 탐색 (Recursively, DFS, Depth-First Search) : 

- 전위 순회(Preorder Traversal): 부모 → 좌 → 우

- 중위 순회(Inorder Traversal): 좌 → 부모 → 우

- 후위 순회(Postorder Traversal): 좌 → 우 → 부모

 

2. 너비 우선 탐색 (Iteratively, BFS, Breadth-First Search)  :

- Level-order : 같은 층끼리 순회

 

Binary Tree Traversal 설명 영상

---