[파이썬 알고리즘 인터뷰] 14장 - 트리

이 글은 "파이썬 알고리즘 인터뷰 (박상길 지음)"을 읽고 주관적으로 요약한 글입니다. 

---

출처 : https://www.onlybook.co.kr/entry/algorithm-interview

 

• 트리
  • 계층형 트리 구조를 시뮬레이션 하는 추상 자료형
  • 서로 연결된 노드의 집합
  • 재귀로 정의된 자기 참조 자료구조
    - Recursively Defined Self-Referential
    - 즉, 트리는 자식도 트리, 그 자식도 트리 (서브트리)

• 트리의 명칭
  
  • 차수 (Degree)
    - 자식 노드의 개수
  • 크기 (Size)
    - 차수 + 자신을 포함(1)
  • 깊이 (Depth)
    - 루트에서 현재 노드까지의 거리
  • 높이 (Height)
    - 현재 노드에서 리프 노드까지의 거리 (가장 깊은)
• 그래프 vs 트리
  • 트리는 순환(cycle)이 없어야 함
    - 간선을 따라 탐색했을 때, 이미 탐색된 노드를 다시 만나지 않음
  • 트리는 부모 -> 자식 단방향
  • 트리는 부모를 1개 가짐
  • 트리는 루트를 1개 가짐
• 이진 트리 (BT, Binary Tree)
  • 모든 노드의 차수가 2 이하를 만족하는 트리
  • 이진 트리를 사용하는 이유
    - 왼쪽, 오른쪽 자식 노드 구조로 간결함
    - 여러 알고리즘 구현도 간단하게 가능
  • 종류
    1. 정 이진 트리 (Full BT)
       - 모든 노드가 0 또는 2개 자식 노드를 가짐
    2. 완전 이진 트리 (Complete BT)
       - 마지막 레벨을 제외한 모든 레벨에 노드가 완전히 채워짐
       - 마지막 레벨은 가장 왼쪽부터 채워짐
    3. 포화 이진 트리 (Perfect BT)
       - 모든 레벨의 노드가 완전히 채워짐
       - 모든 리프노드가 동일한 깊이를 가짐
• 이진 탐색 트리 (BST, Binary Search Tree)
  • 정렬된 이진 트리
    - 왼쪽 서브트리는 현재 노드보다 작은 값
    - 오른쪽 서브트리는 현재 노드보다 같거나 큰 값
  • 탐색의 시간 복잡도가 O(log n)
  • 그러나 트리의 모양이 균형을 제대로 이루지 못하면 O(n)
  • 이를 위해 '자가 균형 이진 탐색 트리'가 존재
• 자가 균형 이진 탐색 트리 (Self-Balancing BST)
  • 높이를 가능한 낮아지도록 유지하는 트리 구조
  • AVL 트리 / 레드-블랙 트리
  • 자바의 해시맵
    - 해시 테이블의 개별 체이닝시 연결 리스트와 레드-블랙 트리 병행 저장
    - 효율적인 저장구조
• 트리 순회 (Traversal)
  • 트리 자료구조에서 각 노드를 정확히 한 번 방문하는 과정
  • 종류
    1. 전위 순회 (Pre-Order)
       - NLR
    2. 중위 순회 (In-Order)
       - LNR
    3. 후위 순회 (Post-Order)
       - LRN
• 신장 트리 (Spanning Tree)
  • 정의
    - 그래프 내의 모든 정점을 포함하고 사이클이 없는 트리 (각 노드를 연결하는 간선이 1개)
    - 따라서 간선의 개수는 V - 1 (모든 노드가 연결되며 사이클이 없는 경우는 V-1개를 넘지 않음)
  • 최소 신장 트리 (Minimal Spanning Tree)
    - 간선의 가중치 합이 가장 작은 Spanning Tree
    - [주의] 노드와 노드 사이의 최소 가중치 경로가 아님