Tree (트리)

트리는 스택, 큐, 연결리스트와는 다르게 비선형적 자료구조이다.

트리는 계층 구조로 이루어져 있다.

계층 구조로 나타내기 적합한 자료는 가계도, 목차-내용, 폴더-파일 관계 등이 있다.

 

보통 일반 적인 경우에는 이진 트리를 많이 사용한다.

특별한 경우(게임 맵, 웹사이트의 카테고리 등)에서는 삼진 이상의 다진 트리를 이용하기도 한다.

 

트리는 가지는 특징에 따라서 이진 트리, 완전 이진 트리, B-Tree, AVL트리, 레드 블랙 트리 등등 다양한 이름으로 불린다.

마치 이브이같다.

이 포스트에서는 트리의 특징에 대해서 설명하고, 트리의 개념을 이해하자.

---

트리는 한 개 이상의 요소(노드)로 이루어진 유한 집합이다. 이들 중에서 특정 한 개의 노드는 root node라고 불리고, 나머지는 subtree(서브 트리)라고 불린다. 보통 계층적인 구조에서 가장 높은 곳에 있는 노드를 root node라고 부른다. 그리고 root node의 하위 트리를 서브 트리라고 부른다.

트리

트리 용어는 이러하다

root(뿌리) : 계층적인 구조에서 가장 높은 곳에 있는 노드, 서브 트리에서 최상위에 위치하는 노드

level(단계) : 트리의 깊이. (root node의 level은 1이고, 그 자식 노드의 level은 2이다.)

depth(깊이) : root 노드에서 얼마나 떨어져 있는지 나타냄.

height(높이) : 트리의 높이, 트리의 최대 level과 같음

edge(간선) : root node와 서브트리를 잇는 연결선

parent(부모) : 어떤 노드의 한 단계 상위 노드

child, children(자식) : 어떤 노드의 한 단계 하위 노드

degree(차수) : 어떤 노드가 가지고 있는 자식 노드의 개수

sibling(형제) : 어떤 노드와 같은 level의 노드

leaf node, terminal node(단말 노드) : 어느 서브 트리 안에서 더이상 자식이 없는 노드 (= 차수가 0인 경우)

 

forest(포리스트) : 트리들의 집합

---

용어를 제대로 이해했는지 확인하면 좋겠다.

• C,D,Q,I,R은 모두 형제 노드이다.
• 위 트리의 높이는 4이다.
• 노드 R은 노드 V와 노드 E의 부모 노드이다.
• 노드 T는 노드 Q의 자식 노드이다.
• T는 자식 노드가 없기 때문에 단말 노드이다.
• B는 차수가 2이다.

---