Tree

트리의 개념

• 트리는 노드로 이루어진 계층 구조의 자료 구조이다.
• 하나의 루트 노드를 가진다.
• 루트 노드는 0개 이상의 자식 노드를 갖는다.
• 자식 노드들 또한 0개 이상의 자식 노드를 갖고, 반복적으로 정의된다.
• 트리는 노드(node)들과 연결하는 간선(edge)들로 구성된다.
• 트리에는 사이클(cycle)이 존재할 수 없다.
• 그래프의 한 종류 (Acyclic Connected Graph / Directed Acyclic Graph)이다.

관련 용어

• 루트 노드 (root node) : 부모가 없는 노드, 트리는 하나의 루트 노드만을 가진다.
• 단말 노드 (leaf node) : 자식이 없는 노드, 말단 노드, 잎 노드, 리프 노드 등으로도 불린다.
• 내부 노드 (internal node) : 단말 노드가 아닌 노드
• 간선 (edge) : 노드를 연결하는 선, link, branch로도 불린다.
• 형제 (sibling) : 같은 부모를 가지는 노드
• 노드의 크기 (size) : 자신을 포함한 자신의 모든 자손 노드의 개수
• 노드의 깊이 (depth) : 루트에서 어떤 노드에 도달하기 위해 거쳐야 하는 간선의 수
• 노드의 레벨 (level) : 트리의 특정 깊이를 가지는 노드의 집합
• 노드의 차수 (degree) : 하위 트리 개수 || 간선 수 = 각 노드가 지닌 가지의 수
• 트리의 차수 (degree of tree) : 트리의 최대 차수
• 트리의 높이(height) : 루트 노드에서 가장 깊숙히 있는 노드의 깊이 (= 최대 레벨)

트리의 특징

• 그래프의 한 종류이다. '최소 연결 트리'라고도 불린다.
• 계층적 특성을 가진다.
• 트리는 DAG(Directed Acyclic Graph)의 한 종류이다. (사이클이 없다.)
• 노드가 N개인 트리는 항상 N-1개의 간선을 갖는다.
• 임의의 노드에서 어떤 노드로 가는 경로는 유일한다
• 한 개의 루트 노드만이 존재하며 모든 자식 노드는 한 개의 부모 노드만을 가진다.
• 순회는 pre-order, in-order, post-order로 이루어진다. 이 3가지 모두 DFS / BFS 안에 있다.
• 트리는 이진트리, 이진 탐색 트리, 균형 트리(AVL 트리, red-black 트리), 이진 힙(최대힙, 최소힙) 등이 있다.

트리의 종류

트리 vs 이진 트리

• 이진 트리
  • 자식 노드의 개수가 0 ~ 2개인 트리
  • Binary Tree 참조
• 트리
  • 자식 노드의 개수에 제한이 없는 트리

이진 트리 vs 이진 탐색 트리

• 이진 탐색 트리 (Binary Search Tree)
  • 모든 노드가 아래와 같은 특정 순서를 따르는 속성이 있는 이진 트리
  • 모든 왼쪽 자식들 ≤ n < 모든 오른쪽 자식들

균형 트리 vs 비 균형 트리

• 균형 트리
  • O(logN) 시간에 insert와 find를 할 수 있을 정도로 균형이 잘 잡혀 있는 트리
  • 레드-블랙 트리, AVL 트리

완전 이진 트리 vs 전 이진 트리 vs 포화 이진 트리

• 완전 이진 트리 (Complete BT)
  • 트리의 모든 높이에서 노드가 꽉 차 있는 이진 트리. 즉, 마지막 레벨을 제외하고 모든 레벨이 완전히 채워져 있다.
• 전 이진 트리 (Full BT / Strictly BT)
  • 모든 노드가 0개 또는 2개의 자식 노드를 갖는 트리
• 포화 이진 트리 (Perfect BT)
  - 전 이진트리이면서 완전 이진트리인 경우
  자세한 내용은 Binary Tree 참조

이진 힙(최소힙, 최대힙)

• 최소 힙(Min Heap)
  • 트리의 마지막 단계에서 오른쪽 부분을 뺀 나머지 부분이 가득 채워져 있는 완전 이진 트리이며, 각 노드의 원소가 자식들의 원소보다 작다.
  • 즉, key(부모 노드) ≤ key(자식 노드)인 완전 이진 트리
  • 가장 작은 값은 루트 노드이다.
  • N개가 힙에 들어가 있으면 높이는 log(N)이다.
• 최대 힙(Max Heap)
  • 원소가 내림차순으로 정렬되어 있다는 점에서만 최소힙과 다르다.
  • 각 노드의 원소가 자식의 원소보다 크다.
• 나중에 따로 정리할 예정

트라이 (trie / 접두사 트리; Prefix Tree)

• n-차 트리(n-ary Tree)의 변형
• 각 노드에 문자를 저장하는 자료구조
• 따라서 트리를 아래쪽으로 순회하면 단어 하나가 나온다.
• 접두사를 빠르게 찾아보기 위한 흔한 방식으로, 모든 언어를 트라이에 저장해 놓는 방식이 있다.
• 유효한 단어 집합을 이용하는 많은 문제들은 트라이를 통해 최적화 가능하다.

트리 구현 방법

트리는 그래프의 한 종류이므로 그래프 구현 방법으로 구현 가능하다.

인접 배열 이용

• 1차원 배열에 자신의 부모 노드만 저장하는 방법
  • 트리는 부모 노드를 0개 또는 1개를 가지기 때문
  • 부모 노드가 0개 : 루트 노드
• 이진 트리의 경우, 2차원 배열에 자식 노드를 저장하는 방법
  • 이진 트리는 각 노드가 최대 두 개의 자식을 갖는 트리이기에 가능
  • ex) A[i][0] → left, A[i][1] → right

인접 리스트 이용

• 가중치가 없는 경우 → 링크드 리스트 변형
• 가중치가 있는 경우 → 가중치 값 추가

Reference

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