[Data Structure] Binary Tree (이진 트리)

Binary Tree

📢 모든 Node가 최대 2개의 자식을 가지고 있는 트리

---

위의 그림처럼 모든 Node의 자식이 0~2개씩 있다면 Binary Tree라고 할 수 있어요. Node의 각 자식은 Left-Child, Right-Child라고 합니다. 단어 그대로 Node 기준 왼쪽에 있다면 Left-Child, 오른쪽에 있다면 Right-Child예요. Binary Tree는 종류가 많아서 아래에서 하나씩 보도록 합시다.

---

Tree Traversal (트리 순회)

다른 자료구조와 달리 Tree는 데이터 값을 알기 위해 3가지 방법을 사용해요. 이 3가지는 순회 하는 방법에 따라서 나뉘게 되요. 완전 이진 트리를 기준으로 설명해 드리겠습니다.

1. Preorder Traversal (전위 순회)

Parent Node -> Left-Child -> Right-Child

2. Inorder Traversal (중위 순회)

Left-Child -> Parent Node -> Right-Child

3. Postorder Traversal (후위 순회)

Left-Child -> Right-Child -> Parent Node

---

Binary Search Tree (이진 탐색 트리)

• 부모 Node 값을 기준으로 Left-Child는 작고, Right-Child는 큰 값을 지닌 트리다.
• 데이터 탐색이 목적이므로 중복을 허용하지 않는다.

⏰ 시간 복잡도

탐색(Search)

• 균형 잡힌 이진 트리라면O(logN)의 시간 복잡도를 가져요.
• 루트 노드부터 확인 해야하는 노드 수가 반씩 줄어들기 때문이에요.
• 편향 이진 트리라면O(N)의 시간 복잡도를 가져요.
• 루트 노드부터 해당 데이터 노드까지 모든 노드를 확인해야 하기 때문이에요.

삽입(Insert)

• 원하는 삽입 위치를 탐색 하는데 대부분의 시간이 소요돼요.
• 탐색과 동일한 시간 복잡도를 가져요.

제거(Delete)

• 제거를 하려는 데이터를 탐색하는데 대부분의 시간이 소요돼요.
• 탐색과 동일한 시간 복잡도를 가져요.

---

📋 예제

백준 1991 - 트리 순회

백준 1991 - 해답

---

📚 다양한 이진 트리

Full Binary Tree (정 이진 트리)

• 모든 Node의 자식이 2개 또는 0개다.

Complete Binary Tree (완전 이진 트리)

Complete Binary Search Tree (완전 이진 탐색 트리)

• 마지막 Level을 제외하고 꽉 차 있는 Tree다.
• 마지막 Level의 Node들은 왼쪽부터 오른쪽으로 순서대로 채워져야 한다.
• 위 아래 모두 Complete Binary Tree다.

아래는 Complete Binary Search Tree의 설명

• 데이터 삽입을 할 때 마다 Tree 형태를 유지해야 하므로 모양을 바꾸는데 시간이 소요된다.
• 삽입 보다는 탐색을 주로 하는 경우에 유리하다.

Perfect Binary Tree (포화 이진 트리)

• Full Binary Tree이면서 모든 Leaf Node(External Node)의 Depth가 같다.
• Binary Tree가 꽉 찼다고 생각하면 된다.

Skewed Binary Tree (편향 이진 트리)

• 모든 Node가 한 쪽으로 치우친 Tree다.

Balanced Binary Tree (균형 이진 트리)

• 왼쪽, 오른쪽 SubTree의 Height 차이가 1인 Tree다.