0725-tree.md

2020.07.25

📚공부한 거 List📚

• 트리 - 23. 우선순위 큐와 힙
• 트리 - 25. 상호 배타적 집합(disjoint set)

---

[종만북] 우선순위 큐와 힙

우선순위가 가장 높은 자료가 가장 먼저 꺼내지는 큐Queue

균형 잡힌 이진 검색 트리를 사용하여 원소들을 우선순위로 정렬해두면 최대 원소를 찾아 삭제하는 일과 원소 삽입 연산을 **O(NlgN)**동안 할 수 있다.

하지만, 균형 잡힌 이진 검색 트리로 우선순위 큐를 구현하는 것은 너무나 무리...(주객전도)

그래서 보다 간단한 구조를 가진 **힙(heap)**을 사용하여 우선순위 큐를 구현한다.

how? 우선순위와 실제 자료의 쌍을 담는 heap을 만들고, 대소솬계를 비교할 때는 우선순위를 비교하면 된다.

heap의 구현 방식

◾️ (최대)힙의 중요한 특징

1. 부모 노드가 가진 원소는 항상 자식 노드가 가진 원소 이상이다. (=힙의 대소 관계 규칙)
2. 힙의 대소 관계 규칙에 따라 트리에서 가장 큰 원소는 항상 트리의 루트에 들어간다.
3. (모양규칙) 마지막 레벨을 제외한 모든 레벨에 노드가 꽉 차 있다.
4. (모양규칙) 마지막 레벨에 노드가 있을 경우, 항상 가장 왼쪽부터 순서대로 채워져 있다.
5. (특징 3 + 특징 4 만족 시) 힙의 높이는 **O(lgN)**이다.

*트리의 레벨 = 깊이가 같은 노드들의 집합

|

✏️ 배열을 이용해 heap구현하기

일차원 배열 A[]의 각 원소와 힙의 노드들을 일대일 대응하면 다음의 규칙을 얻는다.

1. A[i]에 대응되는 노드의 왼쪽 자손은 A[2*i + 1]
2. A[i]에 대응되는 노드의 오른쪽 자손은 A[2*i + 2]
3. A[i]에 대응되는 노드의 부모는 A[(i-1)/2]에 대응된다. (나눗셈 결과는 내림)

⌨️ 정수를 저장하는 힙

vector<int> heap;

힙의 원소의 개수는 동적 배열의 크기가 된다.

|

✏️ 원소 삽입

모양 규칙을 먼저 만족시킨 후, 대소 관계 규칙을 만족시킨다.

원소 삽입 과정은 다음과 같다.

1. 새 노드를 항상 heap[] 마지막에 추가한다.
2. 새 원소를 자신의 부모 노드가 가진 원소와 비교하고, 부모 노드가 가진 원소가 더 작으면 두 원소의 위치를 바꿔준다.
3. 새 원소가 더 크거나 같은 원소를 가진 부모 노드를 만나거나, 루트에 도달할 때까지 <과정 2>를 반복한다.

⌨️ 정수 원소를 갖는 최대 힙에 새 원소 삽입하기

/*
 * 정수 원소를 담는 최대 힙 heap에 새 원소 newValue를 삽입하는 함수
 * @param heap [정수 원소를 담는 최대 힙]
 * @param newValue [새 원소]
 */
void push_heap(vector<int>& heap, int newValue) {
  heap.push_back(newValue); //일단 모양 규칙을 만족시키기 위해 heap 맨 끝에 원소 삽입
  int idx = heap.size() - 1; //초기 새 원소의 위치 
  //idx>0 : 루트에 도달하거나
  //heap[(idx-1)/2]<heap[idx] : 부모노드값이 newValue보다 작으면 
  while(idx>0 && heap[(idx-1)/2]<heap[idx]) {
    swap(heap[idx], heap[(idx-1)/2]); //두 노드를 바꾼다
    idx = (idx-1)/2; //newValue의 위치를 수정
  }
}

⏱Time-Complexity⏱

O(lgN)

|

✏️ 최대 원소 꺼내기

◾️ 모양 규칙 만족 과정

