05_tree

5. Tree

• 각 노드가 계층적으로 연결된 비선형적 자료구조
• 나무의 뿌리가 제일 위에, 잎이 제일 아래에 있어 나무를 뒤집어 놓은 모양과 같음
• root : 최상단 노드
• leaf : 최하단 노드
• child : 링크로 연결된 하위 노드
• parent : 링크로 연결된 상위 노드
• subtree : 'child'를 'root'로 하는 트리
• depth : 'root' 기준 레벨, height : 'leaf' 기준 레벨

5.1. Binary Search Tree

5.2. Heap(priority queue)

5.3. Trie(prefix tree)

생각해보기

💬 트리가 사용되는 상황

• 파일시스템(디렉토리 구조), 검색엔진, 데이터베이스관리시스템(DBMS), 라우터 알고리즘 등
• 일상 : 조직도, 족보 등

💬 이진트리의 종류

• 이진트리(Binary Tree) : 각각의 노드가 최대 2개의 child를 갖는 트리
  • 정 이진트리 (full binary tree) : 모든 노드가 0개 또는 2개의 child를 갖는 이진트리
  • 균형 이진트리 (balanced tree) : 좌우 subtree의 height가 1 이상 차이나지 않는 이진트리
  • 포화 이진트리 (perfect binary tree) : 꽉 찬 이진트리
  • 완전 이진트리 (complete binary tree) : 마지막 레벨을 제외하고 '포화이진트리'인 이진트리

💬 배열로 트리를 구현하려면?

• index 0은 비우고 index 1은 root, index 2는 root의 child...로 순서대로 배치함
• 이진트리인 경우, index p의 child는 index 2p 와 index 2p + 1이며, index c의 parent는 index c/2임
• 트리의 높이가 높아지고 한 쪽으로 기울어질 수록 비어있는 공간이 많아져서 메모리 효율이 떨어짐

💬 트리순회의 종류

• 트리순회 : 각각의 노드를 딱 한 번만 방문하는 과정
• 깊이우선탐색 (DFT, Depth First Search)
  • 전위 순회 (pre_order traversal) : Visit - Left - Right 순서
  • 중위 순회 (in_order traversal) : Left - Visit -Right 순서
  • 후위 순회 (post_order traversal) : Left - Right - Vist 순서
• 너비우선탐색 (BFS, Breadth First Search)
  • 레벨 순회 (level_order traversal) : Root - ... - Leaf 순서

💬 상태공간트리(State-Space Tree)란?

• 해를 찾기위해 탐색해야 하는 모든 노드를 포함하는 트리
• 되추적기법 (Backtracking) : DFS방식으로 '상태공간트리'를 탐색하여 해를 찾는 알고리즘
• 분기한정법 (Branch & Bound) : 방식에 제한없이 '상태공간트리'를 탐색하여 해를 찾는 알고리즘