트리란 그래프의 일종으로, 노드로 이루어진 자료구조이다.
주로 계층적인 자료를 표현하는데에 사용되며, 데이터를 부모-자식 관계로 나타낸다.
나무를 거꾸로 뒤집어 놓은 모양과 유사하다 하여 트리라는 이름이 나오게 되었다.

노드는 컴퓨터 과학에서 쓰이는 기초적인 단위이며, 대형 네트워크에서는 장치나 데이터 지점(data point)을 의미한다.
인터넷에서는 ip 주소를 보유한 어떠한 것이 될 수 있으며, 자료구조에서는 데이터를 포함할 수 있다.

용어

• 루트 노드(root node): 부모가 없는 노드, 트리는 단 하나의 루트 노드만을 가짐
• 단말 노드(leaf node): 자식이 없는 노드
• 내부 노드(internal node): 단말 노드가 아닌 노드
  • 부모 노드(parent node): 자신보다 바로 위에 있는 노드
  • 형제 노드(sibling node): 자신과 같은 부모를 가지는 노드
  • 자식 노드(child node): 자신보다 바로 아래에 있는 노드
• 간선(edge): 노드를 연결하는 선(link, branch 라고도 불림)
• 노드의 크기(size): 자신을 포함한 모든 자손 노드의 개수
• 노드의 깊이(depth): 루트에서 어떤 노드에 도달하기 위해 거쳐야 하는 간선의 수
• 노드의 레벨(level): 트리의 특정 깊이를 가지는 노드의 합(level은 0부터 시작할 수도 있고 1부터 시작할 수도 있음)
• 노드의 차수(degree): 하위 트리의 개수/간선 수 = 각 노드가 지닌 가지의 수
• 트리의 차수(degree of tree): 트리의 최대 차수
• 트리의 높이(height): 루트 노드에서 가장 깊숙히 있는 노드의 깊이
• 서브 트리(subtree): 루트 노드를 제외한 나머지 노드(서브 트리에서도 다시 루트와 서브를 나눌 수 있음)

특징

• 계층형 모델
• Cycle이 존재하지 않음
• 모든 노드는 서로 연결되어 있음
• 모든 자식 노드는 하나의 부모 노드만을 갖음
• 루트 노드에서 어떠한 노드로 가는 간선은 유일함
• 노드가 N개인 트리는 항상 N-1개의 간선을 가짐

트리의 종류

• 편향 트리(skew tree)
• 이진 트리(Binary Tree)
• 이진 탐색 트리(Binary Search Tree, BST)
• m원 탐색 트리(m-way search tree)
• 균형 트리(Balanced Tree,B-Tree)

편향 트리(skew tree)

• 모든 노드들이 자식을 하나만 갖는 트리
• 자식을 갖는 방향에 따라서 left skew tree, skew tree, right skew tree로 구분

이진 트리(Binary Tree)

• 각 노드의 차수(자식 노드)가 2이하인 트리
• 모든 노드가 이진트리는 아님

이진 탐색 트리(Binary Search Tree, BST)

• 순서화된 이진 트리
• 노드의 왼쪽 자식은 부모의 값보다 작은 값을, 오른쪽 자식은 부모보다 큰 값을 지님

m원 탐색 트리(m-way search tree)

• 최대 m개의 서브 트리를 갖는 탐색 트리
• 이진 탐색 트리의 확장된 형태로 높이를 줄이기 위해 사용
• 탐색 트리의 제한을 따르되 2개 이상(m개 이하) 자식을 가질 수 있음 (3원 탐색 트리, 4원 탐색 트리, ...)

균형 트리(Balanced Tree,B-Tree)

• m원 탐색 트리에서 높이 균형을 유지하는 트리
• height-balanced m-way tree라고도 함

Reference

• [자료구조] 트리 (Tree)
• [자료구조] 트리(Tree)란
• 노드 (컴퓨터 과학) - 위키백과