[ 자료구조 ] 머지 소트 트리(Merge Sort Tree)

1. 머지 소트 트리(Merge Sort Tree)

 

머지 소트 트리(Merge Sort Tree)는 분할 정복을 활용하는 합병 정렬(Merge Sort)을 저장하는 자료구조 입니다.

 

2. 머지 소트 트리(Merge Sort Tree) 동작 원리

머지 소트 트리(Merge Sort Tree)는 각 노드에서 해당 노드에 포함된 모든 원소들을 정렬한 상태로 저장하는 트리입니다.

머지 소트 트리(Merge Sort Tree)는 아래와 같이 구성되어 있습니다.

 

1 2 3 4 5 6 7 8
1 2 5 6				3 4 7 8
1 5		2 6		3 7		4 8
1	5	2	6	3	7	4	8

 

3. 머지 소트 트리(Merge Sort Tree) 구현

void merge(int node, int s, int e) {
    int s_size = mergeSortTree[node * 2].size();
    int e_size = mergeSortTree[node * 2 + 1].size();
    int i = 0;
    int j = 0;
    while (1) {
        if (mergeSortTree[node * 2][i] < mergeSortTree[node * 2 + 1][j]) {
            mergeSortTree[node].push_back(mergeSortTree[node * 2][i++]);
        }
        else {
            mergeSortTree[node].push_back(mergeSortTree[node * 2 + 1][j++]);
        }
 
        if (i == s_size || j == e_size) {
            break;
        }
    }
 
    if (i == s_size) {
        for (j; j < e_size; j++) {
            mergeSortTree[node].push_back(mergeSortTree[node * 2 + 1][j]);
        }
    }
    else {
        for (i; i < s_size; i++) {
            mergeSortTree[node].push_back(mergeSortTree[node * 2][i]);
        }
    }
}
 
void makeTree(int node, int s, int e)
{
    if (s == e) {
        mergeSortTree[node].push_back(arr[s]);
        return;
    }
 
    int m = (s + e) / 2;
    makeTree(node * 2, s, m);
    makeTree(node * 2 + 1, m + 1, e);
 
    merge(node, s, e);
}