자료구조: 트리Tree의 기본 개념

자료구조: 트리Tree의 기본 개념

Graph Concept를 이해하기 위한 아주 기본적인 tree 개념에 대해 알아봅니다.
트리가 어떤 개념인지, 트리의 특성, 트리의 종류, 그리고 탐색방식에 대해서요.

이진트리

---

child node가 최대 2개 붙는 경우 이진트리binary tree입니다.
세 개, 혹은 그 이상도 존재하는 트리도 있긴 해요.

이진탐색트리 Binary search tree

---

root node보다 값이 작은 child node는 왼쪽에, 값이 큰 child node는 오른쪽에 배치해서 탐색을 용이하게 한 트리 구조입니다. 줄여서 BST라고들 말해요.

밸런스 - balanced / unbalanced

왼쪽/오른쪽 child node의 개수가 균형을 이루지 않아 트리로 판단하기 어려운 정도가 되면 unbalanced하다고 합니다. 당연히 트리로서의 특성이 떨어지겠죠. tree가 unbalanced 해지지 않도록 대개 삽입/삭제 시에 구조를 재조정하는 알고리즘이 추가되어 있습니다.
balanced tree의 대표적인 것들에는 red-black tree, AVL tree 등이 있습니다.

트리 종류를 소개하기 앞서

---

잘은 모르지만 트리들을 구분해 부르는 이름은 제각기 부르기 나름인 것 같아요. 특히 영어와 한국어 사이에 정확히 매칭이 되지 않으니 학습 시 유의해야겠습니다.
아래 소개되는 트리들도 이름을 외우지 말고 특성에 집중해서 이해하면 좋을 듯 합니다.

완전 이진 트리

---

완전 이진 트리는 child node를 왼쪽에서부터 오른쪽으로 차례로 갖고 있는 형태의 트리를 말합니다. 꽉 차있을 필요는 없어요. leaf node level을 제외한 모든 subtree의 레벨이 동일해야 하고, 왼쪽부터 차있어야해요.

정 이진 트리

---

하나의 노드가 0개 혹은 2개의 child node를 가집니다. 하나의 child node를 갖는 node가 있다면 그 트리는 정 이진 트리가 아닙니다.

포화 이진 트리

---

leaf node가 아닌 모든 node가 두 개의 child node를 갖고 있습니다. tree의 level이 n일 때에, tree에 포함된 모든 node의 개수는 2^n - 1개입니다.

트리 순회 방식 Binary Tree Trabersal

---

tree라는 특별한 구조를 탐색하는 방식은 아래 소개할 세가지입니다. root를 기준으로 중위, 전위, 후위를 말합니다.
이 순회 방식과 별개로, 트리를 탐색하는 기본적인 방향은 왼쪽 먼저, 오른쪽 나중입니다.

1. 중위 Inorder / left - root - right
2. 전위 Preorder / root - left - right
3. 후위 Postorder / left - right - root