Tree(트리)

Tree(트리)의 개념과 특징

---

 

트리 자료구조란?

---

트리는 그래프의 한 종류로, 한개 이상의 node(노드)들이 나무가지처럼 연결된 자료구조를 의미한다. 하나의 루트 노드와 0개 이상의 자식 노드를 가진 방향성 있는 그래프를 트리라고 한다.

 

트리의 특징

---

• 하나의 root node(루트 노드)를 가진다
• 루트 노드는 0개 이상의 자식 노드를 가진다
• 자식 노드는 또 각자 0개 이상의 자식 노드를 가지고 있고 이는 반복적으로 정의된다
  즉, 트리는 재귀적인 구조를 가지고 있다
• 트리는 노드와, 노드를 연결하는 edge(간선)으로 구성된다.
• 트리는 DAG(Directed Acyclic Graphs, 방향성이 있는 비순환 그래프)의 한 종류다.
  때문에 트리에는 cycle(사이클)이 존재하지 않는다. 즉, 같은 노드를 거치지 않는다는 조건 하에 시작 노드에서 다른 노드를 거쳐 다시 시작 노드로 돌아오는 경로는 없다
  또한 한 노드에서 출발해서 자기 자신으로 돌아오는 간선(self-loop)도 존재하지 않는다.
• 트리는 사이클이 없는 하나의 연결 그래프(Connected Graph)라고 할 수 있다.
• N개의 노드를 가진 트리는 N-1개의 간선을 가진다
• 모든 자식 노드는 하나의 부모 노드를 가진다
  
  

용어 설명

---

• 
  노드(node)
  트리를 구성하는 기본요소 (A, B, C, D, ... O)
• 간선(edge)
  노드와 노드를 연결하는 연결선, link 혹은 branch라고도 한다.
• 루트 노드(root node)
  부모가 없는 노드, 하나의 트리에는 단 하나의 루트 노드만 있다 (A)
• 부모 노드(parent node)
  자식 노드를 가지는 노드, 특정 노드에게 하위 노드가 있다면 특정 노드는 하위 노드의 부모 노드가 된다(N과 O의 부모 노드는 H)
• 자식 노드(child node)
  부모를 가지는 노드, 특정 노드에게 상위 노드가 있다면 특정 노드는 상위 노드의 자식 노드가 된다(H의 자식 노드는 N과 O)
• 리프 노드(leaf node)
  자식이 없는 노드(N, O, I, J, K, L, M)
• 내부(internal) 노드
  리프 노드가 아닌 노드(H, D, E, F, G, B, C, A)
• 형제(sibling)
  같은 부모를 가지는 노드(N과 O, J와 K, F와 G 등)
• 노드의 크기(size)
  자신을 포함한 모든 자손 노드의 개수(E의 크기는 3, C의 크기는 5)
• 노드의 깊이(depth)
  루트에서 어떤 노드에 도달하기 위해 거쳐야 하는 간선의 수(L의 깊이 3, O의 깊이 4 등)
• 노드의 레벨(level)
  트리의 특정 깊이를 가지는 노드의 집합
• 노드의 차수(degree) (간선 수와 같음)
  하위 트리 개수 / 각 노드가 지닌 가지의 수 (A의 차수 2, E의 차수 2)
• 트리의 차수(degree of tree)
  트리의 최대 차수 (위 트리는 모든 노드 차수가 2이기 때문에 트리의 차수가 2가 된다. 차수가 2 이상인 노드가 있었다면 트리의 차수는 해당 노드의 차수가 된다)
• 트리의 높이(height)
  루트 노드에서 가장 깊숙히 있는 노드의 깊이(A부터 N 혹은 A부터 O, 4)

 

 

 

참고

---

https://gmlwjd9405.github.io/2018/08/12/data-structure-tree.html

[자료구조] 트리(Tree)란 - Heee's Development Blog

https://code-lab1.tistory.com/8

[자료구조] 트리(Tree)의 개념 | 이진 트리, 전 이진 트리, 완전 이진트리, 포화 이진 트리, 이진 탐