[Data Structure] #4-1 Tree 개념

Tree 개념

 Tree는 외워야 할(?) 용어와 이해해야 하는 개념이 몇 가지 있다. 그리 어렵지는 않다. 배운 것을 토대로 정리를 해보았다.

 우선 Tree는 hierarchical structure (계층적 구조)를 가진다. 좀 그림을 못 그리긴 했는데 다음과 같은 구조를 계층적 이라고 한다.

 그럼 반대의 개념은 뭘까? 바로 지금껏 다뤘던 리스트, 스택, 큐와 같은 자료구조와 같은 선형적 구조다. 선형적이라는 말은 데이터간의 관계가 하나의 선을 이룬다는 의미다. 책에서는 '나열'이라는 말로 선형적이라는 말을 해석해 놓았다.

 트리는 인공지능(AI)에서도 이용된다. 인공지능이란 사실 알고리즘과 굉장히 관련이 깊다. 알고리즘을 간단하게 정리하기는 쉽지 않지만 나는 개인적으로 input을 넣었을 때 의미있는 output이 나오는 과정 혹은 해법을 알고리즘이라 생각한다. 즉, 인공지능 또한 어떤 질문(input)을 던져 넣었을 때 의미 있는 대답(output)이 나오는 것을 의미한다.

 어째서 이 트리가 인공지능에 사용 될까. 사실 tree는 우리의 삶과 굉장히 관련이 깊다. 우리가 어떤 결정을 하고자 할 때 어떤 대안들이 존재하고 그 대안을 선택하고 나면 또 다시 결정 해야 하고 마찬가지로 결정에는 대안이 존재한다. (물론 답없는 인생도 있다.. :D) 어쩐지 이 계층적 구조와 닮아있지 않은가? 그래서 문제 해결 과정인 인공지능에 트리가 자주 쓰이는 것이다. 책에서는 이러한 결정 과정 트리를 decision tree라고 부른다.

 잡설은 여기까지하고 용어에 대해서 알아보자. 쉬운 용어는 그냥 넘어가고 이해가 필요한 용어는 조금 설명을 붙이겠다.

Node : Tree를 구성하는 하나(one)의 구성요소 

Root : Tree의 꼭대기 Node

Subtree : Root의 아래에 존재하는 Node 집합

Edge : Node와 Node를 잇는 연결선

Parent Node : 한 Node의 부모 Node (한 계층 위에 존재하는 Node)

Child Node : 한 Node의 자식 Node들 (한 계층 아래에 존재하는 Node)

Sibling : 같은 계층에 존재하는 Node들

Ancestor Node (조상) : 특정 Node의 Parent Node부터 Root Node까지의 모든 Node들

Descendent Node (자손) : 특정 Node의 Child Node부터 마지막 Node까지의 모든 Node들

Terminal Node : Child Node가 존재하지 않는 노드 (<=> Nonterminal Node)

Degree (차수) : Child Node의 갯수

Level : 설명하기가 어려우니 그림으로 보자

 root부터 한 계층 씩 내려 갈수록 level이 증가한다. 계층을 숫자로 바꾼 것에 불과하다. 다만 root가 1부터 시작한다는 것을 알아두자. 

Height : Tree의 최대 Level. 위의 그림에서는 height가 3이다.