3.Tree에 대해서 알아보자.
27 Aug 2016자료구조 트리와 그 표현에 대해서 알아보자.
트리, 나무라는 이름의 이 자료구조는 생소하게 느껴질테지만 사실 일상생활에서 많이 볼 수 있는(?) 자료구조이다. 고등학교 생물 시간에 멘델의 법칙을 배운적이 있는데 아래와 같은 그림을 본적이 있다.
상염색체에 의한 유전, zum학습백과
저는 혀말기가 잘 됩니다. 부모와 자식간의 관계를 나타내기에는 tree가 아주 제격이다. 그럼 tree의 정의에 대해서 알아보자.
정의
트리(tree)는 한 개 이상의 정점(노드, node)로 이루어진 유한 집합으로서
- 노드 중에는 루트(root)라고 하는 노드가 하나 있고
- 나머지 노드들은 n(>= 0)개의 분리집합, T1,… Tn으로 분할될 수 있다. 여기서 T1,…,Tn은 각각 하나의 트리이며 루트의 서브트리(subtree)라고한다.
이석호. C++ 자료구조론 (2nd ed.). 인피니티북스.
정의가 어려운데 트리의 정의를 한 문장으로 정의하면 다음과 같다.
Connected Acyclic Graph
모든 노드들이 연결되어 있고 사이클이 존재하지 않는 그래프가 바로 트리이다!
용어
정보통신기술용어해설, 트리
트리에서 사용되는 용어들은 다음과 같다.
- Root
트리의 꼭대기에 있는 노드, 그림에서 A - Child
루트로부터 멀어지는 방향으로 직접적으로 연결된 노드, A의 자식은 B, C - Parent
루트로부터 가까워지는 방향으로 직접적으로 연결된 노드, B의 부모는 A - Siblings
같은 부모를 가지고있는 노드들의 집합, D E F - Descendant
특정 노드에서 노드의 subtree의 모든 집합, C의 자손은 G H L M N - Ancestor
특정 노드에서 노드의 부모 노드의 집합, J의 조상은 D B A - Leaf
자식이 없는 노드, I J K F L M N - Internal Node
적어도 하나의 자식이 있는 노드 - External Node
자식이 없는 노드 - Degree
자식 노드들 중 최대 개수, B가 자식 3을 가지므로 차수 3 - Edge
노드와 노드사이를 잇는 간선 - Path
한 노드에서 다른 한 노드에 이르는 길 사이에 놓여있는 노드들의 순서 - Depth
루트에서 어떤 노드까지의 경로길이 - Level
표현
트리의 표현은 여러가지 방법으로 구현할 수 있다. 다루고자하는 tree마다 표현이 다를 수 있으므로 다루고자하는 자료가 어떤 tree의 모양을 하고 있을지 미리 예상하면 좋다. 고 생각한다.
-
인접행렬 노드의 갯수가 V개라고 했을때 VxV의 크기를 가진 이차원 배열을 할당하여 구현 할 수 있다. 할당한 배열을 A라고 했을 때 노드i에서 j로 가는 간선이 있을 때
A[ i ][ j ] = 1로 표현 할 수 있다. - 인접리스트
- Linked List 이전 포스트에서 다룬 Linked List로 Tree의 표현을 구현할 수 있다.
- STL
Linked List는 구현하는데 시간이 오래 걸린다. vector나 list같은 STL을 이용하면 쉽게 구현 할 수 있다. 정점 A[i]와 연결된 정점들의 정보를 가지고 있으면 된다.
A[1] 1 2 A[2] 3 4 A[3] 5 - 배열 이진트리(Binary tree)의 경우 배열로 나타낼 수 있다. 트리의 부모만 저장하는 방식으로는 index는 현재 정점을 배열이 가지는 값은 노드의 부모를 가르키는 방식으로 구현 할 수 있다.