[알고리즘 개념정리] 9. 트리

**본 포스팅은 22Winter 신촌캠프 초급반 강사 raararaara님의 강의를 참고하여 작성하였습니다.**

 

 

트리 (Tree)

• Connected Acyclic Undirected Graph
  모든 정점이 이어져있음(연결 그래프) / 사이클 존재하지 않음 / 방향성 없음
• 계층형 자료구조
  리프노드를 제외한 노드들은 T1, T2, ... Tn을 root로 하는 서브트리들을 가진다.
• 부모/자식, 형제(부모 노드가 같음), 조상(부모 노드들의 집합), 자손(자식 노드들의 집합),
  리프 노드, 서브 트리(어떤 노드 t와 그 자손들로 구성된 트리), 포레스트(트리가 여러개)

• 간선의 개수 = 정점의 개수 -1
  : sparse graph 이므로 인접리스트로 표현할 수 있다.
• 임의의 서로 다른 두 정점 사이의 경로가 유일 (Acyclic)
• 재귀적인 구조 (subtree)

  -트리 순회

    vector<int> adj[1001];

    void dfs(int cur, int par){ //부모-> 자식 순회
        for(int &next:adj[cur]){
            if(next==par) continue; //부모는 들렸었으므로 스킵
            //
        }
    }

정점 N개, 간선 N-1개 -> O(N)  ∵그래프 탐색과 유사. O(|v|+|E|) = O(2N) = O(N) 

 

 

이진 트리 (Binary Tree)

•  모든 정점이 2개 이하의 자식을 가지는 트리

• 자식이 2개이기 때문에 left, rignt로 방향이 정의된다.
• 높이가 h인 이진트리의 최대 노드 수는 2^h - 1 개 이다.
• 노드 개수가 N인 이진트리의 최소 높이는 대략 logN이다.

• 포화 이진 트리 (Full Binary Tree)
  : 리프 노드를 제외한 모든 정점의 자식이 2개인 트리
• 완전 이진 트리 (Complete Binary Tree)
  : 마지막 레벨을 제외하고 모든 레벨이 완전히 채워져 있으며,
    마지막 레벨은 왼쪽부터 채워진 트리
  
  -> 위쪽, 왼쪽부터 차례로 index를 1, 2, 3, ...으로 부여했을 때 (1-based!!)
      부모 idx 를 i 라고 하면 자식은 2i 와 2i+1 이다.

 

- 전위 순회 (Preorder) : 루트 - 왼쪽 서브트리 - 오른쪽 서브트리 순
- 중위 순회 (Inorder) : 왼쪽 서브트리 - 루트 - 오른쪽 서브트리 순
- 후위 순회 (Postorder) : 왼쪽 서브트리 - 오른쪽 서브트리 - 루트 순

    void inorder(int par){
        if(childL[par]) inorder(childL[par]); //왼
        cout<< par; //중위순회
        if(childR[par]) inorder(childR[par]); //오
    }

 

 

 

우선순위 큐 & 힙 (Priority Queue & Heap)

우선순위 큐

• 입력된 순서에 상관없이, 우선순위가 가장 높은 자료가 가장 먼저 꺼내지는 자료구조

• top (우선순위가 가장 높은 원소 반환), push, pop (top에 있는 원소 제거)

  배열로 구현하면 접근은 O(1)인데 삽입/삭제 후 미는게 O(N)이다.. 어떡하지..? 
  이진 트리의 최소높이가 logN이니까 트리로 구현해볼까?? 그럼 log시간으로 줄일 수 있을것같아!!

힙

• 완전 이진 트리 (Complete Binary Tree) + heap property
  우선순위 큐 구현에 쓰이는 자료구조!!

• 항상 완전 이진 트리를 만족한다!
• 루트 노드의 우선순위 > 해당 서브트리의 노드들의 우선순위
• 삽입/삭제: O(logN)  , 접근: O(1)
   ㄴ이유? 최대로 tree높이만큼의 swap이 일어남

 

  - std::priority_queue
     : 디폴트가 max heap

    // min heap 구현 1
    std::priority_queue<int, std::vector<int>, std::greater<int>> pq;
       // sort(v.begin(), v.end(), greater<>()) 하면 내림차순 정렬이지만
       // heap은 greater하면 오름차순(작은 값이 먼저)이다.

 

    // min heap 구현 2
    std::priority_queue<int> pq;
    ...
    // to push 1, 2, 3
    pq.push(-1);
    pq.push(-2);
    pq.push(-3);

 

 

 

이진 검색 트리 (Binary Search Tree)

• 왼쪽 서브트리에는 루트보다 작은 원소들을,
  오른쪽 서브트리에는 루트보다 큰 원소들을 배치시켜 특정 원소의 존재 여부 탐색

• 넣는 순서에 따라 생김새가 달라질 수 있다.
• 탐색시간(높이) 최악: O(N), 평균: O(logN)

• 균형잡힌 이진 검색 트리 (Balanced BST)
  : 입력 순서에 따라 상관없이 트리의 높이를 최대한 낮게 만들어줄 필요가 있다. O(logN)

   - std::set, std::map
      : Balanced BST (Red-Black Tree)기반으로 만들어진 탐색형 자료구조
       탐색, 삽입, 삭제에 평균 O(logN)의 시간복잡도가 들지만 상대적으로 느린편(거의 logN*logN인 느낌)

 

 

 

 

---

관련 문제

14244. 트리 만들기 (정답코드)
15681. 트리와 쿼리 (정답코드)
2022.02.11 - [PS/Baekjoon] - [백준/C++] 15942번: Thinking Heap(G2)
19598. 최소 회의실 개수 (정답코드) 우선순위 큐
5639. 이진 검색 트리 (정답코드) 전위/후위 순회
1351. 무한 수열 (정답코드) dp, map

2022.03.03 - [PS/Baekjoon] - [백준/C++] 20924번: 트리의 기둥과 가지(G4) bfs
7662. 이중 우선순위 큐 (정답코드) map
21939. 문제 추천 시스템 Version 1 (정답코드) map
11725. 트리의 부모 찾기 (정답코드)
1991. 트리 순회 (정답코드)
2644. 촌수계산 (정답코드)
11279. 최대 힙 (정답코드)
1655. 가운데를 말해요 (정답코드)
14425. 문자열 집합 (정답코드) Polynomial Rolling hash
20292. 컨설팅