[Data Structure] Trees 기초

Trees

Tree란, 유한개의 node로 이루어진 자료구조 입니다. 그 종류는 Binary Tree, Red-Black Tree 등 많이 있지만, 오늘은 그 모든 Tree의 기초에 대해 알아보도록 합시다.

---

Tree란?

Tree를 한국어로 번역하면 무엇일까요? 바로 "나무" 입니다. 이 자료구조는 나무와 유사하다고 생각하시면 됩니다. 다음 그림을 볼까요?

Tree는 이렇게 생겼습니다.

이게 어딜봐서 나무일까요? 대충 보면 하나도 닮은 것 같지가 않습니다. 우리가 생각하는 나무는 이렇게 생기지 않았거든요.

우리가 생각하는 나무는 이렇게 생겼다. 사진:  Unsplash 의 Simon Wilkes

그런데, root나 leaf는 그래도 나무의 요소라고 볼 수 있겠죠? 만약 저 위의 자료구조 Tree를 뒤집으면 조금은 진짜 나무와 비슷해보이지 않을까 싶네요. 그 상태에서 계속 자라날 수 있는(node를 추가할 수 있는) 특성상 해당 자료구조를 Tree라고 명명하지 않았나 싶습니다!

---

왜 사용하나요?

역시 이 질문이 나올 수밖에 없을 것 같네요. 왜 사용해야 할까요? 이러한 자료 구조는 어디서 어떻게 사용하는 것이 올바를까요? 사실, 해당 자료구조는 정말 많이 사용되고 있습니다. 간단한 예시를 들어 볼게요. 자동차를 분류한다고 생각을 해 볼까요? 자동차를 분류하는 방법은 여러 가지가 있지만, 이번에는 차종에 따라 나누어 본다고 가정합시다. 그럼 다음과 같이 분류할 수 있을 것 같네요.

이 외에도 컨버터블이나 트럭 등 많은 종류가 있을 수 있습니다.

어때요? 뭔가 위에서 본 그림과 비슷해지지 않았나요? 여기서 세단을 더 나누어 볼까요?

당연히 세단에도 많은 종류가 있을 수 있습니다ㅎㅎ

이렇게 계속해서 가지를 치고 나가는 자료 구조가 바로 Tree입니다.

Tree는 이런식으로 분류하는 것 뿐만 아니라 정렬을 하는 데에도 사용될 수 있습니다. 마구잡이로 놓여있는 숫자들 중 하나를 골라 기준을 삼고, 그 기준보다 큰 숫자는 오른쪽 가지로, 작은 숫자는 왼쪽 가지로 놓는 식으로 한 뒤, 왼쪽부터 읽으면 정렬이 되어 있겠죠? 이 방법은 나중에 Binary Tree를 볼 때 다시 보도록 합시다!

---

용어 정리

Tree에서 사용되는 특수한 용어들이 있습니다. 이를 숙지하신다면, 공부하는 데에 도움이 될 수 있을 것 같네요.

 

1. Node: Tree에서 데이터를 저장하는 가장 기본적인 단위의 원소입니다. 지금까지 동그라미로 표현한 것이 Node입니다.

2. Root: Tree에서 가장 상위 한 개의 Node를 말합니다.

3. Branch: Node간 연결하고 있는 선을 의미합니다.

4. Parent-Child(Children): Branch로 연결된 두 개의 Node 사이의 관계를 이야기합니다. 당연히 root에 가까운 쪽이 parent입니다. 한 개의 Node는 최대 1 개의 parent만을 가질 수 있습니다.

5. Siblings: 동일한 Parent를 갖는 Node들입니다. 한 개의 Parent는 여러 개의 Children을 가질 수 있기 때문에 나타납니다.

6. Degree: Tree의 크기를 의미합니다.

7. Leaf(Terminal Node): Degree가 0인 Node를 의미합니다. 즉, Child가 없다고 생각하시면 됩니다.

8. Internal node: Degree가 0보다 큰 Node를 의미합니다. Leaf와 달리 Child가 있는 Node들입니다.

9. Subtree: 원래의 Tree의 부분 집합으로 이루어진 Tree입니다.

10. Ancestors - Descendants: 두 개의 Node에 대한 관계입니다. 다음과 같이 볼 수 있습니다.

    10-1. Ancestors: 자신과 root와의 Path 상에 존재하는 모든 Node들입니다. 말 그대로 내 부모의 부모, 부모의 부모의 부모... 입니다.

    10-2. Descendants: 자신과 직접 혹은 간접적으로 연결된 모든 하위 Node입니다.

11. Level: Root가 1일 때, Root와의 상대적인 거리입니다.

Height(=depth): Tree의 최대 Level입니다.

---

여기까지 Tree에 대해 알아보았습니다. Tree는 매우 무궁무진하게 활용할 수 있는 매우 중요한 Data Structure입니다. Tree가 지금 당장은 어떻게 쓰일지 감이 안잡힐 수도 있습니다만, 사실 매우 중요합니다. Binary Search Tree(BST)와 같은 Tree는 Searching 시간을 상당히 많이 줄여주기 때문입니다!

다음번에는 BST에 대해 알아보도록 합시다!