[자료구조] 트리, Tree

면접을 준비하면서 정리한 CS 자료들을 하나씩 올려보려 한다!
먼저 트리 자료구조이다.

트리, Tree 란?

트리는 값을 가지는 노드(node) 와 노드들을 연결해주는 간선(edge) 들로 이루어져 있는 자료구조이다. 모든 노드들이 0개 이상의 자식 노드를 가지며 부모-자식 관계가 존재한다.

이러한 트리가 가지는 특징이 몇가지 있는데,

• 트리에는 사이클이 존재할 수 없다.
  • 만약 사이클이 생성된다면 그 순간 그 자료구조는 트리가 아닌, 그래프(graph) 이다!
• 루트 노드로 부터 특정 노드로 가는 경로는 오직 하나뿐이다.
• 만약 트리 내 노드 갯수가 N개라면 간선 갯수는 N-1 개이다. 서로다른 두 노드를 연결하는 간선은 오직 하나이기 때문
• 트리 내에 다시 트리가 존재하는 재귀적 구조를 갖는다.
• 데이터를 순차적으로 저장하지 않는다. 비선형 자료구조이고 방향이 없는 그래프 구조이다.
• 노드 사이에 부모-자식 관계가 존재하는 특징을 가지며 모든 자식노드는 단 하나의 부모 노드를 갖는다.

트리 종류

1. 이진 트리 (Binary Tree)
   각 노드의 차수(자식 수)가 2 이하인 트리

2. 이진 탐색 트리 (Binary Search Tree, BST)
   순서화된 이진트리로 노드의 왼쪽 자식의 값은 부모보다 작고, 오른쪽 자식은 부모보다 큰 값을 가진다.

3. m원 탐색 트리 (m-way Search Tree)
   최대 m개의 서브 트리를 갖는 탐색 트리, 이진 탐색 트리의 확장된 형태로 트리의 옾이를 줄이기 위해 사용한다.

   ex) 4-way search tree
   

4. 균형 트리 (Balanced Tree, B-Tree)
   m원 탐색 트리에서 높이 균형을 유지하는 트리이다. (height balanced m-way tree)

트리 순회 방식

1. 전위 순회, pre-order
   : 루드 노드 -> 왼쪽 자식 노드 -> 오른쪽 자식 노드
   1-2-4-8-9-5-10-11-3-6-13-7-14

2. 중위 순회, in-order
   : 왼쪽 자식 노드 -> 루트 노드 -> 오른쪽 자식 노드
   8-4-9-2-10-5-11-1-6-13-3-14-7

3. 후위 순회, post-order
   : 왼쪽 자식 노드 -> 오른쪽 자식 노드 -> 루트 노드
   8-9-4-10-11-5-2-13-6-14-7-3-1

4. 레벨 순회, level-order
   루트 노드부터 계층별로 순회
   1-2-3-4-5-6-7-8-9-10-11-13-14

트리 자료구조 사용 사례

• 계층적으로 데이터를 저장할 때
• 효율적인 검색이 필요할 때
  • 이진 트리 검색을 통해 logN 에 검색 가능
• 힙(heap) 구조
• 데이터 베이스 인덱싱
  • B-Tree, B+ Tree, AVL Tree
• Trie