[Computer Science] 트리 (Tree)

트리의 정의

• 비선형 구조
• 원소들간에 1:n 의 관계를 가지는 자료구조
• 원소들간에 계층관계를 가지는 계층형 자료구조
• 상위 원소에서 하위원소로 내려가면서 확장되는 나무모양의 구조

한개 이상의 노드로 이루어진 유한집합을 말하며 다음 조건을 만족함

1. 노드중 최상위 노드를 루트(root)라고 한다
2. 나머지 노드들은 n(≥0)개의 분리 집합 T1~TN 으로 분리될 수 있다.
3. 사이클이 존재할 수 없다. (부모로 가는 간선은 한개며 다른 부모 노드는 하나임)
4. 아래와 같이 표현이 가능

 

class Node {
  public String name;
  public Node[] children;
}

 

이들 T1~TN은 각각 하나의 트리가 되며(재귀적 의미) 루트의 부 트리(subtree)라고 한다

트리에 나오는 용어

1. 노드 - 트리의 원소를 말함
2. 간선 - 노드를 연결하는 선, 부모와 자식노드를 연결
3. 루트노드 - 트리의 시작노드, 최상위 노드 (A)
4. 형제노드 - 부모가 같은 노드들 (B의 형제 C)
5. 조상노드 - 간선을 따로 루느토드까지 이르는 경로에 포함된 노드들 (I의 조상 D,B,A)
6. 서브트리 - 부모노드와 연결을 끊었을경우 생성되는 트리
7. 자손노드 - 서브트리에 있는 하위 레벨의 노드들 (B의 자식 D,E,H,I,J)
8. 차수 (degree) -
   • 노드의 차수 : 노드에 연결된 자식노드 수 (B의 차수는 2)
   • 트리의 차수 : 트리에 있는 노드의 차수중 가장 큰 값 ( 2가 가장 큼)
   • 단말 노드(리프 노드) : 차수가 0인 노드, 자식이 없는 노드
9. 높이( level )
   • 노드의 높이 : 루트에서 노드에 이르는 간선수
   • 트리의 높이 : 트리의 노드중 가장 큰 높이값

 

 

트리의 특징

• 그래프의 한 종류이다. ‘최소 연결 트리’ 라고도 불린다.
• 트리는 계층 모델 이다.
• 트리는 DAG(Directed Acyclic Graphs, 방향성이 있는 비순환 그래프)의 한 종류이다.
  • loop나 circuit이 없다. 당연히 self-loop도 없다. 즉, 사이클이 없다.
• 노드가 N개인 트리는 항상 N-1개의 간선(edge)을 가진다.
  • 즉, 간선은 항상 (정점의 개수 - 1) 만큼을 가진다
• 루트에서 어떤 노드로 가는 경로는 유일하다.
  • 임의의 두 노드 간의 경로도 유일하다. 즉, 두 개의 정점 사이에 반드시 1개의 경로만을 가진다.
• 한 개의 루트 노드만이 존재하며 모든 자식 노드는 한 개의 부모 노드만을 가진다.
  • 부모-자식 관계이므로 흐름은 top-bottom 아니면 bottom-top으로 이루어진다.
• 순회는 Pre-order, In-order 아니면 Post-order로 이루어진다. 이 3가지 모두 DFS/BFS 안에 있다.
• 트리는 이진 트리, 이진 탐색 트리, 균형 트리(AVL 트리, red-black 트리), 이진 힙(최대힙, 최소힙) 등이 있다.