목차
- 트리 란?
- 트리 용어
- 트리의 종류
3-1. 이진 트리
3-2. 완전 이진 트리
3-3. 이진 탐색 트리 - 트리 구현 방법
- 마치며
1. 트리 란?
말그대로 나무를 본떠서 만든 자료구조입니다.
하나의 뿌리를 가진 체 여러 갈래의 가지를 치면서 나아가는 모습을 가지고 있습니다.
위에서 보이듯 아래로 뻗어 나아가는 모습을 보이고 있습니다.
2. 트리 용어
노드(node): 각각의 자료를 담고있는 가장 작은 단위입니다.
루트 노드(root node): 뿌리라는 의미에 맞게 가장 처음 시작된 노드를 가리킵니다.
부모 노드(parent node): 자식노드를 가진 노드입니다. (A, B를 기준으로 A노드가 부모노드입니다.)
자식 노드(child node): 부모 노드에서 뻗어나간 노드입니다. (A, B를 기준으로 B가 자식노드입니다.)
잎 노드(leaf node): 자식 노드가 없는 노드입니다. (K, L, F, G, M, I ,J)
내부 노드(internal node): 잎 노드를 제외한 나머지 노드입니다. (A, B, C, D, E, H)
깊이(depth): 특정 노드가 루트에서 뻗어나기 위해 거쳐가야 할 간선의 갯수
차수(degree): 특정 노드가 가진 자식 노드의 갯수
3. 트리의 종류
3-1. 이진 트리
각 노드들의 차수가 2를 넘지 않는 트리입니다.
3-2. 완전 이진 트리
이진 트리에서 앞의 자식노드를 우선으로 차례대로 노드를 추가하는 방식입니다.
3-3. 이진 탐색 트리
이진 트리의 한 종류입니다.
우선순위를 정하여 만족하면 자신의 오른쪽 자식노드로, 만족하지 못하면 왼쪽 자식노드로 추가합니다.
위 예시는 "큰 숫자"를 우선순위로 생각하고 만들어진 결과입니다.
3-4. heap
이진 탐색트리와는 다르게 우선 순위를 기준으로 가장 높은 우선 순위를 가지는 노드를 root로 가지는 트리입니다.
보통 트리에 있어서 자료를 추가하게 될 경우 자식노드로 추가하게 됩니다.
그렇기 때문에 heap을 구현하기 위해서는 연결된 노드끼리의 위치를 변환하는 과정이 필요합니다.
4.구현 방법
유명한 트리의 구현의 경우 대부분이 이진트리의 형태를 가지고 있습니다.
4-1. 배열을 이용한 구현
이러한 방법을 사용했을 때 왼쪽 자식 노드의 배열은 자신의 배열의 두 배 위치이며, 오른쪽 노드의 배열 위치는 거기에 1을 더한값으로 부모 노드가 자식 노드에 해당하는 연결이 용이합니다.
4-2. 리스트를 이용한 구현
각 노드를 구조체등을 위 그림의 노드처럼 구현한 다음 left_child, right_child를 각각 자식 노드에 해당하는 노드에 연결해주는 방식입니다.
배열로 만들는 것에 비해 공간적으로 절약하게 됩니다.
5. 마치며
정말 기초적인 설명만 되어했습니다.
그럼에도 segment tree, Fenwik tree등에 대한 설명도 드리고 싶었습니다만 해당하는 각각의 트리들은 하나의 포스팅을 해도 될 정도로 깊이있다고 생각되는 구조들이기 때문에 다음 기회에 좀 더 심도있게 다뤄보도록 하겠습니다.