1. 힙의 마지막 노드를 지운다.
2. 마지막 노드에 있던 원소를 루트에 덮어씌운다.

◾️ 대소 관계 규칙 만족 과정

1. 트리의 바닥에 도달하거나, 두 자손이 모두 부모노드이하의 원소를 갖고 있을 때까지 <과정 2> 반복
2. 두 자식이 가지고 있던 원소 중 큰 노드를 부모노드와 바꿔준다.

⌨️ 정수 원소를 갖는 최대 힙에서 최대 원소 삭제하기

/*
 * 정수를 담는 최대 힙 heap에서 heap[0]을 제거한다.
 * @param heap [정수를 담는 최대 힙]
 */
void pop_heap(vector<int>& heap) {
  heap[0] = heap.back(); //힙의 루트에 마지막 값을 넣는다.
  heap.pop_back(); //마지막 노드는 삭제
  int here = 0; //마지막 값의 현재 위치
  while(true) {
    int left = here*2 + 1, right = here*2 + 2;//left:왼쪽 자식노드, right:오른쪽 자식노드
    if(left >= heap.size()) break; //리프에 도달한 경우 중단
    int next = here; //현재 위치를 next에 저장해놓고
    if(heap[next] < heap[left]) //현재노드(부모)보다 왼쪽자식노드 값이 더 크면
      next = left; //현재노드위치를 왼쪽자식노드 위치로 설정
    if(right < heap.size() && heap[next] < heap[right]) //현재노드(부모)보다 오른쪽자식노드 값이 더 크면
      next = right; //현재노드위치를 오른쪽자식노드 위치로 설정
    if(next == here) break; //부모노드의 값이 자식노드 값보다 크다면(=대소관계규칙을 만족한다면) while문 중단
    swap(heap[here], heap[next]); //아니라면 노드를 서로 바꿔준다
    here = next; //현재 위치 갱신
  }
}

⏱Time-Complexity⏱

O(lgN)

|

📝예제::변화하는 중간 값

문제 : 텅 빈 수열에서 시작해서 각 수가 추가될 때마다 중간 값을 계산하는 프로그램을 작성.

수열의 길이가 짝수일 때는 가운데 있는 두 값 중 보다 작은 것을 수열의 중간 값이라고 정의한다.

⚡️keypoint⚡️

1. 트립을 이용해 해결하기

2. 주어진 수열의 숫자들을 정렬한 뒤, 앞의 절반을 최대힙에, 뒤의 절반을 최소힙에 넣어 푼다. 이 경우 다음의 불변식으로 표현할 수 있다.

   1. 최대 힙의 크기는 최소 힙의 크기와 같거나, 하나 더 크다.
   2. 최대 힙의 최대 원소는 최소 힙의 최소 원소보다 작거나 같다.

   그 결과, 이 수열의 중간 값은 항상 최대 힙의 루트에 있게 된다.

🔑**해답(코드)**🔑

/*
 * 변화하는 중간 값 문제의 입력 생성하기
 */
struct RNG {
  int seed, a, b;
  RNG(int _a, int _b) : a(_a), b(_b), seed(1983) {}
  int next() {
    int ret = seed;
    seed = ((seed * (long long)a) + b) % 20090711;
    return ret;
  }
};

/*
 * <iostream>, <queue>, <vector>
 * 힙을 이용해 변화하는 중간 값 문제를 해결하는 함수의 구현
 * @param n []
 * @param rng []
 */
int runningMedian(int n, RNG rng) {
  priority_queue<int, vector<int>, less<int>> maxHeap;
  priority_queue<int, vector<int>, greater<int>> minHeap;
  int ret = 0;
  for(int cnt=1; cnt<=n; ++cnt) {
    if(maxHeap.size() == minHeap.size()) maxHeap.push(rng.next());
    else minHeap.push(rng.next());
    if(!minHeap.empty() && !maxHeap.empty() && minHeap.top()<maxHeap.top()) {
      int a = maxHeap.top();
      int b = minHeap.top();
      maxHeap.pop(); minHeap.pop();
      maxHeap.push(b); 
      minHeap.push(a);
    }
    ret = (ret + maxHeap.top()) % 20090711;
  }
  return ret;
}

