Computer Science에서의 Tree란

트리란 그래프 이론 상 Connected+Acyclic의 성질을 가지고 있는 그래프의 한 형태이다.

출처: 위키피디아

위와 같은 트리에서 edge(5,6)이 제거되면 모든 Vertex가 연결되어 있어야 한다는 Connected 성질을 만족하지 못한다.

또한 edge(4,6)이 추가된다면, 4-5-6 사이에 Cycle이 생겨 Acyclic 성질을 만족하지 못한다.

 

자료구조에서 구현하는 트리는 보통 Rooted Tree를 의미한다. 

Rooted Tree의 Non-Recursive한 정의

• 데이터를 지닌 노드와, 노드들을 연결해주는 Directed Edge의 집합으로 이루어진다. Edge의 방향은 Parent Node에서 Child Node로 향한다.

• Tree 상의 노드 중 In-degree가 0인 Node를 Root Node라고 한다. Root Node 이외의 모든 Node들은 Incomming Edge가 최대 1개 존재한다.

• Tree 상의 모든 노드 K에 대해, Root에서 K로의 유일한 Path가 존재한다.

• Node가 N개인 Tree의 Edge 수는 반드시 N-1개이다.

• 루트 노드를 제외한 모든노드는 1:1 매칭되는 부모 노드를 가지고 있다.

• 자식 노드가 없는 노드를 Leaf Node(단말 노드)라고 한다. 반대의 경우는 Non-leaf Node 혹은 Internal node라고 한다.

• 같은 부모 노드를 가진 Node들의 관계를 Sibling(형제)라고 한다.

• 만약 Node u에서 Node v로의 Path가 존재할 경우 u를 v의 ancestor(조상), v를 u의 decendant(후손)이라고 한다.

Rooted Tree의 Recursive한 정의

출처: https://images.slideplayer.com/26/8721804/slides/slide_2.jpg

• Base case: Single Node는 Tree이다.
• Recursive step: Root + 0개 이상의 Subtree + Root에서 각각의 Subtree들의 Root로 향하는 Edge는 Tree이다.

Tree 용어 

Degree(차수)	해당 Node의 Child 수
Height(높이)	해당 Node에서 도달할 수 있는 아무 Leaf Node까지 가장 긴 Path의 길이(= 두 Node간에 경로에 존재하는 edge의 수). Tree의 Height는 Root의 Height로 정의된다.
Depth(깊이)	Root에서 해당 Node까지의 Path의 길이. Tree의 Depth는 가장 Depth가 큰 Node의 Depth로 정의된다.
Level(레벨)	Depth + 1

•  

트리

 

트리는 계층적인 구조를 나타내는 비선형 자료구조로써 활용할 수 있다.

특히, 그 구조를 모든 Node의 degree가 최대 N인 N-ary Tree로 정형화되는 것이 일반적이다.

그 중에서도 N=2인 Binary Tree(이진 트리)가 가장 많이 사용된다.