[트리] [x]INSERTION 삽입 정렬 뒤집기

1. 삽입정렬

11:38

삽입 정렬은 정렬된 부분 배열을 유지하며 이 배열에 새 원소를 삽입해나간다.

 

void insertionSort(vector<int>& A) {
    for(int i = 0; i < A.size(); i++) {
        int j = i;
        while(j > 0 && A[j-1] > A[j]) {
            swap(A[j-1], A[j]);
            --j;
        }
    }
}

 

삽입 정렬이 0~i-1 이 정렬된 배열을 가질때

i를 적절한 위치까지 한칸씩 옮긴다.

 

길이 N인 수열을 삽입 정렬했을 때

각 원소가 몇칸이나 앞으로 이동했는지 를 알고 있을 때

원래 수열을 찾아내야하는게 이 문제의 내용이다.

 

2. 트리 

 

일단 1~n까지 임의로 원소를 만들어. 트리를 형성한다.

 

주어진 배열은 각 원소가 몇칸이나 앞으로 이동했는지 나타내는 배열이다.

 

삽입정렬할 때 배열의 마지막 원소는 맨 마지막에 움직인다.

 

그러므로 주어진 배열의 마지막 인덱스는 마지막 원소의 값을 알 수 있는 힌트를 주는 것과 마찬가지이다.

 

마지막 인덱스를 통해 트리에서 마지막 원소의 값을 얻고

 

그 원소를 제거하면

 

또한 마지막에서 두번째 값을 얻을 수 있다.

 

위의 반복적인 재귀를 통해 모든 값을 결국엔 구할 수 있게된다.

 

다음 코드는 책의 코드이고

이 코드는은 본받아야할 코드이다

 

#include <iostream>
#include <utility>
#include <vector>
#include <algorithm>
 
using namespace std;
 
typedef int KeyType;
 
 
struct Node {
    KeyType key;
    int priority, size;
    Node *left, *right;
    Node(const KeyType& _key) : key(_key), priority(rand()), size(1), left(NULL), right(NULL) {}
    void calcsize() {
        size = 1; 
        if(left)
            size += left->size;
        if(right)
            size += right->size;
    }
    void setRight(Node* _right){
        right = _right;
        calcsize();
    }
    void setLeft(Node* _left) {
        left = _left;
        calcsize();
    }
};
 
typedef pair<Node*, Node*> NodePair;
NodePair split(Node* root, KeyType key)
{
    if(root == NULL) return NodePair(NULL, NULL);
 
    if(root->key < key) {
        NodePair rs = split(root->right, key);
        root->setRight(rs.first);
        return NodePair(root, rs.second);
    }
    NodePair ls = split(root->left, key);
    root->setLeft(ls.second);
    return NodePair(ls.first, root);
}
 
Node* insert(Node* root, Node* node) {
    if(root == NULL) return node;
    if(root->priority < node->priority) {
        NodePair splitted = split(root, node->key);
        node->setLeft(splitted.first);
        node->setRight(splitted.second);
        return node;
    }
    else if(node->key < root->key)
        root->setLeft(insert(root->left, node));
    else
        root->setRight(insert(root->right, node));
    return root;
}
// max(a) < min(b)
Node* merge(Node* a, Node* b) 
{
    if(a == NULL) return b;
    if(b == NULL) return a;
    if(a->priority < b->priority)
    {
        b->setLeft(merge(a, b->left));
        return b;
    }
    a->setRight(merge(a->right, b));
    return a;
}
 
Node* erase(Node* root, KeyType key) {
    if(root == NULL) return root;
    if(root->key == key) {
        Node* ret = merge(root->left, root->right);
        delete root;
        return ret;
    }
    if(key < root->key)
        root->setLeft(erase(root->left, key));
    else
        root->setRight(erase(root->right, key));
    return root;
}
 
Node* kth(Node* root, int k) {
    int leftSize = 0;
    if(root->left != NULL) leftSize = root->left->size;
    if(k<=leftSize) return kth(root->left, k);
    if(k==leftSize + 1) return root;
    return kth(root->right, k - leftSize - 1);
}
 
int countLessThan(Node* root, int x) {
    if(root == NULL) return 0;
    if(root->key >= x)
        return countLessThan(root->left, x);
    int ls = (root->left ? root->left->size : 0);  
    return ls + 1 + countLessThan(root->right, x); 
}
 
 
vector<int> R;
vector<int> B;
 
int T;
int N;
void inorder(Node* tree)
{
    if(!tree) return;
    inorder(tree->left);
    cout<<tree->key<< " ";
    inorder(tree->right);
}
void insertionRestore() 
{
    Node* tree = NULL;
    for(int i = 0; i < N; i++)
        tree = insert(tree, new Node(i+1));
    
    for(int i = N-1; i >= 0; i--)
    {
        Node* element = kth(tree, i + 1 - B[i]);
        R[i] = element->key;
        tree = erase(tree, element->key);
    }
}
int main()
{
    cin>>T;
    for(int i = 0; i < T; i++)
    {
        B.clear();
        R.clear();
        cin>>N;
        B.resize(N);
        R.resize(N);
        for(int j = 0; j < N; j++)
            cin>>B[j];
        insertionRestore();
        for(int j = 0 ; j < N; j++)
            cout<<R[j]<<" ";
        cout<<"\n";
    }
}

• INSERTION