⏱Time-Complexity⏱

O(lgN)

---

[종만북] 상호 배타적 집합(disjoint set)

유니온-파인트(Union-Find)

상호 배타적 집합(disjoint set)

Union-Find 자료구조란?

👉 공통 원소가 없는, 다시 말해 상호 배타적인 부분 집합들로 나눠진 원소들에 대한 정보를 저장하고 조작하는 자료구조

n개의 원소들로 이뤄진 집합을 표현하기 위해서, 원소를 0부터 n-1까지로 표현하고 각 1개의 원소를 포함하는 n개의 집합을 만든다.

Union-Find에서 사용되는 세 가지 연산

1. 초기화 : n개의 원소가 각각의 집합에 포함되어 있도록 초기화
2. union : 두 원소 a,b가 주어질 때 이들이 속한 두 집합을 하나로 합친다.
3. find : 어떤 원소 a가 주어질 때, 이 원소가 속한 집합을 반환한다.

배열로 상호 배타적 집합 표현하기

belongsTo[i] : i번 원소가 속하는 집합의 번호

초기화 : belongsTo[i] = i

😵**배열로 상호 배타적 집합 표현하기의 문제점 **

Union연산을 할 때, belongTo의 원소순환에 O(n)시간이 소요된다.

트리를 이용한 상호 배타적 집합의 표현

한 집합에 속하는 원소들을 하나의 트리로 묶어주어, 상호 배타적 집합 자료구조를 트리들의 집합으로 표현하는 것을 의미.

두 원소가 같은 집합에 있는지 확인하는 방법 : 속한 트리의 루트가 같은지 확인하면 된다.

전체 코드

struct NaiveDisjointSet {
  vector<int> parent;
  NaiveDisjointSet(int n) : parent(n) { //아래 복사 생성자 설명 참고
    for(int i=0; i<n; ++i) parent[i] = i;
  }
  //찾기 연산:find
  int find(int u) const {
    if(u == parent[u]) return u;
    return find(parent[u]);
  }
  //합치기 연산:union
  void merge(int u, int v) {
    u.find(u);
    v.find(v);
    if(u==v) return;
    parent[u] = v;
  }
};

🚩🔎C++::default copy constructor_디폴트 복사 생성자

#include <iostream>
#include <vector>
using namespace std;

class Sample {
    vector<int> num;
    int n = num.size();
    public : 
        Sample(int param) : num(param) {
            for(int i=0; i<n; ++i) num[i] = i;
        }
        void printNum() {
            for(int i=0; i<n; ++i) cout<<num[i]<<endl;
        }
};
int main()
{
    vector<int> a = {1,2,3};
    Sample first(3);
    Sample num = first;
    num.printNum();
    return 0;
}

실행결과 : 0 1 2

• find 연산

  • 원소가 속한 트리의 루트를 찾는다.

  • 모든 자식 노드가 부모 노드에 대한 포인터를 가지고 있어야 한다.

  • ⏱Time-Complexity⏱ : 해당 트리의 높이에 비례하는 시간이 소요된다.

  • int find(int u) const {
      if(u == parent[u]) return u;
      return find(parent[u]);
    }

• union 연산

  • 각 트리의 루트를 찾고, 하나를 다른 한쪽의 자손으로 포함시키면 된다.

  • ⏱Time-Complexity⏱ : 해당 트리의 높이에 비례하는 시간이 소요된다.

  • void merge(int u, int v) {
        u.find(u);
        v.find(v);
        if(u==v) return;
        parent[u] = v;
      }
    

상호 배타적 집합의 최적화

트리를 사용해서 상호 배타적 집합을 표현할 경우 생기는 문제점

👉 연산의 순서에 따라 자칫 트리가 한쪽으로 기울어질 수 있다.

해결방안

👉 랭크(rank)에 의한 합치기(union-by-rank) 최적화 : 두 트리를 합칠 때, 항상 높이가 더 낮은 트리를 더 높은 트리 밑에 집어넣음으로써 트리의 높이가 높아지는 상황을 방지한다.