[Data Structure] Tree

💫 트리는 노드로 이루어진 자료 구조
✅ 트리는 하나의 루트 노드를 갖는다.
✅ 루트 노드는 0개 이상의 자식 노드를 갖고 있다.
✅ 그 자식 노드 또한 0개 이상의 자식 노드를 갖고 있고, 이는 반복적으로 정의된다.

• 노드(node)들과 노드들을 연결하는 간선(edge)들로 구성되어 있다.
  • 트리에는 사이클(cycle)이 존재할 수 없다.
  • 노드들은 특정 순서로 나열될 수도 있고, 그럴 수 없을 수도 있다.
  • 각 노드는 부모 노드로의 연결이 있을 수도 있고, 없을 수도 있다.
  • 각 노드는 어떤 자료형으로도 표현 가능하다.
• 비선형 자료구조로 계층적 관계를 표현한다.
• 그래프의 한 종류이다.
  • Cycle이 없는 하나의 연결 그래프(Connected Graph)
  • DAG(Directed Acyclic Graph, 방향성이 있는 비순환 그래프)

2. 트리 관련 용어

   

   루트 노드	부모가 없는 노드, 트리는 하나의 루트 노드만을 가진다.
   단말 노드	자식이 없는 노드
   내부 노드	단말 노드가 아닌 노드
   간선	노드를 연결하는 선 ( ≒ link, branck )
   형제	같은 부모를 가지는 노드
   노드의 크기	자신을 포함한 모든 자손 노드의 개수
   노드의 깊이	루트에서 어떤 노드에 도달하기 위해 거쳐야 하는 간선의 수
   노드의 레벨	트리의 특정 깊이를 가지는 노드의 집합
   노드의 차수	하위 트리 개수 / 간선 수 ⇒ 각 노드가 가진 가지의 수
   트리의 차수	트리의 최대 차수
   트리의 높이	루트 노드에서 가장 깊숙히 있는 노드의 깊이

3. 트리 특징

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

4. 트리 종류

   • 이진 트리 (Binary Tree)

     • 각 노드가 최대 두개의 자식을 갖는 트리
     • 모든 트리가 이진 트리는 아님
     • 이진 트리 순회 방법

       중위 순회(in-order traversal)	Left → Root → Right
       전위 순회(pre-order traversal)	Root → Left → Right
       후위 순회(post-order traversal)	Left → Right → Root

   • 이진 탐색 트리 (Binary Search Tree)

     • 모든 노드가 아래와 같은 특정 순서를 따르는 속성이 있는 이진 트리
     • 모든 왼쪽 자식들 ≤ n < 모든 오른쪽 자식들 (모든 노드 n에 대해서 반드시 참)
       

   • 균형 트리

     • $O(logN)$ 시간에 insert와 find를 할 수 있을 정도로 균형이 잘 잡혀 있는 경우

   • 완전 이진 트리 (Complete Binary Tree)

     

     • 트리의 모든 높이에서 노드가 꽉 차 있는 이진 트리 → 마지막 레벨을 제외하고 모든 레벨이 완전히 채워져 있음
     • 마지막 레벨은 꽉 차 있지 않아도 되지만 노드가 왼쪽에서 오른쪽으로 채워져야 함
     • 마지막 레벨 $h$에서 $(h$~$2h-1)$개의 노드를 가질 수 있음
     • 가장 오른쪽의 단말 노드가 (아마도 모두) 제거된 포화 이진 트리
     • 완전 이진 트리는 배열을 사용해 효율적으로 표현이 가능함

   • 전 이진 트리 (Full Binary Tree 또는 Strictly Binary Tree)

     

     • 모든 노드가 0개 또는 2개의 자식 노드를 갖는 트리

   • 포화 이진 트리 (Perfect Binary Tree)

     

     • 전 이진 트리이면서 완전 이진 트리인 경우
     • 모든 말단 노드는 같은 높이에 있어야 하며, 마지막 단계에서 노드의 개수가 최대가 되어야 함
     • 모든 내부 노드가 두 개의 자식 노드를 가짐
     • 모든 말단 노드가 동일한 깊이 또는 레벨을 갖음
     • 노드의 개수가 정확히 $2^k-1$개여야 함 ( $k$ : 트리의 높이 ) → 흔하게 나타나는 경우가 아님. 이진 트리가 모두 포화 이진 트리일 것이라고 생각말 것

   • 이진 힙 (최소힙과 최대힙)

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

   • 트라이 (Trie) → 접두사 트리(Prefix Tree)라고도 부름

     • n-차 트리의 변종
     • 각 노드에 문자를 저장하는 자료구조 → ∴ 트리를 아래쪽으로 순회하면 단어 하나가 나옴
     • 접두사를 빠르게 찾아보기 위한 흔한 방식으로, 모든 언어를 트라이에 저장해 놓는 방식이 있음
     • 유효한 단어 집합을 이용하는 많은 문제들은 트라이를 통해 최적화할 수 있음

5. 트리 구현 방법

   • 인접 배열 이용
     • 1차원 배열에 자신의 부모 노드만 저장하는 방법 ∵ 트리는 부모 노드를 0개 또는 1개를 가지기 때문
       
     • 이진 트리의 경우, 2차원 배열에 자식 노드를 저장하는 방법 ∵ 이진 트리는 각 노드가 최대 두개의 자식을 갖는 트리이기 때문
       
   • 인접 리스트 이용
     • 가중치가 없는 트리의 경우
     • 가중치가 있는 트리의 경우

6. 그래프와 트리의 차이

   	그래프	트리
   정의	노드와 그 노드를 연결하는 간선을 하나로 모아 놓은 자료구조	그래프의 한 종류로 DAG(방향성이 있는 비순환 그래프)의 한 종류
   방향성	방향 그래프, 무방향 그래프 모두 존재	방향 그래프
   사이클	사이클 가능 자체 간선(self-loop)도 가능 순환 그래프 비순환 그래프 모두 존재	사이클 불가능 자체 간선(self-loop)도 불가능 비순환 그래프
   루트 노드	루트 노드의 개념 없음	한 개의 루트 노드만 존재하고, 모든 자식 노드는 한 개의 부모 노드만을 가짐
   부모-자식	부모-자식 개념 X	부모-자식 개념 O ∴ top-bottom 또는 bottom-top으로 이루어짐
   모델	네트워크 모델	계층 모델
   순회	DFS, BFS	DFS, BFS안의 Pre-, In-, Post-order
   간선의 수	그래프에 따라 간선의 수가 다름, 간선이 없을 수도 있음	노드가 N인 트리는 항상 N-1의 간선을 가짐
   경로		임의의 두 노드간의 경로는 유일
   예시 및 종류	지도, 지하철 노선의 최단 경로, 전기 회로의 소자들, 도로(교차점과 일방 통행길), 선수 과목	이진 트리, 이진 탐색 트리, 균형 트리, 이진 힙 등

➰ Preferences

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