트리(Tree)

written by sohyeon, hyemin 💡

1. 트리란?

트리(tree)는 그래프의 한 종류로, 데이터 사이의 계층 관계를 나타내는 자료구조를 말한다.

2. 트리의 특징

• 그래프의 한 종류로, 최소 연결 트리라고 한다.

• 트리는 계층 모델이다.

• 트리는 DAG(Directed Acyclic Graphs, 방향성이 있는 비순환 그래프)의 한 종류로, 사이클이 없다.

• 노드가 N개인 트리는 항상 N-1개의 간선(가지, edge)을 가진다.

• 한 개의 루트 노드만이 존재하며, 모든 자식 노드는 한 개의 부모 노드만을 가진다.

• 부모 - 자식 관계이므로 흐름은 top-bottom 이나 bottom-top으로 이루어진다.

• 순회는 Pre-order(전위), In-order(중위) 아니면 Post-order(후위)로 이루어진다.

• 트리의 종류에는 이진 트리, 이진 탐색 트리, 균형 트리(AVL 트리, red-black 트리), 이진 힙(최대힙, 최소힙) 등이 있다.

3. 트리 관련 용어

트리를 구성하는 요소는 노드(node) 와 간선(가지, edge)이다.

• 루트 노드(root node)
  트리의 가장 윗부분에 위치하는 노드로, 0개 이상의 자식 노드를 가지고 있다.

• 단말 노드(leaf node)
  트리의 가장 아랫부분에 위치하는 노드로, 더 이상 뻗어나갈 수 없는 마지막에 위치한 노드를 말한다.

• 내부(internal) 노드
  루트를 포함하여 리프를 제외한 노드로, 다른 용어로 끝이 아닌 노드(non-terminal node)라고 한다.

• 자식 노드(child node)
  어떤 노드로부터 간선으로 연결된 아래쪽 노드로, 노드는 자식을 여러 개 가질 수 있다. 예를 들어 X는 1개, Y는 2개의 자식을 가지고 있다.

• 부모 노드(Parent Node)
  어떤 노드에서 간선으로 연결된 위쪽 노드로, 노드는 1개의 부모를 가진다. 예를 들어 Y의 부모는 X이다.

• 형제 노드(Sibling Node)
  같은 부모를 가지는 노드를 말한다.

• 조상
  어떤 노드에서 간선으로 연결된 위쪽 노드 모두를 말한다.

• 자손
  어떤 노드에서 간선으로 연결된 아래쪽 노드 모두를 말한다.

• 노드의 레벨(level)
  루트로부터 얼마나 떨어져 있는지에 대한 값을 말한다. 루트의 레벨은 0이고 루트로부터 간선이 하나씩 아래로 뻗어나갈 때마다 레벨이 1씩 늘어난다.

• 노드의 크기(size)
  자신을 포함한 모든 자손 노드의 개수를 말한다. 예를 들어 X의 크기는 4이다.

• 노드의 깊이(depth)
  루트에서 어떤 노드에 도달하기 위해 거쳐야 하는 간선의 수를 말한다. 예를 들어 Y의 깊이는 2이다.

• 트리의 차수(degree of tree)
  노드가 갖는 자식의 수를 말한다. 또한, 모든 노드의 차수가 n 이하인 트리를 n진 트리라고 한다. 예를 들어 그림은 모든 노드의 자식이 3개 이하이므로 3진 트리이다.

• 트리의 높이(height)
  루트로부터 가장 멀리 떨어진 리프까지의 거리를 말한다.

• 서브 트리
  트리 안에서 다시 어떤 노드를 루트로 정하고 그 자손으로 이루어진 트리를 말한다.

• 널 트리
  노드, 간선이 없는 트리를 말한다.

• 순서 트리와 무순서 트리
  형제 노드의 순서를 따지면 순서 트리(ordered tree), 따지지 않으면 무순서 트리(unordered tree)라고 한다.

Reference & Additional Resources

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