[Data Structure] Tree, Binary Tree (+heap)

트리

• 노드(정보의 단위. 어떤 정보를 가지고 있는 개체)와 노드의 연결(간선, edge)로 표현.
• 그래프 자료구조의 일종. DB 시스템이나 파일 시스템 같은 곳에서 많은 양의 데이터 관리 위한 목적으로 사용
  • 연결된 정보 저장하는 인접리스트로 구현
  • 비선형 자료구조, 계층적 자료구조
• Connected acyclic (undirected) graph 방향성이 존재하지 않고 사이클이 없는 연결 그래프
• 트리 자료구조의 특징
  1. 부모 노드와 자식 노드의 관계로 표현
     • 형제: 부모 노드가 같은 두 노드의 관계
     • 조상/자손: 부모/자식 노드들의 집합
  2. 루트 노드: 최상단 노드
  3. 단말 노드: 최하단 노드. 리프 노드.
  4. 서브 트리: 트리에서 일부를 떼어낸 것. 일부 떼도 트리 구조.
  5. 포레스트: 트리가 여러 개! 포레스트는 트리가 아님! 각 트리끼리는 연결이 안 돼있기 때문!
  6. 파일 시스템처럼 계층적이고 정렬된 데이터 다루기에 적합
• 성질
  • 간선의 개수 = 정점(노드)의 개수 - 1 정점 두 개를 연결한 게 간선
  • 임의의 서로 다른 두 정점 사이의 경로가 유일. 사이클 없음.
  • 각 노드들이 서로 다른 자식을 가짐
  • 재귀적인 구조

---

이진 트리 (Binary Tree) (+힙)

• 정의
  • 모든 정점이 2개 이하의 자식을 가지는 트리
• 성질
  • 자식이 2개이기 때문에 방향이 정의됨 (Left, Right)
  • 높이가 h인 이진트리의 최대 노드 수는 2$^ℎ$ − 1개
• 포화 이진 트리(Full binary tree)
  • 리프 노드를 제외한 모든 정점의 자식이 2개인 트리
  • 정점이 N개인 포화 이진 트리의 높이: 𝑙𝑜𝑔𝑁
• 완전 이진 트리(Complete binary tree)
  • 마지막 레벨을 제외하고 모든 레벨이 완전히 채워져 있으며, 마지막 레벨은 왼쪽부터 채워진 트리
    • 위쪽, 왼쪽부터 차례로 index를 1, 2, 3, …으로 부여했을 때
      • 부모와 자식의 index 관계 : 부모 𝑖 → 왼쪽 자식 2𝑖, 오른쪽 자식 2𝑖 + 1
      • 자식과 부모의 index 관계 : 자식 2𝑖 혹은 2𝑖 + 1 → 부모: 2𝑖자식 // 2
  • 힙(heap)
    • 완전 이진 트리의 일종. Balanced POT(Partially Ordered Trees)
    • index 사용 가능한 array로 구현. (linked list 사용할 경우 마지막 위치 찾는 게 복잡해서)
    • 우선순위 큐 구현에 사용
    • 여러 값 중 최댓값/최솟값을 빠르게 찾아내도록 만들어진 자료구조
    • 이진 트리와 달리 중복된 값 허용
    • $O(NlogN)$ 노드 N개 * $logN$
      • 데이터 변경→ $O(logN)$
        • 삽입 - 트리의 leaf node(자식이 없는 노드)에 삽입, 크기 따라 부모 노드와 교환. 트리 높이만큼 스왑
        • 삭제 - root node(우선순위가 가장 큰 것, 최댓값) 삭제함. 빈자리에는 힙의 마지막 노드 가져오며 재구성
    • 종류
      • 최대 힙(Max Heap): 부모 노드 ≥ 자식 노드. 우선 순위가 높은 큰 값이 먼저 삭제
      • 최소 힙 (Min Heap): 부모 노드 ≤ 자식 노드. 우선 순위가 높은 작은 값이 먼저 삭제
• 이진 트리 순회
  • 전위 순회(Preorder): 루트 – 왼쪽 서브트리 – 오른쪽 서브트리 순
  • 중위 순회(Inorder): 왼쪽 서브트리 – 루트 – 오른쪽 서브트리 순
  • 후위 순회(Postorder): 왼쪽 서브트리 –오른쪽 서브트리 – 루트 순

---

참고링크

• ICPC 신촌 2022 겨울 알고리즘 캠프 - 트리
• https://github.com/seohyun319/CS_I/tree/main/01. DataStructure